12. fejezet: Érettségi túlélőcsomag 2 (gyakori algoritmusok)

Ebben a fejezetben néhány gyakran előforduló algoritmust ismertetek. Ezekről sokkal bővebben olvashatsz itt. Érdemes lenne őket alaposan elemezni, de most csak az a célom, hogy az érettségi feladatok megoldásához rendelkezésedre álljon a minimális eszközkészlet. Ez természetesen nem elég: sok gyakorlásra van szükség ahhoz, hogy kialakítsd a feladatok megoldásához szükséges gondolkodásmódot, és az egyszerűbb feladatokat gyorsan, rutinosan oldd meg. Ehhez egy ilyen tananyag kevés: szakkörre, tanórára van hozzá szükség, de jó gyakorlás az érettségi feladatok megoldása, mintamegoldásának elemzése is.

A feladatok tömbökről szólnak. Ez többnyire elég, hiszen fájlból is be lehet olvasni az adatokat egy vagy több tömbbe. Ehhez szükséges, hogy ismerjük az adatok maximális mennyiségét, mert akkora tömböket kell deklarálnunk.
Ebben a fejezetben minden példa ugyanazokról az adatokról szól. Legyen egy szöveges fájl, amely azt tartalmazza, hogy egyes színeket mennyire tartanak vidámnak, 1..10-es skálán.
sárga 10
fekete 1
világoszöld 9
sötétzöld 3
...
A fájlban legfeljebb 100 sor lehet. Ekkor az adatokat beolvashatjuk két tömbbe: szin és vidam, a következőképpen:
db:=0;
while not eof(f) do begin
  readln(f,s);
  db:=db+1;
  szin[db]:=extractword(1,s,[' ']);
  vidam[db]:=strtoint(extractword(2,s,[' ']));
end;

Keresés

Keressük meg, mennyire vidám a piros szín! Lehet, hogy nincs piros az adatok között, erre is készüljünk fel! A 9. fejezetben láthattál ehhez hasonló példát.
i:=1;
while (i<=db) and (szin[i]<>'piros') do i:=i+1;
if i<=db then writeln('Ilyen vidám a piros: ',vidam[i])
else writeln('nincs piros');

Emlékezz arra, hogy ha a while első feltétele hamis, vagyis i>db, akkor a másodikat már nem vizsgálja. i tehát vagy az első pirosnál áll meg, vagy db+1 értéket vesz fel.

Maximumkiválasztás

Keressük meg a legvidámabb színt! A ciklus a legvidámabb szín sorszámát fogja megadni. Kezdjük az első színnel, majd minden további színnél megnézzük, vidámabb-e az eddigi legvidámabbnál, és ha igen, az lesz a legvidámabb.
max:=1;
for i:=2 to db do if vidam[i]>vidam[max] then max:=i;
writeln('Legvidámabb: ',szin[max]);
writeln('Ilyen vidám: ',vidam[max]);

Fontos, hogy max nem a vidámságot, hanem annak sorszámát adja meg! Ez jól is jön, mert így a megfelelő színt is meg tudjuk adni. A program most a legelső legvidámabb színt adta meg, ha a > jelet >=-re cseréljük, akkor a legutolsót kapjuk. A program könnyen átalakítható minimumkiválasztásra.

Rendezés

A rendezés nagyon hasznos algoritmus. Egyrészt gyorsítja a keresést (a szótárban azért tudunk gyorsan keresni, mert a szavak ábécérendben vannak, ha össze-vissza lennének, egy szó miatt a teljes szótárat végig kellene néznünk), másrészt rendezés után az egyformák egymás mellé kerülnek, így pl. könnyen csoportosíthatjuk a színeket vidámság szerint. Mivel a példáink kevés adatot tartalmaznak, a lassú keresés (soros keresés) is gyorsan lefut, ezért inkább a második ok miatt rendezünk.

Az itt bemutatott maximum- (minimum-) kiválasztásos rendezés lényege, hogy pl. csökkenő sorrendhez először megkeressük a legnagyobbat, és kicseréljük a legelső elemmel. Mivel most már a legelső elem a helyén van, ugyanezt a lépést a második elemtől kezdve ismételjük meg. A második helyre tehát bekerült a második legnagyobb. Végül az utolsó előtti és az utolsó elemre hajtjuk végre a maximumkiválasztást.
ciklus i:=1..db-1
max:=a maximális elem sorszáma i és db között
az i-edik és max-adik elem kicserélése
ciklus vége
Ez az algoritmus csökkenő sorrendbe tesz. Minimumkiválasztással növekvő sorrendet kapunk.
A példabeli adatoknál ügyelni kell arra, hogy ha két vidámságot felcserélünk, a hozzájuk tartozó két színt is fel kell cserélni! Rendezzük hát a színeket vidámság szerint csökkenő sorrendbe. (Az utolsó ciklus nem tartozik a rendezéshez.)
for i:=1 to db-1 do begin
//maximumkiválasztás:
  max:=i;

  for j:=i+1 to db do if vidam[j]>vidam[max] then max:=j;
//csere:
  mv:=vidam[i]; vidam[i]:=vidam[max]; vidam[max]:=mv;

  ms:=szin[i]; szin[i]:=szin[max]; szin[max]:=ms;
end;
for i:=1 to db do writeln(szin[i],' ',vidam[i]);

A többszempontú rendezés azt jelenti, hogy ha az első szempont szerint több egyforma van, akkor azokat még egy másik szempont szerint sorba rakja. A példában az egyforma vidám színek szomszédosak lesznek a rendezés után, ezeket rendezhetjük a szín neve szerint ábécébe. A relációs jelek szövegek között is működnek, az a string "nagyobb", amelyik ábécérendben később következik. Ez sajnos csak az angol ábécé karaktereire működik, ráadásul megkülönbözteti a kis- és nagybetűket, de példának jó lesz.
A kulcs a maximumkiválasztás relációjának módosítása, mert ez határozza meg, hogy egy adatot mikor kell előbbre hozni a tömbben. Az eredeti feltétel: vidam[j]>vidam[max], ha ez teljesül akkor kell a j. adatot előbbre hozni. Ezt módosítjuk:
(vidam[j]>vidam[max]) or ((vidam[j]=vidam[max]) and (szin[j]<szin[max]))
Tehát ha vidámabb a szín, előbbre jön, ha két szín egyforma vidám, akkor az ábécében korábbi jön előre.

Feladatok

48. Olvasd be két tömbbe a példákban szereplő fájlt (feladat6.txt), majd írd ki a legkevésbé vidám színeket! (Tipp: minimumkiválasztás, majd a minimálissal egyenlők kiírása.)
49. Írj ki egy színt, amelynek a vidámsága 3! (Nem biztos, hogy van. Ahhoz, hogy ennek a működését teszteld, két különböző bemeneti fájllal kell kipróbálnod, az egyikben van 3, a másikban nincs.)
50.  Írd ki a színeket ábécérendben! (Az ékezetes karakterekre nem lesz jó, de nem baj.)

ċ
András Lutter,
2014. dec. 28. 4:17
Comments