Algoritmul de generare a numerelor șirului lui Fibonacci

<

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

Algoritmul de generare celui al n-lea element din șirul lui Fibonacci în limbajul de programare Pascal.

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:

Salvăm valoarea ultimului element într-o variabila temporară.
Ultimul element devine cel curent, adică el va reține suma dintre el, elementului de pe poziția n - 1, și penultimul element, cel de pe poziția n - 2. Adică ultimul element devine cel curent.
Penultimul element devine ultimul.

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:

Generarea primelor n valori ale șirului lui Fibonacci

>

C
a
p
i
t
o
l
u
l

u
r
m
ă
t
o
r

>

Ți-a fost de ajutor ce am scris aici?

Hei, mersi de răspuns.