Az N-edik Fibonacci-számot háromféleképpen találjuk meg ésszerű időn belül: a dinamikus programozás alapjai. Fibonacci számok: hurok és rekurzió Fibonacci c rekurzió

A különféle olimpiákon nagyon gyakran találkoznak ilyen problémákkal, amelyek, mint első pillantásra tűnik, egyszerű kereséssel megoldhatók. De ha a számot számoljuk lehetséges opciók, akkor azonnal meg fogunk győződni ennek a megközelítésnek a hatástalanságáról: például az alábbi egyszerű rekurzív függvény már a 30. Fibonacci-számnál jelentős erőforrásokat emészt fel, míg az olimpiákon sokszor 1-5 másodpercre korlátozzák a megoldási időt.

Int fibo (int n) (ha (n == 1 || n == 2) (1;) else (return fibo (n - 1) + fibo (n - 2);))

Gondoljuk át, miért történik ez. Például a fibo (30) kiszámításához először kiszámoljuk a fibo-t (29) és a fibo-t (28). De ugyanakkor a programunk "elfelejti", hogy fibo (28) mi már kitalálta amikor fibót keres (29).

Az ilyen megközelítés fő hibája az, hogy a függvény argumentumainak ugyanazokat az értékeit sokszor számítják ki - és ezek meglehetősen erőforrás-igényes műveletek. Az ismétlődő számításoktól való megszabadulásban segítségünkre lesz a módszer dinamikus programozás- ez egy technika, használatakor a probléma általános és ismétlődő részfeladatokra oszlik, melyek mindegyikét csak egyszer oldják meg - ez jelentősen növeli a program hatékonyságát. Ez a módszer részletesen le van írva, és vannak példák más problémák megoldására is.

A funkció javításának legegyszerűbb módja, ha emlékezünk a már kiszámított értékekre. Ehhez be kell vezetnünk egy további tömböt, amely egyfajta "gyorsítótárként" fog szolgálni a számításainkhoz: új érték kiszámítása előtt ellenőrizzük, hogy korábban számoltuk-e. Ha kiszámoltuk, akkor a kész értéket vesszük ki a tömbből, ha pedig nem számoltuk ki, akkor az előzőek alapján kell kiszámolnunk és emlékeznünk kell rá a jövőben:

Int gyorsítótár; int fibo (int n) (if (gyorsítótár [n] == 0) (if (n == 1 || n == 2) (gyorsítótár [n] = 1;) else (gyorsítótár [n] = fibo (n) - 1) + fibo (n - 2);)) gyorsítótár visszatérése [n];)

Mivel ebben a feladatban az N-edik érték kiszámításához garantáltan szükségünk lesz (N-1) -edikre, nem lesz nehéz iteratív formában átírni a képletet - csak sorban töltjük ki a tömbünket, amíg el nem érjük a kívánt cella:

<= n; i++) { cache[i] = cache + cache; } cout << cache;

Most már észrevehetjük, hogy amikor kiszámoljuk F (N) értékét, akkor F (N-3) értéke már garantált számunkra soha nem lesz szüksége. Vagyis csak két értéket kell tárolnunk a memóriában - F (N-1) és F (N-2). Sőt, amint kiszámoltuk az F(N)-t, az F(N-2) tárolása értelmét veszti. Próbáljuk meg leírni ezeket a gondolatokat kód formájában:

// Két korábbi érték: int cache1 = 1; int cache2 = 1; // Új érték int cache3; for (int i = 2; i<= n; i++) { cache3 = cache1 + cache2; //Вычисляем новое значение //Абстрактный cache4 будет равен cache3+cache2 //Значит cache1 нам уже не нужен?.. //Отлично, значит cache1 -- то значение, которое потеряет актуальность на следующей итерации. //cache5 = cache4 - cache3 =>Az iteráció után a cache2 elveszti relevanciáját, azaz. cache1 legyen // Más szóval, cache1 - f (n-2), cache2 - f (n-1), cache3 - f (n). // Legyen N = n + 1 (az a szám, amelyet a következő iterációnál számítunk ki). Ekkor n-2 = N-3, n-1 = N-2, n = N-1. // Az új valóságnak megfelelően átírjuk a változóink értékeit: cache1 = cache2; cache2 = cache3; ) cout<< cache3;

Egy tapasztalt programozó megérti, hogy a fenti kód általában nonszensz, mivel a cache3 soha nem használatos (azonnal a cache2-be íródik), és a teljes iteráció átírható egyetlen kifejezéssel:

Gyorsítótár = 1; gyorsítótár = 1; for (int i = 2; i<= n; i++) { cache = cache + cache; //При i=2 устареет 0-й элемент //При i=3 в 0 будет свежий элемент (обновили его на предыдущей итерации), а в 1 -- ещё старый //При i=4 последним элементом мы обновляли cache, значит ненужное старьё сейчас в cache //Интуитивно понятно, что так будет продолжаться и дальше } cout << cache;

Azok számára, akik nem értik, hogyan működik a varázslat a felosztás többi részével, vagy egyszerűen csak egy nem nyilvánvaló képletet szeretnének látni, van egy másik megoldás:

Int x = 1; int y = 1; for (int i = 2; i< n; i++) { y = x + y; x = y - x; } cout << "Число Фибоначчи: " << y;

Próbálja követni a program végrehajtását: meg fog győződni az algoritmus helyességéről.

P.S. Általában egyetlen képlet létezik bármely olyan Fibonacci-szám kiszámítására, amely nem igényel iterációt vagy rekurziót:

Const dupla SQRT5 = sqrt (5); const dupla PHI = (SQRT5 + 1) / 2; int fibo (int n) (return int (pow (PHI, n) / SQRT5 + 0,5);)

De ahogy sejthető, az a bökkenő, hogy a nem egész számok hatványainak kiszámítása meglehetősen magas, csakúgy, mint a hibájuk.

Fibonacci számok Olyan számsor, amelyben minden következő szám egyenlő az előző két szám összegével: 1, 1, 2, 3, 5, 8, 13, .... Néha a sor nulláról kezdődik: 0, 1, 1, 2, 3, 5, .... Ebben az esetben maradunk az első lehetőségnél.

Képlet:

F 1 = 1
F 2 = 1
F n = F n-1 + F n-2

Számítási példa:

F 3 = F 2 + F 1 = 1 + 1 = 2
F 4 = F 3 + F 2 = 2 + 1 = 3
F 5 = F 4 + F 3 = 3 + 2 = 5
F 6 = F 5 + F 4 = 5 + 3 = 8
...

Fibonacci sorozat n-edik számának kiszámítása while ciklus segítségével

Rendelje hozzá a fib1 és fib2 változókhoz a sor első két elemének értékét, azaz rendeljen egységeket a változókhoz.
Kérd meg a felhasználótól annak az elemnek a számát, amelynek az értékét szeretné megkapni. Rendeljen számot az n változóhoz.
Hajtsa végre a következő lépéseket n - 2 alkalommal, mivel az első két elemet már figyelembe vettük:
1. Adja hozzá a fib1-et és a fib2-t, és rendelje hozzá az eredményt egy ideiglenes tárolási változóhoz, például fib_sum.
2. Állítsa be a fib1 változót fib2-re.
3. Állítsa a fib2 változót fib_sum értékre.
Jelenítse meg a fib2 értékét.

Jegyzet. Ha a felhasználó 1-et vagy 2-t ír be, a ciklus törzse soha nem kerül végrehajtásra, a fib2 eredeti értéke jelenik meg.

fib1 = 1 fib2 = 1 n = bemenet () n = int (n) i = 0 míg i< n - 2 : fib_sum = fib1 + fib2 fib1 = fib2 fib2 = fib_sum i = i + 1 print (fib2)

A kód kompakt verziója:

fib1 = fib2 = 1 n = int (bemenet ( "A Fibonacci-sorozat elemszáma:")) - 2 míg n> 0: fib1, fib2 = fib2, fib1 + fib2 n - = 1 nyomtatás (fib2)

Fibonacci számok kiírása for hurokkal

Ebben az esetben nem csak a Fibonacci sorozat szükséges elemének értéke jelenik meg, hanem az összes szám egészen addig, beleértve azt is. Ehhez a fib2 érték kimenetét hurokba helyezzük.

fib1 = fib2 = 1 n = int (bemenet ()), ha n< 2 : quit() print (fib1, end= " " ) print (fib2, end= " " ) for i in range (2 , n) : fib1, fib2 = fib2, fib1 + fib2 print (fib2, end= " " ) print ()

Végrehajtási példa:

10 1 1 2 3 5 8 13 21 34 55

A Fibonacci sorozat n-edik számának rekurzív számítása

Ha n = 1 vagy n = 2, akkor adjon vissza egyet a hívó ághoz, mivel a Fibonacci sorozat első és második eleme eggyel egyenlő.
Minden más esetben ugyanazt a függvényt hívja meg n - 1 és n - 2 argumentumokkal. Adja hozzá a két hívás eredményét, és adja vissza a hívó program ágába.

def fibonacci (n): ha n in (1, 2): 1 visszatérés fibonacci (n - 1) + fibonacci (n - 2) print (fibonacci (10))

Tegyük fel, hogy n = 4. Ez rekurzív módon hívja a fibonaccit (3) és a fibonaccit (2). A második egyet ad vissza, az első pedig további két függvényhívást eredményez: fibonacci (2) és fibonacci (1). Mindkét hívás egyet ad vissza, összesen kettőt. Így a fibonacci (3) hívás visszaadja a 2-es számot, amely hozzáadódik a fibonacci (2) hívás 1-eséhez. A 3. eredmény visszatér a mainstreamhez. A Fibonacci sorozat negyedik eleme három: 1 1 2 3.

A programozóknak mostanra már elegük van a Fibonacci-számokból. Számításukra mindenhol példákat használnak. Ez azért van, mert ezek a számok adják a rekurzió legegyszerűbb példáját. Jó példái a dinamikus programozásnak is. De szükséges-e ezeket így kiszámítani egy valós projektben? Nem. Sem a rekurziós, sem a dinamikus programozás nem ideális választás. És nem egy lebegőpontos számokat használó zárt képlet. Most elmondom, hogyan kell helyesen csinálni. De először nézzük meg az összes ismert megoldást.

A kód Python 3-ra vonatkozik, bár a Python 2-re is mennie kell.

Először is hadd emlékeztesselek a definícióra:

F n = F n-1 + F n-2

És F 1 = F 2 = 1.

Zárt képlet

A részleteket kihagyjuk, de aki szeretne, az megismerkedhet a képlet levezetésével. Az ötlet az, hogy feltételezzük, hogy van olyan x, amelyre F n = x n, majd keressük meg x-et.

Mit csinál

Csökkentse x n-2

Megoldjuk a másodfokú egyenletet:

Hol nő az „aranymetszet” ϕ = (1 + √5) / 2-ből? A kezdeti értékeket behelyettesítve és további számításokat végezve a következőket kapjuk:

Ezt használjuk az F n kiszámításához.

A __jövő__ import részlegből import math def fib (n): SQRT5 = math.sqrt (5) PHI = (SQRT5 + 1) / 2 return int (PHI ** n / SQRT5 + 0,5)

Jó:
Gyors és egyszerű kis n
Rossz:
Lebegőpontos műveletek szükségesek. A nagy n nagyobb pontosságot igényel.
Gonosz:
A komplex számok használata az F n kiszámításához matematikai szempontból szép, de számítógépes szempontból csúnya.

Rekurzió

A legkézenfekvőbb megoldás, amelyet már sokszor láttál, valószínűleg egy példa arra, hogy mi a rekurzió. A teljesség kedvéért még egyszer megismétlem. Pythonban egy sorba írható:

Fib = lambda n: fib (n - 1) + fib (n - 2), ha n> 2 különben 1

Jó:
Nagyon egyszerű megvalósítás, amely megismétli a matematikai definíciót
Rossz:
Exponenciális végrehajtási idő. Nagyon lassú a nagy n
Gonosz:
Verem túlcsordulás

Memorizálás

A rekurzív megoldásnak van egy nagy problémája: a metsző számítások. A fib (n) meghívásakor a fib (n-1) és fib (n-2) megszámolásra kerül. De amikor megszámolja a fib (n-1) értéket, az ismét függetlenül számolja a fib-t (n-2) – vagyis a fib (n-2) kétszeresét számolja. Ha folytatjuk az érvelést, látni fogjuk, hogy a fib (n-3) háromszor lesz számolva, és így tovább. Túl sok kereszteződés.

Ezért csak meg kell jegyeznie az eredményeket, hogy ne számolja újra. Ehhez a megoldáshoz lineárisan használjuk fel az időt és a memóriát. A megoldásban szótárt használok, de egy egyszerű tömböt is lehetett volna használni.

M = (0:0, 1:1) def fib (n): ha n az M-ben: visszatérés M [n] M [n] = fib (n - 1) + fib (n - 2) visszatérés M [n]

(Pythonban ez a functools.lru_cache dekorátorral is megtehető.)

Jó:
Csak alakítsa át a rekurziót emlékező megoldássá. Az exponenciális végrehajtási időt lineáris idővé alakítja, ami több memóriát fogyaszt.
Rossz:
Sok memóriát pazarol
Gonosz:
Lehetséges veremtúlcsordulás, például rekurzió

Dinamikus programozás

Az emlékezéssel történő döntés után világossá válik, hogy nem az összes korábbi eredményre van szükségünk, hanem csak az utolsó kettőre. Alternatív megoldásként ahelyett, hogy a fib (n) ponttól kezdené, és visszafelé sétálna, elkezdheti a fib (0) ponttól, és sétálhat előre. A következő kód lineáris végrehajtási idővel és fix memóriahasználattal rendelkezik. A gyakorlatban a megoldás sebessége még nagyobb lesz, mivel nincs rekurzív függvényhívás és kapcsolódó munka. És a kód egyszerűbbnek tűnik.

Ezt a megoldást gyakran emlegetik a dinamikus programozás példájaként.

Def fib (n): a = 0 b = 1 __ esetén az (n) tartományban: a, b = b, a + b visszatér a

Jó:
Gyorsan működik kis n-es, egyszerű kódokhoz
Rossz:
Még mindig lineáris futásidő
Gonosz:
Semmi különös.

Mátrix algebra

És végül a legkevésbé megvilágított, de a leghelyesebb megoldás, bölcsen kihasználva az időt és a memóriát. Bármilyen homogén lineáris szekvenciára kiterjeszthető. Az ötlet a mátrixok használata. Elég csak ezt látni

Ennek általánosítása arra utal

Az x két korábban kapott értéke, amelyek közül az egyik az aranymetszés volt, a mátrix sajátértékei. Ezért a zárt képlet levezetésének másik módja a mátrixegyenlet és a lineáris algebra használata.

Miért hasznos tehát egy ilyen megfogalmazás? Az a tény, hogy a hatványozás logaritmikus időben is elvégezhető. Ez négyzetre emeléssel történik. A lényeg az

Ahol az első kifejezést páros A-ra használjuk, a másodikat páratlanra. Már csak a mátrixszorzást kell megszervezni, és kész. Kiderül a következő kód. Megszerveztem a pow rekurzív megvalósítását, mert könnyebben érthető. Tekintse meg az iteratív verziót itt.

Def pow (x, n, I, mult): "" "Az x-et az n-edik hatványra adja vissza. Feltételezi, hogy I az azonosságmátrix szorozva multtal, és n egy pozitív egész" "" ha n == 0: I elif visszatérés n == 1: return x else: y = pow (x, n // 2, I, mult) y = mult (y, y) if n% 2: y = mult (x, y) return y def identitásmátrix ( n): "" "Az n-szeres azonosságmátrixot adja vissza" "" r = lista (tartomány (n)) return [for j in r] def matrix_multiply (A, B): BT = lista (zip (* B) ) ) return [az A sor_a] def fib (n): F = pow ([,], n, identitásmátrix (2), mátrix_szorzás) return F

Jó:
Rögzített memóriaméret, logaritmikus idő
Rossz:
Bonyolultabb kód
Gonosz:
Mátrixokkal kell dolgoznunk, bár nem olyan rosszak

Teljesítmény-összehasonlítás

Csak a dinamikus programozás és a mátrix változatát érdemes összehasonlítani. Ha összehasonlítjuk őket az n szám számjegyeinek számával, akkor kiderül, hogy a mátrixmegoldás lineáris, a dinamikus programozású megoldás pedig exponenciális. Gyakorlati példa a fib (10 ** 6) kiszámítása, amely szám több mint kétszázezer karakterből áll.

N = 10** 6
Fib_mátrix kiszámítása: fib (n) összesen 208988 számjegyből áll, a számítás 0,24993 másodpercet vett igénybe.
Fib_dynamic számítása: fib (n) összesen 208988 számjegyből áll, a kiszámítása 11,83377 másodpercet vett igénybe.

Elméleti megjegyzések

Nem közvetlenül érintve a fenti kódot, ez a megjegyzés még mindig érdekes. Tekintsük a következő grafikont:

Számoljuk meg az n hosszúságú utak számát A-tól B-ig. Például n = 1 esetén egy utunk van, 1. n = 2 esetén ismét egy út van, 01. n = 3 esetén két út van, 001 és 101 Egész egyszerűen kimutatható, hogy az n hosszúságú utak száma A-tól B-ig pontosan egyenlő F n-nel. A gráf szomszédsági mátrixát felírva ugyanazt a mátrixot kapjuk, amit fentebb leírtunk. Ez egy jól ismert eredmény a gráfelméletből, miszerint egy adott A szomszédsági mátrix esetén az A n-beli előfordulások a gráf n hosszúságú utak száma (a „Good Will Hunting” című filmben említett egyik probléma).

Miért vannak ilyen jelölések a széleken? Kiderült, hogy ha egy végtelen karaktersorozatot nézünk egy végtelen mindkét irányú útvonalsorozaton egy gráfon, akkor valami „véges típusú részeltolásnak” nevezett jelenséget kapunk, amely a szimbolikus dinamikai rendszer egy típusa. A végső típusnak ezt a sajátos alváltását „aranymetszés-eltolódásnak” nevezik, és a „tiltott szavak” halmaza határozza meg (11). Más szavakkal, mindkét irányban végtelen számú bináris sorozatot kapunk, és ezek párja nem lesz szomszédos. Ennek a dinamikus rendszernek a topológiai entrópiája egyenlő a ϕ aranymetszővel. Érdekes, hogy ez a szám periodikusan megjelenik a matematika különböző területein.