Programozni jó! 3. rész
Abonyi-Tóth Andor
2005/03/23 14:55
940 megtekintés
A cikk már legalább egy éve nem frissült, az akkor még aktuális információk lehet, hogy mára elavultak.
Sorozatunk harmadik részében a rekurzió buktatóival és a Pascal és LOGO adatkezelése közötti különbségekkel foglalkozunk.

Sokan úgy gondolják, hogy a LOGO nyelv rekurzív algoritmusok írására teremtődött, amit főleg a rajzos feladatokban lehet remekül használni. Sokan, ha a rekurziót számolásos példában akarják bemutatni, akkor az ismert rekurzív sorozathoz, a Fibonacci-sorozathoz fordulnak, és ennek kapcsán mutatják meg a rekurzió megvalósítását. Mi is tegyük ezt, de előtte a rend kedvéért fogalmazzuk meg pontosan most is a feladatot:

Készítsünk függvényt, amely kiszámítja a Fibonacci-sorozat n-edik elemét!

A sorozat első eleme 1, a második 1, a harmadik pedig már a rekurzív képlettel adódik:

fn=fn-1+fn-2

Ha száraznak tartjuk a feladatot, vagy a puszta képlettel való megadást, akkor bármelyik ismert történetet is előadhatjuk körítésként, például bevezetésképpen a következőt :

Egy lakatlan szigetre vetett a vihar egy arapapagájpárt. A tojó évente egy tojótojást tojik és költ ki, a kikelő tojófióka két év elteltével lesz érett arra, hogy maga is tojjon. 20 év múlva hány tojópapagáj fog élni a szigeten, ha közben egy sem pusztul el?

Egy másik megfogalmazás lehet a következő:

Anna nagy kislány: már nemcsak egyesével, hanem kettesével is tudja venni a lépcsőket. Éppen ezért elhatározza, hogy a lakásukhoz vezető 20 lépcsőn minden nap máshogyan megy fel. Hány napig tart az összes lehetséges változat végigpróbálása?

Mindkét feladat megoldása a Fibonacci-sorozat 20. eleme, noha látszólag nem sok köze van egymáshoz a két feladatnak. A papagájtojók esetén szinte azonnal látszik a képlet szerinti összefüggés, addig a lépcsősnél kis segítséget nem árt adnunk, miért is lesz ez a sorozat a megoldás: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... Ha nincs lépcső, akkor egy módon mehetünk haza. Ha egy lépcsőfok van, akkor is 1 módon. Ha két lépcső fok van, akkor a kezdőszintről léphetünk az első vagy a második fokra, előbbit egy egyes lépéssel folytathatjuk, azaz 2 felmenetel van. Ha n lépcső van, akkor az n-dik fokra úgy juthatunk fel, hogy az előző n-1-dik fokról egyes lépéssel, vagy az n-2-dik fokról egy kettes lépéssel lépünk fel. Az ezekhez vezető utak ezzel az új folytatással különbözőek lesznek, és a kettő összege adja ki az összes lépéssort. A feladat tehát többféleképpen is megfogalmazható, de ugyanaz: fn=fn-1+fn-2 képletnek megfelelően kell kiszámolni az elemeket.

A LOGO-hívők megoldása szinte azonnal kész, a képlet szinte szószerint átírható:

A "vájt szemű" olvasónak feltűnt a zárójel az első híváson: ha elhagyjuk, akkor a LOGO jobbról balra haladó képletfeldolgozása miatt először kiszámítaná n-2 esetére az értéket, és utána ezt 1-gyel növelné, majd ezt vonná ki az n-ből, és az így kapott értékkel hívná meg újra a függvényt, aminek eredménye egyrészt kisebb káosz és egy végtelenségig tartó rekurzió. Aki nem hiszi, járjon utána! Így viszont helyes a képlet. Biztos helyes a függvény is? Próbáljuk ki az eljárást a 60. elem meghatározására! Ha valaki ezt megteszi, és a 10. perc után is még volt türelme a 3 GHz-es Pentium 4-es gépén megvárni az eredményt, az bátran vállalkozhat a húsvétról visszamaradt tojások kiköltésére is. A keresett érték különben 1 548 008 755 920, de még mielőtt bárki kerekített értékre gondolna, a 80. elemet is meghatározhatjuk: ez 23 416 728 348 467 684, ami még ráadásul nem is az utolsó szám.

Mennyi a LOGO-ban még pontosan ábrázolható legnagyobb elem sorszáma?

Lelki füleimmel hallom, hogy a Pascal-pártiak már mondják is: ez is mutatja, hogy a LOGO nem alkalmas semmi komoly feladatra, bezzeg a Pascal! Nézzük akkor a Pascal-megoldást, hisz az is gyorsan elkészíthető: A program futtatási kísérlete után persze enyhe kétségeink támadnak, ha 60-nal próbálkozunk:  a megválasztott adattípus maximum a 46. elemet engedi kiszámolni, az is 6 percig tart, amibe legfeljebb csak egy kicsit kemény tojás főzése fér bele, költeni nincs idő.

A számábrázolásban tehát a LOGO nyert, de ha Pascalban az elemszámot már nem is növelhetjük, legalább az időt csökkentsük le! Erre a megoldás egy kis gondolkodással adódik: a program azért "lassul le" nagyon a sokadik elem esetén, mert a rekurzív hívásokkal teljesen feleslegesen újra és újra kiszámoljuk a korábbi Fibonacci-számokat is, és így a hívásszám exponenciálisan nő. Ennek bemutatására futtassuk le a fakt.ír eljárást LOGO-ban, vagy írjuk meg a párját Pascalban! A kapott híváslista például 10 esetén a következő lesz: A tárolásra építő gyorsítás megoldása Pascalban szinte magától adódik: egy tömbben tároljuk el a már egyszer meghatározott elemeket, és a következő kiszámításához ebből vegyük ki az előzőeket! A LOGO viszont a lista szerkezettel dolgozik, nem kedveli a tömb adatszerkezetet, de a feladat listával is megoldható, és nem is kell sokkal többet gondolkodnunk ezen a megvalósításon sem.

Az alapgondolat annyiban más, hogy itt az első két elemet a kezdő listába megadjuk, majd addig bővítjük a listát egy, a szabálynak megfelelő új elemmel, amíg n elemű nem lesz a lista. Ha ezt elértük, akkor az utolsó listaelem egyben a keresett is. A fakt2 függvény valósítja meg ezt: A függvényünket a fakt.tárol függvénnyel hívjuk meg: A két feladat teljes megoldását a tömörített állományban adjuk meg a további elemzéshez.

Módszertani ajánló

tantárgy

informatika

témakör

programozás

kapcsolat

matematika

évfolyam/korosztály

8 - 12. évfolyam

módszer

programozási hibák bemutatása frontális bevezetéssel és egyéni programvizsgálattal

idő

1 tanóra

célok

A figyelem felkeltése a felesleges rekurzió alkalmazására, illetve a javítás bemutatása

tanulási helyzet

A tanulók a probléma megismerése után programot készíthetnek az alapfeladat megoldására, majd a nagyobb sorszámok esetén fellépő hatékonysági és tárolási problémákra láthatnak példát.

szükséges

számítógépterem, kivetítő, Pascal és Comenius LOGO programozási környezet

szerző

Rozgonyi-Borus Ferenc

cím

http://www.sulinet.hu/tart/cikk/ae/0/25899/1

Rozgonyi-Borus Ferenc
(ABAX)

Csatlakozz hozzánk!

Ajánljuk

European Schoolnet Academy Ingyenes online tanfolyamok tanároknak
School Education Gateway Ingyenes tanfolyamok és sok más tanárok számára
ENABLE pilot Program iskoláknak a bullying ellen
eBiztonság Minősítés Minősítési rendszer oktatási intézményeknek