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:

  • Fibonacci számok
  • Euklideszi algoritmus
  • Hanoi tornyai
  • Pascal háromszög (binomiális együtthatók)
  • Partíció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: $F_0=0$, $F_1=1$ és $F_n=F_{n-1}+F_{n-2}$. 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 rekurzív recursive_fib függvényobjektum tagváltozójaként 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()
f = recursive_fib(33)
print(time.time() - start)
print(f"F_33 = {f}, counter = {recursive_fib.counter}")

3.9937119483947754
F_33 = 3524578, counter = 11405773
In [2]:
recursive_fib.counter = 0
f = recursive_fib(5)
print(f"F_5 = {f}, counter = {recursive_fib.counter}")

F_5 = 5, counter = 15

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). Például fib(5) kiszámításához a következő 15 függvényhívás kell:

                           fib(5)   
                     /               \
               fib(4)                 fib(3)   
             /        \               /     \ 
        fib(3)        fib(2)        fib(2) fib(1)
       /      \      /      \      /      \
    fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
   /      \
fib(1) fib(0)

Az értékeket megadva:

                          5  
                     /          \
               3                      2   
            /     \                /     \ 
         2           1           1         1
       /   \       /   \       /   \
      1     1     1     0     1     0
   /     \
  1       0

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.

Dinamikus (iteratív) megoldás

In [3]:
import time

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

start = time.time()
f = dynamic_fib1(1000)
print(time.time() - start)
print(f"F_1000 = {f}")

0.0005877017974853516
F_1000 = 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
In [4]:
start = time.time()
for i in range(100):
    dynamic_fib1(1000)
print((time.time() - start)/100)

0.00033469438552856444

De van még hatékonyabb megoldás, ha csak az utolsó két értéket tároljuk, és így listakezelésre sincs szükség:

In [5]:
import time

def dynamic_fib2(n):
    f0, f1 = 0, 1
    for i in range(n-1):
        f0, f1 = f1, f0 + f1
    return f1

print(dynamic_fib2(1000))

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

43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
0.00014218568801879883

Euklideszi algoritmus

A két megoldás lényegében azonos: ugyanannak a lépésnek az ismétlését egyszer rekurzív függvényhívásokkal, egyszer ciklussal valósítjuk meg. A dinamikus megoldásban itt is elég csak két értéket tárolni. A paraméterek nemnegatív egészek:

In [6]:
def r_gcd(a, b):
    if b == 0:
        return a
    else:
        return r_gcd(b, a%b)

r_gcd(110, 242)
Out[6]:
22
In [7]:
def d_gcd(a, b):
    while b:
        a, b = b, a%b
    return a

d_gcd(110, 242)
Out[7]:
22

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

A from kulcsszó, így helyette a from_ változónevet használjuk:

In [8]:
def hanoi(n, from_, to_, third_):
    if n > 0:
        hanoi(n-1, from_, third_, to_)
        print(f"disk no. {n}: {from_} -> {to_}")
        hanoi(n-1, third_, to_, from_)
In [9]:
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 [10]:
hanoi(2, "A", "B", "C")

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

disk no. 1: 1 -> 2
In [12]:
hanoi(4, 1, 2, 3)

disk no. 1: 1 -> 3
disk no. 2: 1 -> 2
disk no. 1: 3 -> 2
disk no. 3: 1 -> 3
disk no. 1: 2 -> 1
disk no. 2: 2 -> 3
disk no. 1: 1 -> 3
disk no. 4: 1 -> 2
disk no. 1: 3 -> 2
disk no. 2: 3 -> 1
disk no. 1: 2 -> 1
disk no. 3: 3 -> 2
disk no. 1: 1 -> 3
disk no. 2: 1 -> 2
disk no. 1: 3 -> 2

Egy nem rekurzív, hatékonyabb megoldás megkeresése kicsit nehezebb feladat, kihagyjuk. Ha észrevesszük, hogy páratlan $n$ esetén ciklikusan ismételve az alábbi pálcapárok közt mozgatunk egy korongot

A <-> B
A <-> C
B <-> C

míg páros $n$ esetén

A <-> C
A <-> B
B <-> C

párok közt, akkor könnyen írhatunk ilyen programot.

Továbbiak a Wikipedia oldalán.

Pénzváltás

Feladat: adott pénzérmékből mennyi a minimális számú, amellyel egy adott összeg kifizethető. (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 [13]:
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 [14]:
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
5.445605993270874
4399137
In [15]:
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.003894329071044922
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, hogy megnézhessük a tartalmát.

In [16]:
def d_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 [17]:
coins = [1, 2, 5, 10, 20]
start = time.time()
print(d_exchange(34))
print(time.time() - start)

4
0.0022008419036865234
In [18]:
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 [19]:
coins = [1, 5, 8, 10, 20]
start = time.time()
print(d_exchange(24))
print(time.time() - start)

3
0.0014858245849609375
In [20]:
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 [21]:
coins = [5, 10, 20, 50]
start = time.time()
print(d_exchange(24))
print(time.time() - start)

inf
0.004336357116699219
In [22]:
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 [23]:
def r_sums(n):
    if n == 0:
        return [[]]
    else:
        sumlist = []
        for i in range(1, n+1):
            lst = [i]
            for l in r_sums(n-i):
                sumlist.append(lst + l)
    return sumlist

n = 4
print(f"A(z) {n} összesen {len(r_sums(n))}-féleképp bontható fel.")
for s in r_sums(n):
    print((" + ".join(str(x) for x in s)))

A(z) 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 [24]:
def d_sums(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 [25]:
for s in d_sums(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 [26]:
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 (kettős betűk)

Feladat (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 [27]:
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 [28]:
sample = "gally lyuk alma xylofon folyam"
lys = ly(sample)
print(f"{lys[0]} ly és {lys[1]} lly")

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

Állapotgépeket gyakran szövegfelismerésre használnak.

Feladata: Írjunk programot a sztringekben az escape karakterek felismerésére, kiírására és megszámolására!

In [29]:
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 [30]:
sample = r"\"Hello\"\nbackslash: \\not a new line"
print(escape(sample))

\" \" \n \\ 
4

Zárójelezés

Záró feladat: Számoljuk meg, hogy hány zárójel van egy képletben. Az s számláló kezdőértéke legyen 0. Ha nyitó zárójelet találunk, akkor növeljük, ha csukót, akkor csökkentsük 1-gyel, 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 [ ]: