ugrás a tartalomhoz

Leggyakoribb számsor keresése egy számsorhalmazban

program · 2009. Júl. 11. (Szo), 20.59
Sziasztok!
Van egy problémám amit nem tudok megoldani:

Azt szeretném megcsinálni, hogy van egy két dimenziós tömböm, pl:
3,4,5,6,7,8,9,10,11
3,4,5,6,12,22,23
1,2,3,4,5,6,7,8,9
20,21,22,23,24,25,26,27,8
Az lenne a feladat, hogy keressük ki azt a számsorrészletet melyek a legtöbbször szerepelnek, úgy, hogy a lehető legtöbb sorban benne van.
A példámban pl a megoldás az a 3,4,5,6 mert ez minden sorban szerepel(bár nem kell minden sorban szerepelnie).
Bármilyen segítség jól jön, mert nem tudom megcsinálni:(
‹ Netbeans verziók és pluginek frissítése apache mod_proxy glassfish vs. session ›
 ■
1

metszetek

Poetro · 2009. Júl. 11. (Szo), 22.07
Veszed a halmazok metszeteit, és ezek közül veszed a legnagyobbat.
3

metszet

program · 2009. Júl. 12. (V), 09.43
Ez a metszetes megoldás is tetszik, csak azt nem tudom, hogy mivel nekem táblázatba vannak a számok, akkor h tudom azt megcsinálni, hogy a táblázat minden sora külön TreeSet-be kerüljön? Tehát pl. 100 sor, soronként 20 számmal, az 100 TreeSet-be kerüljön.
5

TreeSet

Poetro · 2009. Júl. 12. (V), 13.16
Egyesével kiveszed a sorokat a táblázatból, csinálsz belőlük Collection-t, abból pedig TreeSet-et.
2

az én verzióm

szabo.b.gabor · 2009. Júl. 11. (Szo), 23.17
Szia!

először is kitalálnék vmi módszert, ami alapján mérni lehet, hogy egy számsor mennyire jó. ahogy látom két kritérium van amit kezelni kell, az egyik a számsor hossza (n), a másik hogy hány sorban szerepel (m). ezekből kell kialakítani egy függvényt, ami meghatározza egy számsor 'jóságát' :) pl. n x m az egyszerűség kedvéért, de lehet mindenféle varázslatot belevinni, attól függően, hogy neked mi számít. tehát az első lépés egy jóságszámítófüggvény kialakítása.

ezek után venném a sorozat első számát, kiszámítanám a hozzá tartozó jóságértéket (x), hozzácsapnám a második számot, kiszámítanám ily módon is a két számból álló sorozat jóságértéket (y). ha x > y zsákutcában vagyunk, továbbmennék a második számmal kezdődő sorozatra, ellenkező esetben pedig hozzácsapnám a sorozathoz a harmadik számot és a három számból álló sorozatra is kiszámolnám a dolgot.

és így szépen végigmennék a számokon mindenhol növelve a sorozat hosszát a lehető legnagyobbra, mindaddig, amíg a jóságérték nem csökken. és mindig tárolnám az éppen legnagyobb jóságértékkel bíró sorozato(ka)t.

vhogy így csinálnám a dolgot.

a kód ami vmi hasonlót csinál elvileg, bár nem futott egyszer sem..

class Szamsor {
	protected $halmaz;
	protected $josagMax;
	protected $legjobbSzamsor;
	
	function __construct($halmaz) {
		$this->halmaz=$halmaz;
		$this->josagMax=0;
		$this->legjobbSzamsor=array();
	}
	
	function keresd(){
		foreach($this->halmaz as $idx1=>$sor){
			foreach($this->sor as $idx2=>$szam){
				$subJosagMax=0;
				$aktualisSzamsor=array($szam);
				while(($tmp=$this->josag($aktualisSzamsor))>=$subJosagMax){
					$subJosagMax=$tmp;
					if(isset($this->halmaz[$idx1][$idx2+1])){		#ha van még szám amit hozzáfűzhetünk
						$aktualisSzamsor[]=$this->halmaz[$idx1][$idx2+1];	#akkor adjuk hozzá
					}else{		#amúgy meg törjünk ki a ciklusból..
						break;
					}
				}
				if($subJosagMax>$this->josagMax){
					$this->legjobbSzamsor=array($aktualisSzamsor);
					$this->josagMax=$subJosagMax;
				}elseif($this->josagMax==$subJosagMax){
					$this->legjobbSzamsor[]=$aktualisSzamsor;
				}
			}
		}
	}
	
	protected function josag(&$szamsor){
		$josag='vmi módon kiszámolod'; 
		return $josag;
	}
}
4

aha

program · 2009. Júl. 12. (V), 09.45
Ez a megoldás nagyon tetszik, de a jósági tényezőre sajnos nincs használható megoldás, mert a számoknak mindegy milyen az értéke, így nem tudom mihez kötni:S
Mindenestre köszi a választ, nagyon ötletes;)
6

egy verzió

szabo.b.gabor · 2009. Júl. 12. (V), 13.33
legyen a kiindulási függvényünk a sorozat hossza, szorozva azzal, hogy hány sorban fordul elő.

1 hosszú dolog szerepel 4 sorban. 1x4 = 4
2 hosszú 3 sorban. 2x3 = 6
3 hosszú 4 sorban 3x4 = 12

de az is lehet, hogy a hosszabb az jobb, vagy a több sor is többet ér.
ilyenkor egy exponenciális függvényt használhatsz.
n - sorozat hossza
m - sorok száma, amiben szerepel a sorozat

n x 2^m - itt a szereplő sorok száma nagyobb hangsúllyal van jelen

3^n x 2^m - mindenből jobb a hosszabb, sorozat hossz hangsúlyosabb, mint a sorok száma

a lényeg, hogy lehet ám olyan függvényt is csinálni a jóságra, ami nem a sorozatban szereplő számok értékére vonatkozik ;)