 |  |
 |
Nick: NEVERLAND
Oggetto: re:Serie di Fibonacci
Data: 22/5/2006 18.23.59
Visite: 36
divertiti e poi mi fai sapere :°D
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;
Ultime Visioni:
Il Codice Da Vinci (***)
Crash - Contatto Fisico (***)
Il Conto E' Chiuso (*)
L'Era Glaciale (***)
Il Castello Errante di Howl (***)
H2Odio (**)
L'Era Glaciale 2 - Il Disgelo (***)
