Csak akkor olvass tovább, ha a többszörös megszámlálás feladatot megoldottad, vagy nem sikerült megoldani.
Alapeset
Az alap probléma tehát az, hogy számoljuk meg, egy szám hányszor fordul elő egy olyan tömbben, amely a [0;10] intervallumból tartalmaz elemeket.
A megoldás rendkívül egyszerű és elegáns. Először is szükségünk van egy olyan tömbre, melynek akkora a mérete, mint ahány féle számot tartalmaz az a tömb, melyben a megszámolandó számok vannak. Ez a tömb tartalmazza majd azt, hogy a számok közül melyiket hányszor számoltuk meg. Mivel a tömb, melyben a megszámlálandó számok vannak csak a [0;10] intervallumból tartalmaz értékeket, ezért itt 11 féle szám fordulhat csak elő. A darabszámokat tartalmazó tömb mérete így 11 lesz.
A trükk lényege az, hogy az megszámlálás eredményét tartalmazó tömb megfelelő indexei fogják jelenteni a megszámlálandó számokat, az adott indexű elem értéke pedig a darabszámot.
Nézzük mit jelent például az, ha a darabszámokat tartalmazó tömb a megszámlálás után így néz ki. Ez csak egy példa, nem a feladat eredménye. A megjegyzés sorban a darab tömb indexei szerepelnek, alatta pedig az adott indexhez tartozó értékek:
// 0 1 2 3 4 5 6 7 8 9 10
{ 5, 3, 0, 7, 3, 8, 2, 8, 9, 2, 0 }
Ez ebben az esetben azt jelenti, hogy a 0 számból 5 darabot számoltunk, az 1-es számból 3-at, 2-es szám nem szerepelt, stb.
A szép az egészben az, hogy még feltételvizsgálatra sincs szükség a megszámlálásra, de példán keresztül hamarabb megértjük.
int[] szamok = { 2,5,4,0,10,1,4,8,5,2,8,1,9,10,
7,7,3,5,2,4,3,8,0,8,10,8,1,1,8,
10,7,7,3,8,3,6,6,7,5,8,9,3,9,3,
5,9,9,5,2,8,10,4,1,0,4,9,2,5,5 };
int[] db = new int[11];
for( int i = 0; i < szamok.length; i++ )
{
db[ szamok[i] ]++;
}
System.out.println("A tombben levo szamok darabszama:");
for( int i = 0; i < db.length; i++ )
{
System.out.println(i+": "+db[i]);
}
Ennyi lenne csak? Igen. Mit is csinálunk? A db tömb megfelelő helyén lévő számot megnöveljük eggyel. Pontosabban: a db tömb “számodik” indexű elemét megnöveljük eggyel. Vagyis ha a ‘szamok’ tömbben éppen egy 3-as számnál járunk, akkor a db[3] elemet növeljük meg eggyel, vagyis megszámoltuk! A végén pedig az eredménytömbben látni fogjuk, melyik indexnél milyen érték szerepel, vagyis melyik számból hány darab volt.
Pozitív irányba eltolt intervallum
Oké, de mi van akkor, ha az intervallum nem 0-val kezdődik, vagyis valamilyen irányba el kellett tolni? Például a tömbben lévő számok intervalluma [5;20], mint ahogy az egyik feladatban is szerepel. Akkor a darabokat tároló tömb méretét is ennek megfelelően kell megválasztani, vagyis 0-20 indexeknek kell rendelkezésre állni. Az egy dolog, hogy a 0-4 indexeknek itt semmi jelentősége nem lesz, de ez senkit nem érdekel. Ami fontos, hogy különbséget tudj tenni aközött, hogy a 3-as index eleme nulla, és a 7-es index eleme nulla. Az első ugye egy nem létező szám, mert ilyen szám nincs az intervallumban. A 7-es index eleme pedig azt jelenti, hogy nincs 7-es szám a tömbben. Lássuk akkor így a példát:
int[] szamok = { 13,18,11,14,17,12,18,11,11,17,17,13,
5,13,5,14,19,5,11,15,11,12,13,20,
18,16,16,13,11,17,17,19,5,14,11,
14,11,14,8,14,13,20,17,6,20,17,
18,9,9,12,15,20,10,5,7,11,19,16,
11,10,10,11,14,20,5,10,10 };
int[] db = new int[21];
for( int i = 0; i < szamok.length; i++ )
{
db[ szamok[i] ]++;
}
System.out.println("A tombben levo szamok darabszama:");
for( int i = 5; i < db.length; i++ )
{
System.out.println(i+": "+db[i]);
}
Ha jobban megnézed, az algoritmusban gyakorlatilag csak a két kiemelt sorban van különbség. Az egyik az, hogy más a tömb mérete, amibe meg akarom számolni az egyes számok előfordulásait. A másik az, hogy amikor a darabszámaikat ki akarom írni, akkor az első 5 elemet kihagyom, hiszen azok nem valódi eredményt tartalmaznak.
Negatív irányba eltolt intervallum
Eddig rendben is volnánk, bármilyen nem negatív számokat tartalmazó tömbben könnyen megszámolhatjuk az előfordulásokat. És ha negatív irányba toltuk el? Negatív indexek nem léteznek. Akkor mit tehetünk? Toljuk el úgy, hogy nekünk jó legyen.
A feladat alapján a tömbben lévő számok a [-10;10] intervallumban vannak. Akkor mit csináljunk? Azt, hogy hány féle számot kell megszámolni, könnyen megkaphatjuk, hiszen csak az intervallum méretét kell kiszámolni. Ha emlékszel rá, ezt már a véletlen számok sorsolásánál is kihasználtuk: felső-alsó+1=21. Ha ez megvan, akkor létrehozunk egy ekkora tömböt, melybe a darabszámokat rögzítjük. A megszámlálás során pedig mi figyelünk arra, hogy az intervallumot meg az elemeket is az eltolás mértékének megfelelően kezeljük. Mennyivel kell és merre eltolni ezt az intervallumot, hogy a kezdőpontja a 0 legyen? +10-zel, igaz?
Akkor lássuk a megoldást ennek megfelelően:
int[] szamok = { -2,9,4,2,6,4,2,-9,5,-1,0,-6,-6,
2,-3,-9,-4,7,-2,-9,3,5,-9,2,-5,
-8,-5,0,-9,-7,-8,-2,9,5,7,-7,
-1,3,-9,0,9,-3,-1,2,-3,8,-9,4,
-2,-2,-4,6,-5,-3,6,10,-3,8,5,
-6,1,-9,-9,-4, 8,0,3 };
int[] db = new int[21];
for( int i = 0; i < szamok.length; i++ )
{
db[ szamok[i]+10 ]++;
}
System.out.println("A tombben levo szamok darabszama:");
for( int i = 0; i < db.length; i++ )
{
System.out.println((i-10)+": "+db[i]);
}
Itt azért picit több sort emeltem ki, nézzük őket tételesen:
- 7 – A darabokat tároló tömb mérete pontosan akkora, mint ahány féle szám előfordul a tömbben.
- 10 – Itt az első trükk, hogy az adott előfordulásokat a darab tömbben mindig 10-zel pozitív irányba eltolva tároljuk. Vagyis a -10-es számot a 0 index jelenti, a -9-et az 1-es, -8-at a 2-es, stb.
- 13 – Az eredményeket kiírató tömbben ilyenkor nem kell gondolkodni azon, hogy honnan kezdjük a kiíratást, hiszen az eltolással pontosan azt oldottuk meg, hogy a tömb 0-tól indulva tartalmazza a megfelelő darabszámokat.
- 15 – Amikor a darabszámokhoz hozzá akarunk férni, akkor pontosan fordítva gondolkodunk. Minden i-edik index valójában egy 10-zel kis kisebb számot jelent, vagyis a 0 indexű elem a -10-et, az 1-es indexű a -9-et, stb. Az adott indexű helyen lévő érték továbbra is a darabszámot jelenti, vagyis ezt békén hagyjuk. Csak akkor tolunk el a megfelelő irányba amikor az indexet kezeljük.
Ez most nem ugyanaz?
Ha olvasás közben egy időre meg is álltál átgondolni az eddigieket, felvetődhetett benned a gyanú, hogy ez a megoldás, ami eltolja az intervallumot, lehet, hogy mindkét irányban működik. Emlékszel, pozitív irányú eltolásnál figyelmen kívül hagytam dolgokat. Nem foglalkoztam a nem létező megszámlálandó számokkal, egyszerűen csak figyelmen kívül hagytam őket.
Valójában nem biztos, hogy célszerű minden esetre külön megoldást megjegyezni. Természetesen az is lehet helyes, de felesleges. Miért? Mert az egészben az a legszebb, hogy a negatív irányba eltolt intervallumos mindkét esetben alkalmazható, sőt, két nem elegáns dolgot is kiküszöböl:
- a darabokat tároló tömb mérete ne legyen nagyobb, mint ahány féle elemet számolni szeretnénk
- nem kell a tömb elején azokat az indexeket kikerülni a for ciklusban, melyeknek nincs jelentése
Univerzális megoldás
Lássuk akkor azt a megoldást, amely nem egy konkrét feladat megoldása, hanem beleírom azokat a fontos dolgokat, melyek a megoldást általánossá teszik. Ez a megoldás nem igazán tér el az előző pontban ismertetett megoldástól, csak annak egy általános változata.
int[] szamok = // tetszőleges intervallumbeli egészeket tartalmazó tömb
int[] db = new int[ /* az intervallum mérete */ ];
for( int i = 0; i < szamok.length; i++ )
{
db[ szamok[i]-/* az intervallum alsó határa*/ ]++;
}
System.out.println("A tombben levo szamok darabszama:");
for( int i = 0; i < db.length; i++ )
{
System.out.println((i+/* az intervallum alsó határa */)+": "+db[i]);
}
Megoldás változó értékekkel
A következő megoldást úgy írom meg, hogy amit csak lehet, kisorsoltatok vele. A program minden futásakor mindig más intervallumból sorsol elemeket változó számú elemet, megszámolja, hogy melyik szám hányszor fordul elő a tömbben, és a darabszámokat kiírja a képernyőre. A megoldásban annyit kötök csak ki, hogy az intervallum mérete maximum 100 lehet, és a tömb nem tartalmazhat 30 számnál többet. Ha akarnám, ezek lehetnének jóval nagyobbak is, de az átláthatóság miatt ezeket lekorlátoztam.
// addig sorsolunk intervallum határokat, amíg az alsó nem kisebb, mint a felső
int felso, also;
do
{
also = (int)(Math.random()*101)-50;
felso = (int)(Math.random()*101)-50;
}
while( !(also < felso) );
// a sorsolt intervallumból feltöltünk egy tetszőleges (max 30) méretű tömböt
int[] tomb = new int[(int)(Math.random()*30)+1];
// kiírjuk az értékeket, hogy ellenőrizni lehessen
System.out.println( "innen sorsoltunk szamokat: ["+also+";"+felso+"]" );
System.out.println( "ennyi fele szamot sorsolhatunk: "+(felso-also+1) );
System.out.println( "ennyi darabot sorsoltunk: "+tomb.length );
System.out.println( "ezeket sorsoltuk:\n" );
for( int i = 0; i < tomb.length; i++ )
{
tomb[i] = (int)(Math.random()*(felso-also+1))+also;
System.out.print( tomb[i]+" " );
}
System.out.println();
// a kisorsolt számok intervallumának megfelelően létrehozzuk a számlálótömböt
int[] db = new int[felso-also+1];
// megszámoljuk, melyik számból hány darab van a tömbben
for( int i = 0; i < tomb.length; i++ )
{
db[ tomb[i]-also ]++;
}
// kiírjuk, melyik számból hány darab van a tömbben
System.out.println("\nA tombben levo szamok darabszamai:");
for( int i = 0; i < db.length; i++ )
{
System.out.println((i+also)+": "+db[i]);
}
Egy program kimenet:
innen sorsoltunk szamokat: [-3;5] ennyi fele szamot sorsolhatunk: 9 ennyi darabot sorsoltunk: 12 ezeket sorsoltuk: 0 -1 4 4 0 -3 5 4 4 -3 5 2 A tombben levo szamok darabszamai: -3: 2 -2: 0 -1: 1 0: 2 1: 0 2: 1 3: 0 4: 4 5: 2
A többszörös megszámlálás ettől a ponttól kezdve új eszközt adott a kezünkbe, hiszen ettől kezdve ilyen kérdésekre nagyon egyszerűen tudunk válaszolni:
- mely számok nem szerepelnek a tömbben?
- mely számok szerepelnek a legtöbbször a tömbben?
- mely számok fordulnak elő pontosan kétszer a tömbben?
Ettől kezdve csak a fantázia szabhat határt, hogy mi mindenre jó még ez a technika. A lényeg csak annyi: ismerd fel, hogy az adott feladat ezzel leegyszerűsíthető.