Dinamikus programozás: egy probléma megoldása úgy, hogy
Rekurzív humor:
Rekurzív rövidítések:
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 fibonacci.szamlalo a fibonacci-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 hváskor megnöveljük a változót, azaz megszámoljuk vele a függvényhívások számát. Ez sok esetben triviális, rekurzív függvények esetén viszont egyáltalán nem az.
import time
def rekurziv_fib(n):
rekurziv_fib.szamlalo += 1
if n <= 1:
return n
else:
return rekurziv_fib(n-1) + rekurziv_fib(n-2)
rekurziv_fib.szamlalo = 0
start = time.time()
print rekurziv_fib(33)
print time.time() - start
print rekurziv_fib.szamlalo
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. De van még hatékonyabb megoldás, ha csak az utolsó két értéket tároljuk.
import time
def dp_fib(n):
f = [0, 1]
for i in range(n-1):
f = [f[1], f[0] + f[1]]
return f[1]
start = time.time()
print dp_fib(1000)
print time.time() - start
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!
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.)
def hanoi(n, honnan, hova, minat):
if n>0:
hanoi(n-1, honnan, minat, hova)
print "a(z) {0}. korong: {1} ==> {2}".format(n, honnan, hova)
hanoi(n-1, minat, hova, honnan)
hanoi(3,"A","B","C")
Egy nem rekurzív, hatékonyabb megoldás megkeresése nehezebb feladat, kihagyjuk.
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, hogy a összeg és minden érme értéke egész szám.) A mohó algoritmus 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 a mohó algoritmus 5 érmét ad, de 3 db 8-talléros érmével is megoldás. Rekurzív megoldást keresünk.
A rekurzív pénzváltó program (rekurzivPV) az érmék egy listáját kapja és a felváltandó összeget.
import time
def rekurziv_pv(ermek, felvaltando):
rekurziv_pv.szamlalo += 1
ermekSzMin = float('inf')
if felvaltando in ermek:
return 1
else:
for e in [erme for erme in ermek if erme <= felvaltando]:
ermekSz = 1 + rekurziv_pv(ermek, felvaltando - e)
if ermekSz < ermekSzMin:
ermekSzMin = ermekSz
return ermekSzMin
rekurziv_pv.szamlalo = 0
start = time.time()
print rekurziv_pv([1,2,5,10,20], 34)
print time.time() - start
print rekurziv_pv.szamlalo
rekurziv_pv.szamlalo = 0
start = time.time()
print rekurziv_pv([1,2,5,8,10], 24)
print time.time() - start
print rekurziv_pv.szamlalo
E program igen lassú, nagyobb összegekre kivárhatatlan a sok függvényhívás miatt.
Í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{ermekSzMin}=1+\min\left\{\begin{array}{l}\texttt{memoriatabla[24-1]}\\\texttt{memoriatabla[24-5]}\\\texttt{memoriatabla[24-10]}\end{array}\right\}$$
A programban a táblázatot globálisnak deklaráltuk, de kizárólag csak azért, hogy kívülről is belenézhessünk, egyébként nem kéne.
def dinamikus_pv(ermek, felvaltando):
global memoriatabla
memoriatabla = [0]*(felvaltando+1)
for f in range(1, felvaltando+1):
ermekSzMin = float('inf')
for e in [erme for erme in ermek if erme <= f]:
if memoriatabla[f-e] + 1 < ermekSzMin:
ermekSzMin = memoriatabla[f-e] + 1
memoriatabla[f] = ermekSzMin
return memoriatabla[felvaltando]
start = time.time()
print dinamikus_pv([1,2,5,10], 24)
print time.time() - start
print memoriatabla
start = time.time()
print dinamikus_pv([1,2,5,8,10], 24)
print time.time() - start
print memoriatabla
start = time.time()
print dinamikus_pv([5,10,20,50], 84)
print time.time() - start
print memoriatabla
start = time.time()
print dinamikus_pv([5,10,20], 25)
print time.time() - start
print memoriatabla
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!
def sums(n):
if n == 0:
return [[]]
if n == 1:
return [[1]]
else:
sumlist = []
for i in range(1,n+1):
L = [i]
for l in sums(n-i):
sumlist.append(L + l)
return sumlist
for s in sums(4):
print " + ".join(str(x) for x in s)
def sums_d(n):
global memoriatabla
memoriatabla = [[[]], [[1]]]
if n == 0 or n == 1:
return memoriatabla[n]
for i in range(2, n+1):
sumlist = [[i]]
for j in range(1, i):
for l in memoriatabla[i - j]:
sumlist.append([j] + l)
memoriatabla.append(sumlist)
return memoriatabla[n]
for s in sums_d(4):
print " + ".join(str(x) for x in s)
print memoriatabla
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
l és s=0, akkor s=1;l és s=1, akkor s=2;y és s=1 vagy s=2, akkor megjegyezzük, hogy találtunk egyet és s=0;s=0sample = "gally lyuk alma xylofon folyam"
s = 0
counter = 0
for i in sample:
if i == 'l':
if s <= 1:
s += 1
else:
s = 0
elif i == 'y' and (s == 1 or s == 2):
counter += 1
s = 0
else:
s = 0
print counter
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, pl. a Python fordítója is egy ilyen állapotgép, persze sokkal bonyolultabb.