Kartojimas
Kartojimas yra proceso kartojimas. Mokinys, einantis į mokyklą, kartoja procesą, einantį į mokyklą kasdien iki baigimo. Bent kartą ar du per mėnesį einame į maisto prekių parduotuvę pirkti produktų. Mes kartojame šį procesą kiekvieną mėnesį. Matematikoje Fibonači seka taip pat atitinka užduočių kartojimo savybes. Panagrinėkime „Fibonači“ seką, kur pirmieji du skaičiai yra 0 ir 1, visi kiti skaičiai yra dviejų ankstesnių skaičių suma.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Kartojimo žingsniai
„Fibonacci“ formulę galima parašyti taip,
F (n) = F (n - 1) + F (n - 2)
fibonacci (0) = 0
fibonacci (1) = 1
„Fibonači“ (2) = „Fibonači“ (1) + „Fibonači“ (0) = 1 + 0 = 1
fibonacci (3) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
fibonači (4) = fibonači (3) + fibonači (2) = 2 + 1 = 3
fibonacci (5) = fibonacci (4) + fibonacci (3) = 3 + 2 = 5
fibonači (6) = fibonači (5) + fibonači (4) = 5 + 3 = 8
Žemiau pateiktas algoritmas grąžina n-ąjį Fibonači skaičių.
Rekursija
Kiekvieną kartą, kai gauname naują „Fibonacci“ numerį (n-tasis skaičius), n-asis skaičius iš tikrųjų yra (n - 1)-asis skaičius, kai randame (n + 1)-ąjį Fibonači kaip kitą n-tąjį Fibonači. Kaip matome aukščiau minėtus iteracijos etapus: jei n = 2, tada
Fibonači (2) = Fibonači (2 - 1) + Fibonači (2 - 2) = Fibonači (1) + Fibonači (0) = 1 + 0 = 1
Dabar mes norime sukurti fibonacci (3), tai yra n = 3.
Fibonači (3) = Fibonači (3 - 1) + Fibonači (3 - 2) = Fibonači (2) + Fibonači (1) = 1 + 1 = 2
Tai reiškia, kad kiekvieną kartą n padidina srovės (n - 1) vertę, o (n - 2) th fibonači taip pat padidėja. Bet vargina sekti (n - 1) ir (n - 2)-ąjį fibonacci kiekvienam n. Kaip rašyti metodą, kuris pats save kartoja pakartojimo užduotį?
Metodas, kuris save vadina, įvardijamas kaip rekursinis. Rekursinis metodas turi turėti pagrindinį atvejį, kai programa nustoja skambinti. Mūsų pagrindinis „Fibonacci“ serijos atvejis yra fibonacci (0) = 0 ir fibonacci (1) = 1. Priešingu atveju Fibonacci metodas save vadina dvigubai - fibonacci (n - 1) ir fibonacci (n - 2). Tada jis prideda juos gauti fibonacci (n). Rekursinis metodas n-ajam „Fibonacci“ rasti gali būti parašytas taip -
Jei atidžiai žiūrime, rekursija seka kamino savybę. Tai išsprendžia mažesnes problemas, kad gautų problemos sprendimą. Jei n> 1, ji vykdo paskutinę eilutę. Taigi, jei n = 6, funkcija iškviečia ir prideda fibonacci (6 - 1) ir fibonacci (6 - 2). skambina fibonacci (6 - 1) arba fibonacci (5) ir prideda fibonacci (5 - 1) ir fibonacci (5 - 2). Šis rekursija tęsiasi tol, kol 6 pasiekia pagrindinę atvejo vertę, kuri yra fibonacci (0) = 0 arba fibonacci (1) = 1. Paspaudęs bazinę bylą, jis prideda dvi pagrindines reikšmes ir padidėja, kol gauna fibonacci ( 6). Žemiau pateikiamas rekursijos medis.
rekursijos medis
Kaip matome, kokia gali būti rekursija. Tik viena kodo eilutė daro medį aukščiau (paskutinė aukščiau esančio kodo eilutė, įskaitant pagrindinius atvejus). Rekursija palaiko kaminą ir eina gilyn, kol pasiekia pagrindinę bylą. Dinaminis programavimas (DP): rekursija yra lengvai suprantama ir koduojama, tačiau gali būti brangi laiko ir atminties prasme. Pažvelkite į žemiau esantį rekursijos medį. Kairysis pomedis, prasidedantis fib (4), ir dešinysis pomedis, prasidedantis fib (4), yra visiškai vienodi. Jie generuoja tą patį rezultatą, kuris yra 3, bet tą pačią užduotį atlieka du kartus. Jei n yra didelis skaičius (pavyzdys: 500000), rekursija gali padaryti programą labai lėtą, nes ji tą pačią užduotį iškvies kelis kartus.
rekursija Apsukta medžiu
Norėdami išvengti šios problemos, galima naudoti dinaminį programavimą. Dinaminiame programavime galime naudoti anksčiau išspręstą antrinę užduotį būsimoms to paties tipo užduotims išspręsti. Tai būdas sumažinti užduotį, kaip išspręsti pradinę problemą. Turėkime masyvą fib [], kuriame saugome anksčiau išspręstus užduočių sprendimus. Mes jau žinome, kad fib [0] = 0 ir fib [1] = 1. Saugokime šias dvi reikšmes. Dabar kokia yra fib [2] vertė? Kadangi fib [0] = 0 ir fib [1] = 1 jau buvo saugomi, mes tiesiog turime pasakyti fib [2] = fib [1] + fib [0] ir viskas. Lygiai taip pat galime generuoti fib [3], fib [4], fib [5], ……, fib [n]. Anksčiau išspręstos užduotys kviečiamos gauti kitą užduotį, kol pirminė užduotis nebus išspręsta, taigi sumažėja nereikalingas skaičiavimas.
