L12. Sirul lui Fibonacci

Sirul lui Fibonacci este  1, 1, 2, 3, 5, 8, 13, 21, 34, …. si are legatura cu celebrul numar de aur.

Se observa ca sirul incepe cu valorile 1 si 1 , dupa care, fiecare noua valoare se obtine prin adunarea ultimelor doua valori:

• F(1)=1
• F(2)=1
• F(n)=F(n-1)+F(n-2)

Pentru noi problema este de a determina al N-lea termen din sir.

Daca N=1 sau N=2, raspunsul este simplu, 1. In restul cazurilor trebuie ca avand mereu ultimile valori A si B, sa calculam noua valoare C=A+B (mereu trebuie memorata noua pereche formata – ultimile doua valori determinate)

citeste N;

A=1;B=1;

daca (N<=2) atunci scrie 1;

        altfel {pentru i=3,N executa

                      {//calculam noua valoare

                       C=A+B;

                      //pregatim noua pereche

                      A=B;B=C}

                scrie B;}