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..
  1. class Szamsor {  
  2.     protected $halmaz;  
  3.     protected $josagMax;  
  4.     protected $legjobbSzamsor;  
  5.       
  6.     function __construct($halmaz) {  
  7.         $this->halmaz=$halmaz;  
  8.         $this->josagMax=0;  
  9.         $this->legjobbSzamsor=array();  
  10.     }  
  11.       
  12.     function keresd(){  
  13.         foreach($this->halmaz as $idx1=>$sor){  
  14.             foreach($this->sor as $idx2=>$szam){  
  15.                 $subJosagMax=0;  
  16.                 $aktualisSzamsor=array($szam);  
  17.                 while(($tmp=$this->josag($aktualisSzamsor))>=$subJosagMax){  
  18.                     $subJosagMax=$tmp;  
  19.                     if(isset($this->halmaz[$idx1][$idx2+1])){        #ha van még szám amit hozzáfűzhetünk  
  20.                         $aktualisSzamsor[]=$this->halmaz[$idx1][$idx2+1];    #akkor adjuk hozzá  
  21.                     }else{      #amúgy meg törjünk ki a ciklusból..  
  22.                         break;  
  23.                     }  
  24.                 }  
  25.                 if($subJosagMax>$this->josagMax){  
  26.                     $this->legjobbSzamsor=array($aktualisSzamsor);  
  27.                     $this->josagMax=$subJosagMax;  
  28.                 }elseif($this->josagMax==$subJosagMax){  
  29.                     $this->legjobbSzamsor[]=$aktualisSzamsor;  
  30.                 }  
  31.             }  
  32.         }  
  33.     }  
  34.       
  35.     protected function josag(&$szamsor){  
  36.         $josag='vmi módon kiszámolod';   
  37.         return $josag;  
  38.     }  
  39. }  
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 ;)