|
< C a p i t o l u l a n t e r i o r < |
Cerința: Să se genereze al n-lea element din șirul lui Fibonacci. 1. Algoritm Șirul lui Fibonacci, deși neinteresant la prima vedere, este o problemă interesantă când vine vorba de a fi pusă într-un algoritm. Nu că ar fi dificilă. În primul rând pentru a genera șirul lui Fibonacci, trebuie să știm cum este el definit, și asta e ușor. F(0) = 0 și F(1) = 1. Iar de la indexul 2 înainte avem: F(n) = F(n - 2) + F(n - 1) (unde n ≥ 2) Cu alte cuvinte, fiecare element este suma ultimilor săi 2 predecesori. 2. Executare
Ca și variabile avem nevoie de ultimele două valori ale șirului, pe care le putem reține în F1 și F2. Apoi avem nevoie de o variabilă temporară, aici numită FTemp, pentru a reține ultima valoare - cea care va defini elementul următor. Apoi avem nevoie doar de o variabilă în care vom memora poziția elementului dorit (el) și o altă variabilă temporară care ne va fi variabila de ciclare. Fiindcă generarea elementului de pe poziția x înseamnă doar să calculăm suma celor doi predecesori ai săi, tot ce trebuie să facem e să aflăm această sumă până ce ajungem la rangul cerut. În cazul în care rangul, sau indexul, cerut e 0 sau 1, știind valorile din definiția funcției, pur și simplu le tipărim. Dacă acesta este mai mare sau egal cu 2, pur și simplu intrăm într-un ciclu unde:
La sfârșitul ciclului, pur și simplu afișăm valoarea ultimul element, care, după ce am scris mai sus, de fapt va fi elementul curent.
O altă abordare ar cuprinde păstrarea valorilor într-un vector, însă aceasta ne-ar limita. Dacă avem un vector de 100 de elemente ar consuma destul de multă memorie, iar pe de altă parte numerele din șirul lui Fibonacci ajung destul de repede, destul de mari. Iar integer e limitat la valoarea maximă de doar 32 768. Iar al 24-lea element are deja valoarea 46 368. Și tipul de date word nu ar ajuta mai mult. Pe de altă parte dacă trebuie să: „Generați primele n elemente ale șirului lui Fibonacci.” Atunci tot ce trebuie să facem este să tipărim la fiecare pas valoarea lui F2: |
> C a p i t o l u l u r m ă t o r > |
Ți-a fost de ajutor ce am scris aici?
Motivul:
Hei, mersi de răspuns.
|