8. hét: rendezések, rekurzió

Czirkos Zoltán · 2019.11.07.

Gyakorlófeladatok az előadás anyagához kapcsolódóan.

1. Keresések, rendezések

Számkitaláló

Készíts egy számkitaláló programot! A program kitalál véletlenszerűen egy pozitív egész számot (1 és 1000 között), a felhasználó pedig addig tippel, amíg meg nem találja a keresett számot. A program minden tipp után megmondja, hogy a felhasználó tippje kisebb vagy nagyobb a keresett értéknél. Ha eltalálta, akkor pedig azt. Ilyenkor egyúttal be is fejeződik a program futása.

Vajon mi a nyerő stratégia a gép „ellen”? Hogyan lehet legkevesebb tippből kitalálni a számot, amire a gép gondolt?

Megoldás

A nyerő stratégia: intervallumfelezés, azaz bináris keresés. 500, aztán 250 vagy 750, és így tovább.

import random

gondolt = random.randint(1, 10)
print("Gondoltam egy számra.")

talalt = False
while not talalt:
    tipp = int(input("Mondd a tipped! "))
    if tipp == gondolt:
        print("Eltaláltad! A gondolt szám a {}.".format(gondolt))
        talalt = True
    elif tipp < gondolt:
        print("Nagyobbra gondoltam.")
    elif tipp > gondolt:
        print("Kisebbre gondoltam.")

Számkitaláló fordítva

A felhasználó gondol egy számra 1 és 100 között, a gép pedig megpróbálja kitalálni. Például: „kisebb a szám, mint 25?”, erre a felhasználó „i”gen vagy „n”em választ ad. Mi a nyerő stratégia a gép részéről, hogy tudja a legkevesebb kérdésből kitalálni? Valósítsa meg a programot!

Gondolkodtató: ha a gép a nyerő stratégiát alkalmazza, meg tudja-e mondani, ha a felhasználó következetlen választ ad, csalni próbál? Miért?

Megoldás

Itt az előző feladat nyerő stratégiáját kell megvalósítani programban, a bináris keresést. Nem tudja megmondani a gép, ha a felhasználó csalni próbál, mivel a kérdésekben és válaszokban (azaz a program által kapott információban) nincsen redundancia. Vagyis nincsenek olyan kérdések, amikre ellentmondó válaszokat kaphatna, hogy ezek alapján észrevegye a csalást.

min = 0
max = 100

while (max - min) > 1:
    tipp = (min + max) // 2
    kerdes = "Kisebbre gondoltál mint {0} ? (i/n)".format(tipp)
    if input(kerdes) == "i":
        max = tipp - 1
    else:
        min = tipp
print("Erre gondoltál?", min, "(i/n)", end="")
if input() == "i":
    print("A gondolt szám:", min)
else:
    print("A gondolt szám:", max)

Javított buborékrendezés

A buborékrendezés egymás melletti elemeket cserél sorban. Egy sor csere hatására a legnagyobb elem a lista végére vándorol; a következő körben azt már nem kell vizsgálni, hanem a lista eggyel rövidebb részletét csak. Ezt kell folytatni addig, amíg el nem fogy a lista.

A buborékrendezés hatékonysága javítható azzal, ha megjegyezzük, hogy a vizsgált listarészletnél volt-e csere. Ha nem volt, akkor minden pár jó sorrendben van. Akkor a rövidebb részt vizsgálva is ugyanerre az eredményre jutnánk, vagyis a külső ciklust már nem kell folytatni. Implementáld ezt a változatot!

Lineáris és bináris keresés

Töltsünk fel egy nagy listát véletlenszámokkal. Rendezzük a listát. Válasszunk egy elemet a lista értékkészletéből, és keressük meg, hogy a rendezett lista mely tartományában szerepel (hányadiktól hányadik indexig). Tegyük ezt a keresést a lehető leggyorsabban!

Tipp

A rendezett listán végezhetünk bináris keresést. A bináris keresés egy indexszel fog visszatérni, amelyik az adott szám EGY találatára fog mutatni. Ettől balra is, és jobbra is lehetnek még elemek, például a lista részlete lehet: 1 2 2 3 3 [3] 3 4 4 5 6, ahol a jelölt elem a bináris keresés által megtalált. A bináris keresés után a tartomány két szélét lineárisan kell megkeresnünk.

A három legkisebb

Írjunk programot, amelyik egy listából kiírja a három legkisebb elemet.

Tipp

Ehhez praktikus a közvetlen kiválasztásos rendezést alkalmazni. A közvetlen kiválasztásos eljárás lényege, hogy megkeresi a legkisebb elemet, és azt a lista elejére rakja; utána a fennmaradó listarészletre megcsinálja ugyanezt. Így a második lépésben a lista második helyére a második legkisebb eleme kerül, a harmadikban a harmadik legkisebb.

Mivel nekünk csak az első három legkisebb kell, itt le is állíthatjuk az algoritmust, nem futtatva azt az egészen lista végéig. Így mindössze három csere után meg tudjuk adni a választ.

Medián

Írj függvényt, amely átvesz egy számokból álló listát, és visszaadja a medián elemét! A medián az az elem, amelynél annyi kisebb van a tömbben, ahány nagyobb. Felteheted, hogy a tömbben páratlan sok elem van, és nincs két egyforma. Tetszőlegesen használhatsz segédfüggvényeket, de az eredeti listát nem változtathatod meg!

Megoldás

A mediánról a gyorsrendezés (qsort) kapcsán volt szó előadáson, de a definíciója kiderül a feladat szövegéből is. Ha egy rendezett listát nézünk, annak a medián pont a középső eleme; hiszen a rendezett sorban pont ugyanannyi van a középsőtől balra (nála kisebbek), mint tőle jobbra (nála nagyobbak.) Vagyis nincs más dolog, mint visszatérni a középső elemmel. A probléma már csak annyi, hogy az eredeti listát nem változtathatjuk meg egy rendezéssel. Tehát vagy lemásoljuk, és azt rendezzük, vagy egyszerűen a sorted() függvényt hívjuk, amelyik amúgy is másolatot ad.

Dicsőséglista

Játékot kell írni, amely egy maximum 20 nevet tároló dicsőséglistát vezet. A maximum 100 karakteres nevek mindegyikéhez egy egész pontszám tartozik. Írd meg a következő függvényeket:
1. függvény: eldönti egy adott pontszámról, hogy felkerül-e a listára. Igaz/hamis értékkel tér vissza.
2. függvény: kiírja a képernyőre a dicsőséglistát.
3. függvény: felvesz egy új bejegyzést (név, pontszám) a listára, és visszatér a helyezéssel. (-1, ha nem került fel a listára.) A legkisebb pontszámú bejegyzés ilyenkor törlődik.

Negatívak indexei

A tanórákon szerepelt egy olyan feladat, amelyben egy listából ki kellett válogatni a negatív számokat, és az indexeiket egy másik listába másolni. Az indexek alapján a negatív számok könnyen visszakereshetőek, mert tudni lehet, milyen sorszámokon szerepelnek az eredeti listában negatív számok:

Összesen 10 szám van.
[0]=2.5 [1]=-69 [2]=5.4 [3]=-8 [4]=-7.7 [5]=6 [6]=2.9 [7]=-10 [8]=-3 [9]=9.8 

Ebből 5 szám negatív.
[1]=-69 [3]=-8 [4]=-7.7 [7]=-10 [8]=-3 

A feladat most látszólag ugyanez, de fordítva: adott egy lista, néhány negatív számmal, és adott a másik lista, amely a negatív elemek indexeit tartalmazza. De nem a negatív számokat kell kilistázni az indexek listáját felhasználva, hanem pont azokat, amelyek nem negatívak.

A megoldáshoz ne az eredeti listában keress, hanem használd föl a negatívak ismert indexeit! Általánosságban: adott egy lista, valamilyen adatokkal, és adott mellé egy másik lista, amely az előzőbe mutató indexeket tartalmaz. Azokat az elemeket kell kilistázni, amelyeket nem hivatkozik meg az indexelő lista.

Meg lehet ezt a feladatot O(n²) időben oldani? És meg lehet O(n) időben oldani? Ha igen, mi a feltétele?

Megoldás

A triviális megoldás az alábbi. Ez O(n²) időben fut, mivel minden indexre: O(n) elvégez egy keresést: O(n).

for i = eredeti_tömb indexei...
    if !benne_van(indexek_tömbje, i):
        kiír: eredeti_tömb[i]

Ha tudjuk, hogy az indexek tömbjében a sorszámok növekvő sorrendben vannak, akkor O(n) időben is megoldható a feladat. Mindig az egymás melletti számokat kell nézni, és a köztük lévő elemeket listázni. Például ha az indexelő tömbben 4 és 7 szerepel egymás mellett, akkor tudni lehet, hogy az 5-ös és 6-os elem volt nemnegatív.

Rendezés és funkcionális dekompozíció

Írj függvényt, amely képes megcserélni a paraméterként kapott listában két elemet – azokat, amelyeknek indexeit szintén paraméterként kapja!

Írj függvényt, amely paraméterként egy valós számokat tartalmazó listát vesz át, továbbá két indexet, amelyek egy tartomány elejét és végét határozzák meg! Térjen vissza a függvény a megadott tartományból a legkisebb elem indexével!

Írj függvényt, amely paraméterként egy listát vesz át, és az előbbi két függvényt is felhasználva növekvő sorba rendezi a lista számait!

Egészítsd ki ezeket egy főprogrammal, amely létrehoz egy 5 elemű listát, rendezi azt, majd kiírja az elemeket sorszámozva!

2. Rekurzió

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árázott é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!

Megoldás

A négyből két feladat megoldása: iteratív sorozatkiírás és rekurzív hány-lépés-az-egyig. Az osztásoknál // egész osztást kell használni, hogy ne float típusú eredményt kapjunk.

def main():
    a = int(input("a = "))
    
    print(a, end=" ")
    while a != 1:
        if a % 2 == 0:
            a //= 2
        else:
            a = 3*a + 1
        print(a, end=" ")
    
main()
def collatz_hanyadikra_1(a, n):
    # ha elértük az 1-et. n-ben számoltuk a lépéseket
    if a == 1:
        return n
    
    if a % 2 == 0:
        return collatz_hanyadikra_1(a // 2, n + 1)
    else:
        return collatz_hanyadikra_1(3*a + 1, n + 1)

def main():
    a = int(input("a = "))
    print(collatz_hanyadikra_1(a, 0), "lépés után lesz 1.")
    
main()

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ét dimenzió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!

Megoldás

Rekurzív megoldás. Írjunk először egy függvényt, amelyik egy sztringet kap paraméterként, és egy kezdő pozíciót. Térjen vissza a függvény azzal az indexszel, ahol először bezáró zárójelet talál. Ez könnyű, egyszerűen csak egy ciklust kell futtatnunk addig, amíg meg nem lesz a keresett karakter:

FÜGGVÉNY bezárót_keres(sztring, pozíció)
    AMÍG sztring[pozíció] != ')'
        pozíció=pozíció+1
    CIKLUS VÉGE

    VISSZA: pozíció
FÜGGVÉNY VÉGE

De ez még nem tudja a zárójelek egymásba ágyazását. Mit kell tenni, ha a bezárójel keresése közben egy nyitó zárójelet találunk? Akkor a következő bezárójel még nem az lesz, amit keresünk, hanem a mostani nyitónak a párja. Ez a belső zárójelpár közrefog egy sztringrészletet, amit át kéne ugranunk a keresés közben:

eredeti nyitó az elején          ezt a bezárót keressük
↓                                ↓
(A zárójelek (egymásba lehetnek) ) ágyazva.
             ↑                 ↑
             ezt a részt ki kell hagyni, mintha ott sem lenne

Hogy találjuk meg, hogy hol van ennek a nyitó zárójelnek a párja? Nagyon egyszerűen, hiszen már az előbb megírtuk azt a függvényt, ami ezt tudja! Ott van fent a pszeudokódja. Azt kiegészítve kapjuk a lenti függvényt. Az első utasítás a pozíció növelése; azzal az első nyitó zárójelet egyből átugorja.

FÜGGVÉNY bezárót_keres(sztring, pozíció)
    pozíció=pozíció+1
    CIKLUS AMÍG sztring[pozíció] != ')'
        FELTÉTEL HA sztring[pozíció] == '('
            pozíció = bezárót_keres(sztring, pozíció)
        FELTÉTEL VÉGE

        pozíció=pozíció+1
    CIKLUS VÉGE

    VISSZA: pozíció
FÜGGVÉNY VÉGE

Iteratív megoldás. Minden rekurzív problémának létezik iteratív megoldása. Ennek például nagyon egyszerű. Ha a keresés közben találunk egy nyitó zárójelet, akkor eggyel több bezáró zárójelig kell futtatni a keresést:

A (zárójelek (egymásba () lehetnek) ) ágyazva.
0011111111111222222222233222222222211000000000

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.)

Megoldás

A megoldás elve ugyanaz, mint a labor hasonló feladatánál. Megpróbálunk egy 1-es lappal indulni, és akkor hossz-1-et kell már csak kirakni. Megpróbálunk 2-es lappal is indulni, akkor pedig hossz-2 úthossz marad, amit ki kell majd rakni. A különbség az, hogy itt most a hosszakat egy listában kaptuk, tehát az összegzést egy ciklusban végezzük, minden lehetséges lapméretet végigpróbálva.

Fontos, hogy itt olyan báziskritériumnak a 0 hosszú és a negatív hosszú járdát vegyük: 0 hosszú járdára 1 megoldás van (nem kell lap), negatív hosszú járdára 0 megoldás (nem létezik negatív járda). Ezek azok a báziskritériumok, amelyek a hosszaktól függetlenek. A laborfeladatnál a tipp az 1-es és a 2-es hosszhoz kért báziskritériumot: azok könnyebben érthetőek elsőre, de a lapok hosszaitól függenek. Itt viszont ezt nem tudjuk előre, hanem paraméter.

def jarda(hossz, lapok):
    if hossz < 0:
        return 0
    if hossz == 0:
        return 1
    lehetosegek = 0
    for laphossz in lapok:
        lehetosegek += jarda(hossz - laphossz, lapok)
    return lehetosegek

def main():
    print("10 méter, [1, 2] lapokkal:", jarda(10, [1, 2]))
    print("10 méter, [1, 2, 3] lapokkal:", jarda(10, [1, 2, 3]))

main()

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.)

Megoldás

Abból a megoldásból érdemes kiindulni, ahol a báziskritériumnak a 0 hosszú és a negatív hosszú járdát vettük. Ez így nézett ki:

def jarda(hossz):
    if hossz < 0:
        return 0    # lehetetlen
    if hossz == 0:
        return 1    # nem csinálunk semmit
    
    return jarda(hossz - 1) + jarda(hossz - 2)

Azt kell észrevenni, hogy a hossz == 0 báziskritérium mutatja azt, mikor találtunk épp egy megoldást. Ha negatív hosszhoz jutunk, az azt jelenti, hogy az eddig lerakott lapok túlmentek a kért hosszon, vagyis nem volt jó a kísérlet. A 0 hossz viszont azt, hogy épp olyan sorrendben raktuk az 1, 2 hosszú lapokat, hogy kiadták az eredetileg kért hosszt.

Már csak azt kellene tudni ezen a ponton, hogy hogyan jutottunk el ide. Bevezetünk ehhez egy második paramétert a függvényben a hossz mellé. Ez egy lista lesz az eddig rakott lapok hosszával. Amikor épp megoldáshoz érünk, akkor a lista tartalmazza az „oda vezető utat”, tehát csak ki kell írni az. A függvény indításához egy üres listát adunk paraméterként:

def jarda(hossz, eddigiek):
    if hossz < 0:   # nem vezetett megoldáshoz
        return

    if hossz == 0:  # megoldáshoz vezetett
        print(*eddigiek, sep=" + ")    
        return

    jarda(hossz - 1, eddigiek + [1])
    jarda(hossz - 2, eddigiek + [2])


def main():
    jarda(5, [])

main()
1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 2
1 + 1 + 2 + 1
1 + 2 + 1 + 1
1 + 2 + 2
2 + 1 + 1 + 1
2 + 1 + 2
2 + 2 + 1

A függvényben ilyenkor a megoldások számát összegezni nem kell már, hiszen most nem az volt a feladat.

Észrevehetjük, hogy ilyenkor a lerakott lapok listáját ismerve, az abban lévő hosszakat összegezve is tudjuk, hogy hol tartunk épp. Ezért megoldhatjuk a feladatot úgy is, hogy a hossz paramétert nem csökkentjük, hanem a báziskritériumok ellenőrzéséhez a lapok hosszait összegezzük:

def jarda(hossz, eddigiek):
    if sum(eddigiek) > hossz:   # túlmentünk
        return
    
    if sum(eddigiek) == hossz:  # épp eltaláltuk, ez amegoldás
        print(*eddigiek, sep=" + ")
        return
    
    jarda(hossz, eddigiek + [1])
    jarda(hossz, eddigiek + [2])

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?

Megoldás

A probléma könnyen megoldható rekurzívan. Tekintsünk pl. egy 20 forintost! Két lehetőségünk van: ha a 20 forintos része a megoldásnak (vagyis adunk egy 20-ast), akkor a maradék 100-20=80 forintot még valahányféleképpen (x) ki lehet fizetni. A másik lehetőség, ha azt mondjuk, hogy nem adunk 20-ast, és a 100 forint kifizetését a többi érmével oldjuk meg (y lehetőség). A megoldás ezek összege: x+y.

Így közeledünk a rekurzióban a báziskritérium felé: vagy az összeg csökken, vagy a felhasználható érmefajták fogynak. Figyelembe kell még vennünk három extrém esetet. Ezek lesznek a báziskritériumok:

  1. Ha 0 forintot kell kifizetnünk, azt egyféleképpen tehetjük: nem adunk pénzt.
  2. Ha 0-nál többet kell fizetnünk, de nincs semmilyen fajta érménk, akkor nulla lehetőség.
  3. Ha negatív összeget kell fizetnünk, azt sem tudjuk megtenni: nulla lehetőség.

Az utóbbi feltételt az algoritmus egyszerűségéhez használjuk ki. Jelentése: ha 5 forintot kell kifizetni, és megpróbáljuk egy 20-assal, akkor még -15 forintot kellene – de ez nem megoldás.

def penzvalto(mennyit, cimletek):
    """
    mennyit: int, hány forintot kell fizetni.
    fajták: lista, mik a rendelkezésre álló címletek.
    """
    if mennyit == 0:    # 1. pont
        return 1
    if cimletek == [] or mennyit < 0: # 2. és 3. pont
        return 0
    
    return penzvalto(mennyit - cimletek[0], cimletek) + penzvalto(mennyit, cimletek[1:])


def main():
    cimletek = [5, 10, 20, 50]
    lehetosegek = penzvalto(100, cimletek)
    print("Összesen: {} lehetőség".format(lehetosegek))

main()

Az érmék névértékeit egy tömbbe tettük, amely egy lezáró -1-et is tartalmaz (a római számos példákhoz hasonlóan). A függvény ezt a tömböt kapja, és egy indexet, hogy hányadik elemtől kell a tömböt figyelembe vegye. Az utolsó sorában ezt növeli, és úgy hívja meg magát – így maradnak ki a tömb eleji érmék a rekurzív hívásban, és így fogy el végül a tömb, amikor fajtak[hanyadiktol]==-1. Ez megoldható lenne pointer aritmetikával is: fajtak+1 a tömb belsejébe mutat (a hátsó részére), és így fogyhat el a tömb.

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.

Sierpiński-háromszög