Fibonacci
Írj programot, mely kiírja a képernyőre az első n Fibonacci számot. Az n változó értékét a felhasználó adhassa meg! Írd meg rekurzívan és iteratívan is!
Fibonacci szám-e
Készíts programot, mely a felhasználótól bekér egy természetes számot, majd megállapítja róla, hogy a szám Fibonacci szám-e!
Collatz-féle sorozat
A matematikában a Lothar Collatzról elnevezett sorozatot a következőképpen definiáljuk. Kezdőértéknek válasszunk egy tetszőleges egész számot. A sorozatnak minden további elemét az előzőből származtatjuk, méghozzá így:
- an+1 = an / 2, ha an páros
- an+1 = 3an + 1, ha an páratlan
A sejtés az, hogy ez a sorozat mindig eléri az 1-et – ezt máig senkinek nem sikerült sem bizonyítania, sem ellenpéldát találni rá. A sorozatban néha csak a kezdőelemnél kisebb számok vannak:
20 10 5 16 8 4 2 1
Néha azonban eléggé megnő:
23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
Írj programot, amely a) kiírja a sorozatot egy meghatározott értéktől kiindulva, b) megmondja, hogy hány lépés kell egy adott értéktől kiindulva 1-ig elérni! Írd meg ezeket iteratív és rekurzív változatban is!
Lista előre és hátra
Írj a) iteratív b) rekurzív függvényt, amely kiírja egy lista elemeit x) előrefelé y) hátrafelé. Vegye át mindegyik függvény paraméterként a kiírandó listát! Hozz létre a főprogramban egy tíz és egy öt elemű, egész értékekkel feltöltött listát. Hívd meg a függvényeket a listákra!
Mi kell ehhez? Az iteratív bejárást ismered, egy ciklus, ami 0-tól a lista méretéig megy (–1, értelemszerűen), vagy a lista méretétől 0-ig.
A rekurzív bejáráshoz két részre kell választani a listát, az első elemre és az összes többi elemre. (Mi az első elem indexe? Hogy lehet vágással előállítani egy olyan listát, amelyik a többi elemet tartalmazza?) Ha rekurzívan előbb az első elemet írod ki, és utána a többit, akkor előrefelé sorrendet kapsz. Ha előbb a többit írod ki rekurzívan, és utána az elsőt, akkor hátrafelé, fordított sorrendet.
Aknakereső
Írd meg azt az algoritmust, amely az aknakeresőben felfedi a pálya aknák nélküli részét! Egy kétdimenziós pályán néhány akna van elszórva. A felhasználó szabadon léphet bármelyik mezőre. Ha aknára lép, veszít; ha nem, akkor megmutatjuk neki, hogy a választott mező mellett hány másik mező tartalmaz aknát (0 és 8 között). Ha 0, akkor a szomszédos mezők egyike sem tartalmaz aknát, vagyis azokra biztonságosan lehet lépni; ha azoknál is valamelyik mezőre 0 adódik, természetesen még tovább, arra is. Készíts függvényt, amely egy összefüggő, akna nélküli területet teljesen felderít!
Tükörszámok
Írj rekurzív programot, amely kilistázza az n számjegyből álló tükörszámokat!
Többféle elvű megoldás is lehetséges. Az egyik érdekes változat az, amikor a sok egymásba ágyazott for ciklust helyettesíti a rekurzió.
Emeletes ház (Dinesman feladata)
Ez a feladat már szerepelt egyszer:
Baker, Cooper, Fletcher, Miller és Smith egy ötemeletes ház különböző emeletein laknak. Baker nem a legfölső emeleten lakik, Cooper pedig nem az alsó szinten. Fletcher lakhelye sem a legalsó szinten van, de nem is a legfölsőn. Miller magasabban lakik, mint Cooper. Smith nem Fletcherrel szomszédos emeleten lakik, ahogy Cooper és Fletcher sem emelet-szomszédok. A kérdés: melyik emelet kié?
Akkor az a tipp szerepelt mellette, hogy az összes lehetőség közül (11111, 11112, 11113 stb.) első körben azokat kell kiszűrni, ahol az öt változó közül van két egyforma.
Oldd meg most másképp a feladatot! Tedd be egy listába az öt különböző számot, amely lista egyes elemei rendre Baker, Cooper, Fletcher, Miller és Smith emeleteinek számát mutatják. Írj függvényt, amely permutálja a listát, és írj olyan függvényt is, amely ellenőrzi a megkötéseket! Írj ezek használatával egy programot, amely megoldja a feladatot!
Zárójelek párjai
Írj rekurzív programot, amelyik egy nyitó zárójellel kezdődő sztringben megtalálja a zárójel bezáró párját. (A zárójelek (egymásba () lehetnek)) ágyazva.
Írd meg ugyanezt iteratívan is!
Rendezés közvetlen kiválasztással
Egy lista rendezve: a legelejére rakjuk a legkisebb elemet, utána rendezzük a lista fennmaradó részét. Minden iteráció átírható rekurzióvá: írjuk meg a közvetlen kiválasztásos rendezőt rekurzívan!
Három számjegyenkénti felosztás
Írj függvényt, amely a paraméterként kapott pozitív egész számot három számjegyenként csoportosított formában írja ki. Pl.: 16 077 216. Próbáld ki más számokra is: 999, 1000, 12, 0, 1000222!
Tipp
Használj rekurziót! Ez olyan, mintha ezres számrendszerben írnál ki.
Hanoi tornyai – lépés sorszáma
A rekurziós előadáson volt szó a Hanoi tornyai feladatról. Ott szerepel egy megoldás, amely kiírja, mikor melyik korongot kell áthelyezni. Módosítsd azt a programot úgy, hogy beszámozza a lépéseket! (Ha esetleg globális változóra gondolnál, meg lehet oldani anélkül is!)
Hanoi tornyai – grafikusan
Írd át úgy a Hanoi tornyai programot, hogy valamilyen grafikus könyvtár segítségével (pl. teknőcgrafika) ki is rajzolja a cseréket!
Járda kövezése I.
Hányféleppen lehet egy adott hosszúságú járdát kikövezni 1 és 2 egység hosszúságú járdalapokkal? És ha 1, 2 és 3 egység méretű lapjaink is vannak? És ha paraméterként kapjuk, hogy mekkora lapjaink vannak?
Írj függvényt, amelyik jarda(hossz, [lapok, méretei, ...]) formában hívható, és megadja a kérdésre a választ! (A
feladat egyszerűbb változata laboron szerepelt: csak a megoldások darabszámát
kell kiírni.)
Járda kövezése II.
Hányféleppen lehet egy adott hosszúságú járdát kikövezni 1 és 2 méter hosszúságú járdalapokkal? Például ha 3 méteres a járda, a lehetőségek: 1+1+1, 1+2, 2+1, tehát összesen 3. Listázzuk ki az összes megoldási lehetőséget! (A feladat egyszerűbb változata: csak a megoldások darabszámát kell kiírni.)
Pénzváltás I.
Adott egy zsák 5, 10, 20 és 50 forintos érménk. Hányféleképpen lehet ezekkel kifizetni 100 forintot?
Pénzváltás II.
Adott egy zsák 5, 10, 20 és 50 forintos érménk. Hányféleképpen lehet ezekkel kifizetni 100 forintot? Listázzuk ki az összes megoldási lehetőséget!
Tipp
Ehhez azt kell észrevennünk, hogy a mennyit==0 báziskritérium jelenti azt, hogy megtaláltunk egy
megoldást. Mire oda eljutunk a rekurzióban, már valamilyen érmekombinációval megoldottuk a feladatot. Ha útközben feljegyezzük az
érmék számát egy segédlistában, akkor ezen a ponton kiírva a lista tartalmát, meg tudjuk adni a megoldásokat. (A második, harmadik
báziskritérium olyan próbálkozást jelent, ami nem vezetett megoldásra.) A darab[] segédlistában egy adott indexű elem
azt tárolja, hogy az ugyanannyiadik indexű fajtak[] érméből mennyit adunk.
Kérdés még, hogy hol változik a lista tartalma. A mennyit-fajtak[hanyadiktol] paraméterű rekurzív hívásnál
próbálkozunk egy érme kiadásával. Ezért a rekurzív hívás előtt a megfelelő darabszámot megnöveljük eggyel (hogy a hívásban
a darabszám lista már megfelelő tartalmú legyen, és azt írjuk ki), és a hívás után pedig csökkentjük.
Faktoriális – a kiértékelés megjelenítése
A rekurzív faktoriális függvény (n*(n-1)!) kiértékelését egy ilyen rajzzal lehet szemléltetni:
fakt(3)
fakt(2)
fakt(1)
fakt(0)
1
1*1
1
2*1
2
3*2
6
Módosítsd úgy a rekurzív faktoriális függvényt (maradjon is rekurzív), hogy egy ehhez hasonló rajzot készítsen a program kimenetén!
Bemenet megfordítása
Írj rekurziót használó programot, amely beolvassa a szabványos bemenetén érkező számokat, és az eredetihez képest visszafelé sorrendben írja ki azt! A program ne használjon listákat!
Sierpiński-háromszög
Rajzolj Sierpiński-háromszöget teknőcgrafikával! Az ábra tanulmányozása után észre fogod venni, hogy ez rekurzióval könnyedén megoldható feladat.
Fa
Egy fa törzse h hosszúságú. Ebből két ág nő ki, amelyek hossza az eredeti h hossz kétharmad része.
Egymáshoz képest 120 fokban hajlanak meg, a törzshöz képest pedig szimmetrikusan. Az ágakból – mintha maguk is törzsek lennének –
még rövidebb ágak nőnek ki.
Írj rekurzív függvényt, amely paraméterként a törzs hosszát, és a „szintek” számát kapja, majd kirajzolja a fát!
Kísérletezz más szögekkel, színekkel, esetleg véletlenszerűséggel! Ötleteket a fractal tree kifejezésre keresve kapsz.