Láthattad, hogy az alap algoritmusok nagyon sokféle feladatra szinte kész megoldásokat adnak. A valóságban azonban sokszor nem ilyen tiszta formában fordulnak elő, mivel a feltételek lehetnek bonyolultabbak is. Nem ennyire egyszerű a dolog, ha például a kérdés nem pusztán a legnagyobb vagy legkisebb elemre vonatkozik, hanem egy feltételt is tartalmaz. Nézzünk pár példát:
Tölts fel egy 10 elemű tömböt a [-10;50] intervallumból.
- Melyik a legkisebb negatív szám?
- Melyik a legnagyobb pozitív szám?
- Melyik a legnagyobb negatív szám?
- Melyik a legkisebb pozitív szám?
Az első két feladat valójában annyira nem is vészes, hiszen a legkisebb negatív szám az valójában ugyanazt jelenti, mint a legkisebb szám, a legnagyobb pozitív pedig a legnagyobb szám. Innentől úgy tűnik, hogy csak egy egyszerű minimum és maximumkeresésről van szó. A helyzet azonban ennél árnyaltabb. Lássunk egy teszt feladatot az első feladatra:
Melyik a tömbben szereplő legkisebb negatív szám?
int[] tomb = {-1,3,7,6,-5,9,4,2,-7,-4};
// minimumkeresés, ahol beállítjuk az első minimum helyét
int min = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] < tomb[min] ) min = i;
}
System.out.println("A tombbeli legkisebb negativ szam: "+tomb[min]);
Ez így helyes is, hiszen az első elem negatív volt, és attól még kisebbet is találtunk.
Mi van akkor, ha a tömbünk ezeket az elemeket tartalmazza:
int[] tomb = {3,-2,7,6,-5,9,4,2,-7,-4};
int min = 0;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] < tomb[min] ) min = i;
}
System.out.println("A tombbeli legkisebb negativ szam: "+tomb[min]);
Ha ekkor is az első elemet tekintjük az első minimumnak, akkor gond van, hiszen a legkisebb negatív számot keressük, ez pedig nem is negatív? Pánikra semmi ok, hiszen az első negatív szám ettől úgyis kisebb lesz, és akkor helyreáll a világ rendje. Az eredmény: -7
És ha a tömb így néz ki?
int[] tomb = {3,2,7,6,5,9,4,2,7,4};
Bebuktuk… Az elsőt tekintjük az első minimumnak, hiszen így tanultuk. Az sem segít rajtunk, hogy bármelyik negatív szám kisebb lesz egy pozitívnál, és akkor kicserélhetjük, pontosan úgy, ahogy az előző példában láttuk. De ebben a tömbben nincs is negatív szám! Az eredmény: 2 Vagyis csak a legkisebbet találtuk meg, ami viszont nem negatív!
Az ötlet
Ennél a feladatnál azonban egy jó ötlettel egyszerűsíteni lehet a feladaton. A minimumkeresés esetén ugye abból indulunk ki, hogy a tömb első elemét tekintjük alaphelyzetben a legkisebbnek. Ezután a következő elemtől kezdődően mindegyikkel összehasonlítjuk az addigi minimumot, és ha az aktuális elem kisebb, akkor az lesz az új minimum. Nem felejtjük el, hogy továbbra is csak a minimumelem helyét tároljuk! Alapesetben kétszer van gond ezzel a feladattal:
- Az első elem pozitív, de vannak utána negatív elemek.
- Csak pozitív elemeket tartalmaz, tehát az első is az.
Mindkét esetben az a probléma, hogy eleve nem jó elemet feltételezünk a legkisebbnek, mert a legkisebb negatívot keressük, de elsőként egy pozitív elemet tekintünk helyesnek.
Az 1. esetben ezzel nincs gond, mivel van benne még negatív szám, az úgyis kisebb lesz, tehát gond megoldva. A 2. esetben gond van, mert az első nem helyes elemet nem tudjuk kicserélni egy negatív elemre, mivel nincs a tömbben ilyen.
Egy ötlettel mégis meg tudjuk oldani a helyzetet: Ha az algoritmus végén a legkisebb elem pozitív, akkor kiírhatjuk, hogy nincs benne negatív elem. Ha nem pozitív, akkor kiírjuk, hogy ez a minimum.
Az univerzális megoldás
Akkor mit tehetünk akkor, ha nincs ötletünk? Vagy az az ötlet nem használható minden esetre? Akkor nem a sablon megoldást használjuk, elkerülve ezzel azt, hogy rossz elemet válasszunk az elején. Vagyis nem az elsőt tekintjük a legkisebbnek. Senkit nem tekintünk annak! Azt feltételezzük, hogy nincs is ilyen. Lássuk akkor ezt a megoldást.
int[] tomb = new int[10];
for( int i = 0; i < tomb.length; i++ )
{
tomb[i] = (int)(Math.random()*61)-10;
}
int min = -1;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] < 0 && (min == -1 || tomb[i] < tomb[min]) ) min = i;
}
if( min != -1 )
{
System.out.println("A tombbeli legkisebb negativ szam: "+tomb[min]);
}
else
{
System.out.println("A tombben nincs negativ szam.");
}
A kiemelt részek jelentése a következő:
- 8 – Hoppá, -1 indexű elem nem is létezhet! Igen, pont ez a lényeg. Azért hivatkozok nem létező elemre, hogy a ciklus után eldönthessem, hogy találtam-e egyáltalán olyan számot, mely a feltételemnek megfelel, vagy a tömb nem is tartalmaz olyat.
- 10 – Vedd észre, hogy itt nem 1-től indul a ciklusváltozó! Mivel nem az első elemet feltételezzük a legkisebbnek, ezért az elsőt is meg kell vizsgálni.
- 12 – Na ez egy picit összetettebb:
Az ÉS-sel összekötött részfeltételek első tagja: ha a szám negatív. Ez ugye az alapfeltétel, hogy legkisebb negatív számot keresünk. Pozitív számra nem cserélhetjük le a minimumhelyet. Ami utána jön az viszont megint egy összetett feltétel:
ha a min értéke -1, vagyis még nem találtunk olyan számot, ami nekünk jó
vagy
az aktuális elem kisebb, mint az eddigi minimum (ez meg az alap minimumkeresés feltétele)
Ha az egész feltételt egyben nézzük, akkor azt kapjuk, hogy ha a számunk negatív (tehát megfelel az alapfeltételünknek) ÉS még nem találtunk egyet sem, ami jó, vagy már találtunk olyat, ami jó, de a mostani kisebb tőle, AKKOR legyen ez az új minimum helye. - 15-22 – Ez a feltételes rész már csak a választ adja meg: Ha az eredeti -1 értékű minimum maradt, akkor egy olyan szám sem volt, ami nekünk jó lenne, egyébként pedig ez lesz a feltételünknek megfelelő szám helye.
Ebben az összetett feltételben nagyon fontos a feltételek sorrendje!
- Először vizsgálni kell, hogy egyáltalán megfelelő számmal dolgozzak, ezt biztosítja azt, hogy csak negatív elemmel foglalkozzunk, a többi alapból kiesik a kosárból.
- Aztán megnézem, hogy van-e egyáltalán minimum.
- Majd ha már van minimum (vagyis nem -1 a min), akkor már tényleg össze lehet hasonlítani őket.
Ha az ÉS utáni feltételek nem megfelelő sorrendben állnak, az mit okozhat? Futási hibát! Miért? Gondolj bele: a min -1 értékről indul. Ha negatív számot találok (1. feltétel), akkor azonnal össze kell ezt hasonlítani a tomb[min] értékkel? Nem is lehet, hiszen a min értéke még -1, hiszen egy jó számom sem volt, akkor nincs is mihez hasonlítani. A tömb[-1] elszáll, mint a győzelmi zászló! A VAGY feltételnél az első tag biztosítja azt, hogy a második csak akkor kerüljön megvizsgálásra, ha az első hamis. Vagyis: csak akkor vizsgálhatom meg a tomb [min]-t, ha az valóban létezik!
Ez a szép, vagy épp utálatos a programozásban, hogy gondolkodni kell benne, mert a vizsgálatok sorrendje sem biztos, hogy teljesen mindegy.
Akkor lássuk, hogy miért jobb egy általánosabb megoldást megjegyezni, mint külön minden esetre egy-egy ötletet keresni. Mert az előző trükk a következő feladatnál nem működik:
Melyik a tömbben szereplő legnagyobb negatív szám?
Nézzük milyen esetek vannak:
- A tömb csak negatív elemeket tartalmaz.
- A tömb első eleme negatív, de vannak benne pozitív elemek is.
- A tömb első eleme pozitív, de vannak benne negatív elemek is.
- A tömb csak pozitív elemeket tartalmaz.
Az első eset még csak-csak működne, hiszen csak negatív elemek esetén a maximum az tényleg a legnagyobb negatív szám lesz. A többinél azonban a legnagyobb elem keresése már komoly gondokba ütközik.
A maximumkeresés során arra kell figyelni, hogy a pozitív számokat eleve ki kell zárni a vizsgálatból, csak a negatív számokra kell koncentrálni. Most nem akarom újra végigmagyarázni a teljes programot, nézzük akkor a lényeget.
int max = -1;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] < 0 && (max == -1 || tomb[i] > tomb[max]) ) max = i;
}
- 1 – Itt is -1 a maximum elem helye, mivel senkit nem tekintünk alapból a legnagyobbnak.
- 4 – Itt is 0-ról indul a ciklusváltozó, mivel az első elemet is meg kell vizsgálni.
- 6 – A feltétele is nagyon hasonló: Ha negatív számot találunk ÉS eddig nincs maximum VAGY az aktuális elem nagyobb az eddiginél, AKKOR ez az új maximum.
Ha valakinek nagyon nem megy ez az összetett feltétel, akár fel is bontható:
(feltétel1 ÉS (feltétel2 VAGY feltétel3)) helyett ((feltétel1 ÉS feltétel2) VAGY (feltétel1 ÉS feltétel3))
Megjegyzem, itt sem lehet a VAGY két tagját felcserélni, az ugyanúgy futási hibát okozhat. A feltételek sorrendje kötött!
Melyik a tömbben szereplő legkisebb pozitív szám?
Az előzőhöz hasonló. A fenti ötlet itt sem működik. Próbáld meg az előző megoldás alapján saját magad megírni a helyes algoritmust. Ha nem megy, a megoldás alul található minden különösebb magyarázat nélkül.
int[] tomb = new int[10];
for( int i = 0; i < tomb.length; i++ )
{
tomb[i] = (int)(Math.random()*61)-10;
}
int min = -1;
for( int i = 0; i < tomb.length; i++ )
{
if( tomb[i] > 0 && (min == -1 || tomb[i] < tomb[min]) ) min = i;
}
if( min != -1 )
{
System.out.println("A tombbeli legkisebb pozitiv szam: "+tomb[min]);
}
else
{
System.out.println("A tombben nincs pozitiv szam.");
}
Természetesen ettől különböző megoldások is léteznek, és azok is teljesen helyesek lehetnek. Az is lehet, hogy egyszerűbb, mint a megoldásom. Nyilván én is megtehettem volna, hogy a legnagyobb negatív szám esetén kiválogatom a negatív számokat egy másik tömbbe, és arra ráeresztek egy maximumkeresést minden különösebb feltételvizsgálat nélkül. Én csak egy gondolatmenetet kívántam megosztani, ami hátha inspirálja azokat, akik vagy nem tudták megoldani ezeket a feladatokat, vagy a megoldásuk bonyolult.