Numeri di Fibonacci

Definizione

I numeri di Fibonacci sono definiti dalla relazione di ricorrenza:

F(1)=1
F(2)=1
F(n)=F(n-1)+F(n-2), per n>=3

Talvolta tale relazione viene data a partire da 0:

F(0)=0
F(1)=1
F(n)=F(n-1)+F(n-2), per n>=2

Nel seguito consideremo questa seconda formulazione.

Algoritmo ricorsivo

E' relativamente semplice scrivere una funzione Pascal ricorsiva che calcoli l'n-esimo numero di Fibonacci (si tratta sostanzialmente di tradurre da "notazione matematica" a Pascal).

{AI: n>=0}
{AF: restituisce l'n-esimo numero di Fibonacci}
function fibR (n:integer):longint;
  begin
    if n=0 then fib:=0
    else if n=1 then fibR:=1
    else fibR:=fibR(n-1)+fibR(n-2)
  end;

La funzione ricorsiva ha un inconveniente: ogni chiamata della funzione con argomento n>1 causa due successive chiamate ricorsive, ovvero: il numero totale di chiamate (complessita' computazionale in tempo) cresce esponenzialmente rispetto al valore del parametro n.

Il numero massimo di record di attivazione presenti contemporaneamente sullo stack (complessita' computazionale in spazio) e' lineare in n. Per rendersi conto di cio', e' sufficiente disegnare l'albero delle chiamate della funzione fibR(n), ad es. per n=5.

Algoritmo iterativo

Per scrivere l'algoritmo iterativo procediamo nel seguente modo.

Consideriamo l'intestazione della procedura, con asserzioni iniziali e finali:
```
{AI: n>0}
{AF: restituisce F(n)}
```
Per n<2 il valore di F(n) e' dato (F(0)=0 e F(1)=1).
Per n>=2, invece il valore di F(n) e' calcolato a partire da F(n-1) e F(n-2).
Un invariante di ciclo per il calcolo di F(n) dovra' quindi necessariamente menzionare:
- un indice i che varia da 1 a n
- una variabile f che contiene F(i) e una variabile p che contiene F(i-1)
L'invariante sara' quindi il seguente:
```
{1<=i<=n, f=F(i), p=F(i-1)}
```

Possiamo quindi procedere con la scrittura del codice Pascal.

Per prima cosa scriviamo dello "pseudo-codice", ovvero codice Pascal in cui alcuni dettagli non sono sviluppati:

{AI: n>0}
{AF: restituisce l'n-esimo numero di Fibonacci}
function fibI (n:integer):longint;
  var 
    i:integer;
    f,p:longint;
  begin
    f:=1; p:=0;

    i:=1;
    while i<=n-1 do {1<=i<=n, f=F(i), p=F(i-1)}
      begin
        -- assegna F(i+1) a f, e F(i) a p
        i:=i+1;
      end;
    end;

    fibI:=f;
  end;

Possiamo ora raffinare lo pseudo-codice (nel fare cio' abbiamo introdotto una variable ausiliaria):

{AI: n>0}
{AF: restituisce l'n-esimo numero di Fibonacci}
function fibI (n:integer):longint;
  var 
    i:integer;
    f,p:longint;
    aux:longint; {variabile ausiliaria}
  begin
    f:=1; p:=0;

    i:=1;
    while i<=n-1 do {1<=i<=n, f=F(i), p=F(i-1)}
      begin
        aux:=f;
        f:=f+p; p:=aux;
        i:=i+1;
      end;
    end;

    fibI:=f;
  end;

Ora miglioriamo la procedura precedente, in modo che funzioni anche per n=0.

{AI: n>=0}
{AF: restituisce l'n-esimo numero di Fibonacci}
function fibI (n:integer):longint;
  var 
    i:integer;
    f,p:longint;
    aux:longint; {variabile ausiliaria}
  begin
    if n=0 then fibI:=0 else
    begin
      f:=1; p:=0;

      i:=1;
      while i<=n-1 do {1<=i<=n, f=F(i), p=F(i-1)}
        begin
          aux:=f;
          f:=f+p;
          p:=aux;
          i:=i+1;
        end;

      fibI:=f;
    end;
  end;

Il codice risultante e' "appesantito" (di meno facile lettura). Usando l'istruzione exit del Turbo Pascal e' possibile produrre una versione piu' "leggera" (di piu' facile lettura).

{AI: n>=0}
{AF: restituisce l'n-esimo numero di Fibonacci}
function fibI (n:integer):longint;
  var 
    i:integer;
    f,p:longint;
    aux:longint; {variabile ausiliaria}
  begin
    if n=0 then begin fibI:=0; exit end;

    {n>0}
    f:=1; p:=0;

    i:=1;
    while i<=n-1 do {1<=i<=n, f=F(i), p=F(i-1)}
      begin
        aux:=f;
        f:=f+p;
        p:=aux;
        i:=i+1;
      end;

    fibI:=f;
  end;

Sempre per migliorare la leggibilita' del codice e' consigliabile rimpiazzare il "while" con un "for":

{AI: n>=0}
{AF: restituisce l'n-esimo numero di Fibonacci}
function fibI (n:integer):longint;
  var 
    i:integer;
    f,p:longint;
    aux:longint; {variabile ausiliaria}
  begin
    if n=0 then begin fibI:=0; exit end;

    {n>0}
    f:=1; p:=0;
    
    for i:=1 to n-1 do {1<=i<=n, f=F(i), p=F(i-1)}
      begin
        aux:=f;
        f:=f+p;
        p:=aux;
      end;

    fibI:=f;
  end;

Osserviamo infine che (siccome F(n-1)=F(n)-F(n-2)) possiamo eliminare la variabile ausiliaria aux, migliorando ulteriormente la leggibilita del codice.

{AI: n>=0}
{AF: restituisce l'n-esimo numero di Fibonacci}
function fibI (n:integer):longint;
  var 
    i:integer;
    f,p:longint;
  begin
    if n=0 then begin fibI:=0; exit end;

    {n>0}
    f:=1; p:=0;

    for i:=1 to n-1 do {1<=i<=n, f=F(i), p=F(i-1)}
      begin
        f:=f+p;
        p:=f-p;
      end;

    fibI:=f;
  end;

La complessita' computazionale in tempo della versione iterativa e' lineare in n.

Il numero massimo di record di attivazione presenti contemporaneamente sullo stack (complessita' computazionale in spazio) e' costante.

Riempimento di un vettore con i primi n+1 numeri di Fibonacci

Una prima versione

const 
  MAX=100; {MAX>=1}

type 
  vett = array[0..MAX] of longint;

{AI: 0<=n<=MAX}
{AF: f[0..n] contiene i numeri di Fibonacci F(0),...,F(n)}
procedure fibP (f:vett; n:integer);
  var 
    i:integer;
  begin
    f[1]:=0; f[2]:=1;

    for i:=1 to n-1 do {1<=i<=n, f[0..i] contiene F(0),...,F(i)}
      f[i+1]:=f[i]+f[i-1];
   end;

Una seconda versione (ossevate l'invariante)

const 
  MAX=100; {MAX>=1}

type 
  vett = array[0..MAX] of longint;

{AI: 0<=n<=MAX}
{AF: f[0..n] contiene i numeri di Fibonacci F(0),...,F(n)}
procedure fibP (f:vett; n:integer);
  var 
    i:integer;
  begin
    f[1]:=0; f[2]:=1;

    for i:=2 to n do {2<=i<=n+1, f[0..i-1] contiene F(0),...,F(i-1)}
      f[i]:=f[i-1]+f[i-2];
   end;