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

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

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)

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.

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.

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.

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.

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

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

Használj rekurziót! Ez olyan, mintha ezres számrendszerben írnál ki.

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

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

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.

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.