Programozási stratégiák

Rekurzió

Rekurzív humor:

  • rekurzió: ld.rekurzió
  • Ahhoz, hogy megértsük a rekurziót, először meg kell értenünk a rekurziót.

Rekurzív rövidítések:

  • GNU: GNU's not Unix,
  • PHP: PHP Hypertext Preprocessor,
  • WINE: WINE Is Not an Emulator,
  • TikZ: TikZ is kein Zeichenprogramm.

Példák:

  • Hanoi tornyai
  • Fibonacci számok
  • Pascal háromszög (binomiális együtthatók)

Dinamikus programozás

Dinamikus programozás: egy probléma megoldása úgy, hogy

  1. rekurzív módon visszavezetjük egyszerűbb, kisebb méretű, azonos típusú problémák megoldására,
  2. de a rekurzió elkerülésére, minimalizálására memóriatáblát használunk.

Fibonacci-sorozat

A Fibonacci-sorozat egy rekurzív módon definiált sorozat. Két programot írunk elemeinek kiszámítására.

A programok futási idejének mérésére a time modul time.time() függvényét használjuk, mely az aktuális időt adja vissza, tehát ha a program futása előtt és után is meghívjuk, akkor megkapjuk a köztük eltelt időt a kettő különbségeként.

A recursive_fib.counter a recursive_fib-nak mint függvényobjektumnak a tagváltozója fogja számolni a rekurzív függvény meghívásainak számát. Minden egyes híváskor megnöveljük a változót, azaz megszámoljuk vele a függvényhívások számát. Ezt itt globálisan kezelt változóval tudjuk megvalósítani.

Rekurzív megoldás

In [1]:
import time

def recursive_fib(n):
    recursive_fib.counter += 1
    if n <= 1:
        return n
    else:
        return recursive_fib(n-1) + recursive_fib(n-2)

recursive_fib.counter = 0
start = time.time()
print(recursive_fib(33))
print(time.time() - start)
print(recursive_fib.counter)

3524578
4.043430805206299
11405773

Ez így rettenetesen lassú, a függvény meghívásainak száma hatalmas (a századik Fibonacci-számot ki sem próbáljuk számolni). E rekurzív függvényhívások megkerülhetők, ha egy táblázatban őrizzük az eddig kiszámolt Fibonacci-számokat, ezt akkor használjuk, ha e függvényt sokszor kell meghívni, hasznos lehet az eddig kiszámolt értékeket tárolni.

Iteratív megoldás

In [2]:
import time

def dp_fib1(n):
    f = [0, 1]
    for i in range(n-1):
        f.append(f[-2]+f[-1])
    return f[-1]

print(dp_fib1(1000))
start = time.time()
dp_fib1(1000)
print(time.time() - start)

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
0.00052642822265625
In [3]:
start = time.time()
for i in range(100):
    dp_fib1(1000)
print((time.time() - start)/100)

0.0004088902473449707

De van még hatékonyabb megoldás, ha csak az utolsó két értéket tároljuk.

In [4]:
import time

def dp_fib2(n):
    f = [0, 1]
    for i in range(n-1):
        f = [f[1], f[0] + f[1]]
    return f[1]

print(dp_fib2(1000))

start = time.time()
for i in range(100):
    dp_fib2(1000)
print((time.time() - start)/100)

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
0.0003501319885253906

Hanoi tornyai

Feladat: három pálca egyikére $n$ különböző sugarú korong van fölfűzve, minden korong alatt csak nagyobb sugarú lehet. Ez utóbbi feltételt megtartva tegyük át a korongokat egyesével egy másik pálcára! (animáció a tutorialspoint.com)

Tower Of Hanoi

Rekurzív megoldás: Ha az 1-es pálcáról akarunk $n$ korongot a $2$-esre rakni, akkor tegyünk át $n-1$-et a 3-asra, az $n$-ediket a 2-esre, majd a 3-asról $n-1$-et a 2-esre.

Ez az a példa, amikor rekurzív megoldás nagyon könnyű beprogramozni, de egy hatékonyabb iteratívat nem. (A lépésszámon nem is lehet spórolni, de a memóriahasználaton igen.)

Rekurzív megoldás

In [5]:
def hanoi(n, from_, to_, third_):
    if n > 0:
        hanoi(n-1, from_, third_, to_)
        print("disk no. {0}: {1} ==> {2}".format(
            n, from_, to_))
        hanoi(n-1, third_, to_, from_)
In [6]:
hanoi(3, "A", "B", "C")

disk no. 1: A ==> B
disk no. 2: A ==> C
disk no. 1: B ==> C
disk no. 3: A ==> B
disk no. 1: C ==> A
disk no. 2: C ==> B
disk no. 1: A ==> B
In [7]:
hanoi(2, "A", "B", "C")

disk no. 1: A ==> C
disk no. 2: A ==> B
disk no. 1: C ==> B
In [8]:
hanoi(1, 1, 2, 3)

disk no. 1: 1 ==> 2

Egy nem rekurzív, hatékonyabb megoldás megkeresése nehezebb feladat, kihagyjuk.

Pénzváltás

Feladat: adott pénzérmékből mennyi a minimális számú, amellyel egy adott összeg kifizethető. (Tegyük fel, hogy egy automatát úgy állítunk be, hogy a visszajáró pénzt mindig a legkevesebb érmével fizesse ki. Feltesszük, hogy minden érméből rendelkezésre áll annyi, amennyi kellhet, és hogy az összeg és minden érme értéke egész szám.)

A mohó algoritmus (greedy) első pillanatra jónak tűnik: ha az érmék listája [1, 5, 10, 20, 50], akkor bármely összeg kifizetéséhez szükséges érmék megkaphatók úgy, hogy mindig a legnagyobb címletűvel annyit kifizetünk, amennyit tudunk, majd a maradékkal folytatjuk ezt, amíg a teljes összeget ki nem fizettük, vagy olyan maradékot nem kapunk, amely kisebb értékű minden rendelkezésre álló érménél.

Viszont ez az algoritmus megbukik, ha 8 talléros érméket is veretünk: [1, 5, 8, 10, 20] érmelistával 24 tallér kifizetése esetén a mohó algoritmus 5 érmét ad, de 3 db 8-talléros érmével is lehetséges. Rekurzív megoldást keresünk.

Rekurzív program

A rekurzív pénzváltó program (r_exchange) a felváltandó összeget kapja argumentumként.

Figyeljük meg, hogy az r_exchange.counter változót globálisként kezeljük.

In [9]:
import time

def r_exchange(money):
    coins.sort()
    r_exchange.counter += 1
    min_coins = float('inf')
    if money in coins:
        return 1
    else:
        for coin in coins:
            if coin > money:
                break
            number_of_coins = 1 + r_exchange(money - coin)
            if number_of_coins < min_coins:
                min_coins = number_of_coins
    return min_coins
In [10]:
r_exchange.counter = 0
coins = [1, 2, 5, 10, 20]
start = time.time()
print(r_exchange(34))
print(time.time() - start)
print(r_exchange.counter)

4
4.248380184173584
4399137
In [11]:
r_exchange.counter = 0
coins = [1, 5, 8, 10, 20]
start = time.time()
print(r_exchange(24))
print(time.time() - start)
print(r_exchange.counter)

3
0.003545522689819336
800

E program igen lassú, nagyobb összegekre kivárhatatlan a sok függvényhívás miatt.

Dinamikus program

Írjunk dinamikus programot, mely szisztematikusan végigmegy az összes lehetséges összegen 1-től a felváltandó összegig, és mindegyikre megadja az érmék minimális számát. Ezeket egy táblázatban tárolja, hogy később szükség esetén fölhasználhassa. A rekurzív gondolat itt is az, hogy ha valamekkora érték alatt már minden felváltandó összegre tudjuk az érmék minimális számát, akkor minden szóba jöhető érme értékét levonva belőle, kiválasztjuk a megmaradó összegek közül azt, amelyik a legkevesebb érmével fizethető, majd ehhez 1-et adunk. Konkrétan, ha pl. az érmék listája [1, 5, 10] és az összeg 24 tallér, akkor az utolsó lépésben a következő számítást kell végezni: $$\texttt{min_coins}=1+\min\left\{\begin{array}{l}\texttt{memory_table}[24 - 1]\\\texttt{memory_table}[24 - 5]\\\texttt{memory_table}[24 - 10]\end{array}\right\}$$ A programban a táblázatot itt is globálisnak deklaráltuk.

In [12]:
def dynamic_exchange(money):
    global memory_table
    memory_table = [0]*(money+1)
    coins.sort()
    for t in range(1, money+1):
        min_coins = float('inf')
        for coin in coins:
            if coin > t:
                break
            if memory_table[t-coin] + 1 < min_coins:
                min_coins = memory_table[t-coin] + 1
        memory_table[t] = min_coins

    return memory_table[money]
In [13]:
coins = [1, 2, 5, 10, 20]
start = time.time()
print(dynamic_exchange(34))
print(time.time() - start)

4
0.0007157325744628906
In [14]:
print(memory_table)

[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 1, 2, 2, 3, 3, 2, 3, 3, 4, 4, 2, 3, 3, 4, 4]
In [15]:
coins = [1, 5, 8, 10, 20]
start = time.time()
print(dynamic_exchange(24))
print(time.time() - start)

3
0.001100778579711914
In [16]:
print(memory_table)

[0, 1, 2, 3, 4, 1, 2, 3, 1, 2, 1, 2, 3, 2, 3, 2, 2, 3, 2, 3, 1, 2, 3, 3, 3]
In [17]:
coins = [5, 10, 20, 50]
start = time.time()
print(dynamic_exchange(24))
print(time.time() - start)

inf
0.00556635856628418
In [18]:
print(memory_table)

[0, inf, inf, inf, inf, 1, inf, inf, inf, inf, 1, inf, inf, inf, inf, 2, inf, inf, inf, inf, 1, inf, inf, inf, inf]

Partíciók

Feladat: Hányféleképp bontható fel egy pozitív egész szám pozitív egészek összegére, ha az összeadandók sorrendje számít? Adjunk rekurzív és dinamikus megoldást!

In [19]:
def sums(n):
    if n == 0:
        return [[]]
    else:
        sumlist = []
        for i in range(1, n+1):
            L = [i]
            for l in sums(n-i):
                sumlist.append(L + l)
    return sumlist

n = 4
print(("Az {0} összesen {1}-féleképp bontható fel.".
       format(n, len(sums(n)))))
for s in sums(n):
    print((" + ".join(str(x) for x in s)))

Az 4 összesen 8-féleképp bontható fel.
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
1 + 3
2 + 1 + 1
2 + 2
3 + 1
4
In [20]:
def sums_d(n):
    global memory_table
    memory_table = [[[]]]
    if n == 0:
        return memory_table[n]
    for i in range(1, n+1):
        sumlist = [[i]]
        for j in range(1, i):
            for l in memory_table[i - j]:
                sumlist.append([j] + l)
        memory_table.append(sumlist)
    return memory_table[n]
In [21]:
for s in sums_d(n):
    print(" + ".join(str(x) for x in s))

4
1 + 3
1 + 1 + 2
1 + 1 + 1 + 1
1 + 2 + 1
2 + 2
2 + 1 + 1
3 + 1
In [22]:
print(memory_table)

[[[]], [[1]], [[2], [1, 1]], [[3], [1, 2], [1, 1, 1], [2, 1]], [[4], [1, 3], [1, 1, 2], [1, 1, 1, 1], [1, 2, 1], [2, 2], [2, 1, 1], [3, 1]]]

Állapotgépek

Digráfok

Egy klasszikus probléma: olvassunk be egy szöveget karakterenként, majd számoljuk meg benne az ly betűket. Figyelembe kell vennünk a dupla, lly betűt is, pl. a gally szóban.

Megoldás. Definiálunk egy s állapotot, ami alaphelyzetben 0, viselkedése pedig a következő. Ha

  • a következő betű l és s=0, akkor s=1;
  • a következő betű l és s=1, akkor s=2;
  • a következő betű y és s=1 vagy s=2, akkor megjegyezzük, hogy találtunk egyet és s=0;
  • minden egyéb esetben s=0
In [23]:
def ly(sample):
    s = 0
    counter = [0, 0]
    for i in sample:
        if i == 'l':
            if s <= 1:
                s += 1
        elif i == 'y':
            if s == 1:
                counter[0] += 1
            elif s == 2:
                counter[1] += 1
            s = 0
        else:
            s = 0
    return counter
In [24]:
sample = "gally lyuk alma xylofon folyam"
lys = ly(sample)
print("{0} ly és {1} lly".format(lys[0], lys[1]))

2 ly és 1 lly

Az állapotgép gyakorlatilag egy véges automata, legalábbis a matematikusok így hívják. A gép következő állapota függ az aktuális állapottól (s) és a bemenettől (ez a következő betű).

Alapvetően állapotgépeket szövegfelismerésre használnak. Írjunk programot a sztringekben az escape karakterek felismerésére, kiírására és megszámolására!

In [25]:
def escape(sample):
    s = 0
    counter = 0    
    for i in sample:
        if i == "\\":
            if s == 0:
                s = 1
            else:
                print("\\", end=" ")
                counter += 1
                s = 0
        elif i in 'nt"\'':
            if s == 1:
                s = 0
                print(i, end=" ")
                counter += 1
        else:
            s = 0
    print()
    return counter
In [26]:
sample = r"\"Hello\"\nbackslash: \\not a new line"
print((escape(sample)))

" " n \ 
4

Zárójelezés

Számoljuk meg, hogy hány zárójel van egy képletben. Az s számláló legyen 0, ha nyitó zárójelet találunk, akkor növeljük, ha csukót, akkor csökkentsük, egyébként maradjon változatlan.

Ha ez a szám bármikor is negatív, akkor rosszul van a szöveg zárójelezve, illetve akkor is ha a képlet végén nem 0 ez a szám.

In [ ]: