2. gyakorlat: algoritmizálás

Ez a félév második gyakorlata. Célja az algoritmizálás gyakorlása. Erre a gyakorlatra kérjük, hogy mindenki hozzon be egy pakli kártyát. Bármilyen megteszi, magyar, francia, akár uno, solo vagy autós kártya is.

A feladat egyszerű: keverjük meg a kártypaklit, és utána pedig rakjuk sorba. (A kényelem miatt nem kell az egészet, csak kb. 10 lapot.) Magyarázzuk el, hogy hogyan végezzük a sorba rendezést!

Pl.:

1. Kitesszük a lapokat egymás mellé.
2. Keresünk két lapot, amelyek nincsenek jó sorrendben.
3. Ha találtunk, megcseréljük őket, és újra próbáljuk (2. lépés).
4. Ha nincs ilyen páros, készen vagyunk.

Másik lehetőség:

1. Fogjuk a kezünkben a rendezetlen paklit.
2. Tegyünk ki egy lapot az asztalra.
3. Vegyük a következő lapot a rendezetlen pakliból.
4. Helyezzük az asztalra az előző elé vagy mögé, attól függően, mi a helyes sorrend. (Ha már több van, akkor a sor közepére is szúrhatjuk.)
5. Folytassuk addig a 3. lépéstől, amíg el nem fogy a rendezetlen sor.

Próbáljuk ki mind a két megoldást. Hasonlítsuk össze őket:

1. Melyik tűnik gyorsabbnak?
2. Melyik egyszerűbbnek?
3. Melyik tűnik úgy, hogy jobban, pontosabban van megfogalmazva?
4. Vegyük észre, hogy az első megoldás 2. lépése, „keressünk két rossz sorrendű lapot” egyszerűnek tűnik, de igazából egy bonyolult, nehezen megoldható feladatot tartalmaz.
5. Vegyük észre azt is, hogy az első megoldás egyetlen sorral dolgozik (egy rendezetlenből csinál rendezettet), míg a második kettővel: külön tartja a rendezetlen és a rendezett sort. Az első esetben a sor hossza végig ugyanakkora, a második esetben mindkét sor hossza változik.

Az előző előadáson már szerepelt a típus fogalma. Ennek kapcsán nézzük meg, ki milyen fajta kártyát hozott. Hogyan lehetne az egyes kártyákon látható adatokat meghatározni típus szerint? Szám (egész, valós), szöveg, …?

Milyen tulajdonságok határoznak meg pontosan egy kártyalapot? Milyen színek és számok vannak? (Autós kártyánál: milyen egyéb adatok?) Mi az a legkevesebb adat, ami már elegendő ahhoz, hogy egyértelműen azonosítsunk a pakliból pontosan egyet? Van a kártyán olyan adat, ami nem szükséges ehhez? Lehetne tisztán egy egész számmal hivatkozni egy lapra? Kényelmes lenne az játék közben?

Beszéljük meg azt is, mit jelent egyáltalán „sorba rendezni a lapokat.” Az egész számoknál egyértelmű, matematikailag jól definiált dolog az, hogy az egyik szám nagyobb mint a másik. Különböző kártyajátékokhoz viszont (pl. römi) eltérően szokás rendezni a paklit. Az sem egyértelmű, hogy az ász a 2 alatt, vagy a király felett van. Adjunk különféle definíciókat arra, mit jelent, ha az egyik kártyalap „nagyobb”, mint a másik! (Kisebb pedig akkor, ha nem nagyobb. – Igaz ez a kijelentés?)

1. Egyik kártya nagyobb a másiknál, ha a rajta lévő szám nagyobb. A szín pedig nem számít.
2. Ha számítanak a színek, pl. a következő definíciót adhatjuk. Ha nem egyforma a két lap színe, akkor ♠<♣<♥<♦. Ha egyformák, akkor pedig növekvő számsorrend szerint, mint az előző esetben.

A fenti rendezési módszerek nincsenek teljesen pontosan meghatározva. A „keressünk két rossz sorrendben lévő lapot” utasítás egy bonyolult műveletsort takar, hiszen nem tudjuk az egész paklit átlátni egyszerre. Döntsük el ezért, hogy mik az elemi lépések! Legyenek ezek a következők:

1. Egy kártyasoron dolgozunk. Az asztalra egy sorba kitett lapokat kell növekvő sorrendbe rendezni. Új sort nem nyithatunk sem az asztalon, sem a kezünkben.
2. Két kártyát összehasonlíthatunk, és megmondhatjuk, hogy az egyik kisebb vagy nagyobb-e, mint a másik. Nem mondhatjuk, hogy „keressünk egy párt, ami nincs jó sorrendben.”
3. Két kártyát megcserélhetünk egymással.

Ha az asztalra kitett kártyákat lefordítva tartjuk, akkor könnyen betarthatóak ezek a szabályok: mindig legfeljebb két lapot fordíthatunk fel egyszerre összehasonlítás céljából, és ugyanígy végezhetjük a cseréket is.

Egymás melletti lapok vizsgálata

Próbáljuk ki a következőt:

1. Összehasonlítjuk a sor 1. és 2. lapját.
2. Ha rossz sorrendben vannak (a 2. kisebb, mint az 1.), akkor megcseréljük őket.
3. Végezzük ezt el a 2. és 3. lapra, utána a 3. és 4. lapra, és így tovább.

Vagyis menjünk végig a soron, és mindig az egymás mellettieket cseréljük, ha nem jó a sorrend. Mi történik ennek a hatására? Azt látjuk, hogy a legnagyobb lap a sor végére került, a többi sorrendje pedig nem változott.

Ha ezt a műveletsort megismételjük, akkor a 2. legnagyobb lap az utolsó előtti helyre fog vándorolni. Ráadásul az utolsóval már össze sem kell majd hasonlítani, hiszen az volt a legnagyobb, akkor pedig ennél már biztosan nagyobb. Az egyre kisebb maradék, még rendezetlen sorra ismételve a lépéseket végül az egész sor rendezetté válik.

Írjuk le ezt az algoritmust az eddigiekhez hasonlóan, számozott lépésekkel. Használjuk benne változókat! Mondjuk pl. azt, hogy „cseréljük meg az n. és az n+1. lapot!” Két változóra lesz szükségünk: egyikben azt jegyezzük meg, hogy hányadik lapot hasonlítjuk össze az azt követő párjával (ez mindig növekszik); a másodikban pedig azt, hogy milyen hosszú a sor, amelyet vizsgálunk (ez pedig csökken).

Legkisebb lap keresése

Nézzük végig a paklit. Döntsük el, hogy melyik a legkisebb lap! Hogyan tehetjük ezt meg akkor, ha az engedélyezett, elemi összehasonlítási lépés az, hogy két lapot hasonlíthatunk össze egymással?

1. Ha csak egy lap van, akkor az a legkisebb.
2. Ha van egy második is, akkor az lehet, hogy kisebb nála. Ha így van, megjegyezzük azt.
3. Összehasonlítjuk a harmadikat az eddig feltételezett legkisebbel…
4. … és így tovább.

Mit csinálhatunk akkor, ha megtaláltuk a legkisebb lapot? Egyértelmű: a sor elejére tehetjük (megcserélhetjük a sor elején lévővel). Ezáltal legelőre kerül a legkisebb lap, azt már nem kell később elmozdítani onnan. Ha ezt a műveletsort ismételjük addig, amíg el nem fogy a sor, akkor is rendezett sort kapunk. Írjuk le ezt az algoritmust a fentihez hasonlóan! Két változóra lesz szükségünk: a legkisebb lap helyét (sorszámát) megjegyző változóra, és arra, amelyik a helyet tartja nyilván, ahova keressük a maradékból legkisebb elemet.

Rendezzük a leírt algoritmusok utasításai alapján a paklit. (Nem kell mind a 30-50 lap, elég az is, ha egy adott színből kiválasztjuk a számos lapokat, hogy legyen hely az asztalon.) Tartsuk fejben vagy írjuk le papírra a változók aktuális értékeit! Kövessük minden esetben pontosan a leírt utasításokat! Figyeljük meg, helyesek-e az algoritmusok! A helytelenül leírt programnál esetleg már menet közben észrevehetjük, ha hibás.

Ez a feladat elvégezhető párban is. Egy valaki játssza a számítógép szerepét. A másik pedig diktálja az utasításokat. Az utasítások között lehetnek kérdések is, amelyekre az első embernek felelnie kell. (Pl. kisebb az ötödik lap, mint a hatodik?) Vegyük észre, hogy ezek a kérdések visszahatnak a végrehajtásra! Bár úgy tűnik, a program szövege pontosan meghatározza, mikor melyik sort kell végrehajtani, mégis az az adatoktól függ. Ha nem lenne így, elég unalmasak lennének a programok: a működésük nem függene a külvilágtól. Nem tudnának például reagálni a felhasználók kéréseire sem.

Hasonlítsuk össze a fenti két algoritmust. Melyik tűnik gyorsabbnak? Melyikben kell többet cserélgetni a lapokat?

Figyeljük meg azt is, hogyan alakul a fenti algoritmusok hatékonysága abban az esetben, ha a paklik teljesen rendezetlenek; és hogyan akkor, ha az egész pakliból csak egyetlen lap van rossz helyen!

Rajzoljunk egy táblázatot, amelybe ceruzával írjunk véletlenszerűen kiválasztott számokat! Ebben az esetben nem tudunk közvetlenül olyan cserét végezni, mint a kártyáknál. A számokat ugyanis nem vehetjük ki a sorból, legfeljebb kiradírozhatjuk az egyiket, és másikat írhatunk a helyére. (Ez a programozásban az értékadásnak felel meg.) Hogyan működhetnek ekkor a rendezések? Esetleg megoldható a csere értékadásokkal?

1.	2.	3.	4.	5.	6.	7.	8.	9.	10.
23	81	5	88	52	17	2	75	37	22

• Keresés: válasszunk ki név alapján (pl. pikk dáma) egy lapot. Keressük meg ezt a lapot a pakliban (vagy a 10-20 kirakott lap közül, vagyis a hiányos pakliban). Írjuk le ennek is az algoritmusát a fentiekhez hasonlóan! Ötlet: „Ez az? Nem. Következő. Ez az? Nem. Következő. Ez az? Igen!”
• Számlálás: vegyük találomra a pakli egy részét. Számoljuk meg, hogy hány pikk van közte. Írjuk le az ehhez használható algoritmust is!
• Játékokkal kapcsolatos: pl. adott három kártya. Adjunk meg egy kifejezést, amely akkor igaz, ha a három kártya römiben egy helyes kombinációt (tercet) ad. A römiben ez kétféle lehet: ugyanabból a számból három különböző szín, vagy ugyanabból a színből három egymás utáni szám.
• Folyamatábra: rajzoljuk meg az eddigi programjaink folyamatábráját.