Iteration
Ang Iteration ay pag-uulit ng isang proseso. Ang isang mag-aaral na pumapasok sa paaralan ay inuulit ang proseso ng pagpunta sa paaralan araw-araw hanggang sa pagtatapos. Pumunta kami sa grocery store kahit minsan o dalawang beses sa isang buwan upang bumili ng mga produkto. Inuulit namin ang prosesong ito buwan buwan. Sa matematika, ang isang pagkakasunud-sunod ng Fibonacci ay sumusunod sa mga pag-aari din ng pag-uulit ng gawain. Isaalang-alang natin ang pagkakasunud-sunod ng Fibonacci kung saan ang unang dalawang numero ay 0 at 1, lahat ng iba pang mga numero ay ang kabuuan ng nakaraang dalawang numero.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Mga Hakbang sa Iteration
Ang formula ng Fibonacci ay maaaring isulat bilang,
F (n) = F (n - 1) + F (n - 2)
fibonacci (0) = 0
fibonacci (1) = 1
Fibonacci (2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
fibonacci (3) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
fibonacci (4) = fibonacci (3) + fibonacci (2) = 2 + 1 = 3
fibonacci (5) = fibonacci (4) + fibonacci (3) = 3 + 2 = 5
fibonacci (6) = fibonacci (5) + fibonacci (4) = 5 + 3 = 8
Ang algorithm na ibinigay sa ibaba ay nagbabalik ng ika-apat na numero ng Fibonacci.
Recursion
Sa tuwing makakakuha kami ng isang bagong numero ng Fibonacci (numero ng ika-n) na ang numero ng ika-n (1 - ika-ika) na numero kapag nakita namin ang (n + 1) ika-Fibonacci bilang aming susunod na ika-Fibonacci. Tulad ng nakikita natin ang mga hakbang sa pag-ulit na nabanggit sa itaas: kung n = 2 pagkatapos
Fibonacci (2) = Fibonacci (2 - 1) + Fibonacci (2 - 2) = Fibonacci (1) + Fibonacci (0) = 1 + 0 = 1
Ngayon, nais naming makabuo ng fibonacci (3), iyon ay n = 3.
Fibonacci (3) = Fibonacci (3 - 1) + Fibonacci (3 - 2) = Fibonacci (2) + Fibonacci (1) = 1 + 1 = 2
Nangangahulugan iyon, sa bawat oras na n tataasan ang halaga ng kasalukuyang (n - 1) ika at (n - 2) ika-tsaka din nadagdagan. Ngunit nakakapagod na subaybayan ang (n - 1) ika at (n - 2) ika fibonacci para sa bawat n. Paano ang tungkol sa pagsulat ng isang pamamaraan na tumatawag sa sarili nito upang ulitin ang gawain ng pag-ulit nang mag-isa?
Ang isang pamamaraan na tumatawag mismo ay pinangalanan bilang recursive na pamamaraan. Ang isang recursive na pamamaraan ay dapat magkaroon ng isang base case kung saan hihinto sa pagtawag mismo ng programa. Ang aming batayang kaso para sa serye ng Fibonacci ay fibonacci (0) = 0 at fibonacci (1) = 1. Kung hindi man, ang pamamaraang Fibonacci ay tumatawag sa kanyang sarili nang dalawang beses - fibonacci (n - 1) at fibonacci (n - 2). Pagkatapos ay idinagdag ang mga ito upang makakuha ng fibonacci (n). Ang isang recursive na pamamaraan para sa paghanap ng ika-apat na Fibonacci ay maaaring isulat bilang -
Kung titingnan naming maingat, sumusunod ang recursion sa pag-aari ng stack. Nalulutas nito ang mas maliliit na subproblems upang makuha ang solusyon sa isang problema. Para sa n> 1, isinasagawa nito ang huling linya. Kaya, kung n = 6, Tumawag ang function at nagdaragdag ng fibonacci (6 - 1) at fibonacci (6 - 2). Ang fibonacci (6 - 1) o fibonacci (5) ay tumatawag at nagdaragdag ng fibonacci (5 - 1) at fibonacci (5 - 2). Ang recursion na ito ay nagpatuloy hanggang sa 6 na maabot ang base case halaga na kung saan ay fibonacci (0) = 0 o fibonacci (1) = 1. Sa sandaling ma-hit ang base case ay nagdaragdag ito ng dalawang mga halaga ng base at aakyat hanggang sa makuha ang halaga ng fibonacci ( 6). Nasa ibaba ang isang representasyon ng puno ng recursion.
recursion Tree
Tulad ng nakikita natin, kung gaano katindi ang isang recursion. Isang solong linya lamang ng code ang gumagawa ng puno sa itaas (huling linya ng code sa itaas kasama ang mga pangunahing kaso). Ang Recursion ay nagpapanatili ng isang stack at pupunta ito sa mas malalim hanggang maabot nito ang base case. Dynamic Programming (DP): Ang recursion ay madaling maunawaan at code ngunit maaaring maging mahal sa mga tuntunin ng oras at memorya. Tingnan ang recursion tree sa ibaba. Ang kaliwang subtree na nagsisimula sa fib (4) at ang kanang subtree na nagsisimula sa fib (4) ay eksaktong pareho. Bumubuo ang mga ito ng parehong resulta na kung saan ay 3 ngunit ginagawa ang parehong gawain ng dalawang beses. Kung ang n ay isang malaking bilang (halimbawa: 500000) kung gayon ang recursion ay maaaring gumawa ng isang programa na napakabagal dahil tatawagin ito ng parehong sub task nang maraming beses.
recursion Tree-bilog
Upang maiwasan ang problemang ito maaaring magamit ang dinamikong programa. Sa pabagu-bagong programa maaari naming gamitin ang dati nang nalutas na subtask upang malutas ang hinaharap na gawain ng parehong uri. Ito ay isang paraan upang mabawasan ang gawain para sa paglutas ng orihinal na problema. Magkaroon tayo ng isang array fib [] kung saan nag-iimbak kami ng dating nalutas ang mga solusyon sa subtask. Alam na natin ang fib [0] = 0 at fib [1] = 1. Iimbak natin ang dalawang halagang ito. Ngayon, ano ang halaga ng fib [2]? Tulad ng fib [0] = 0 at fib [1] = 1 na naimbak na dapat lang nating sabihin ang fib [2] = fib [1] + fib [0] at iyon lang. Maaari kaming makabuo ng fib [3], fib [4], fib [5], ……, fib [n] sa parehong paraan. Ang mga naunang nalutas na subtask ay tinatawagan upang makakuha ng susunod na subtask hanggang sa hindi malutas ang orihinal na gawain, sa gayon binabawasan ang kalabasang pagkalkula.
