Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Numeri di Fibonacci

Precedente
SUPERIORE
Successiva

La crescita della popolazione di conigli...

Sinteticamente, il problema è il seguente: con le ipotesi

bulletil 1° mese è presente una coppia di conigli
bulletuna coppia di conigli diventa "matura" all'inizio del 2° mese di vita
bulletla gestazione dura un mese
bulletogni parto produce una coppia di conigli

calcolare il numero di conigli dopo x mesi.

Soluzione

In pratica, se A, B, C ... sono i nomi delle coppie di conigli, risulta

Mese Nascite Popolazione
1 A A
2 - A
3 B A---------->B
4 C A------>C   B
5 D E A-->D   C   B-->E
... ...

...

Ogni mese compaiono i conigli presenti il mese precedente più i figli dei conigli presenti due mesi prima.

Al 5° mese le coppie di conigli presenti sono A, B, C, D, E, quindi il numero di conigli è 2*5=10. E dopo x mesi?

Soluzione ricorsiva

Fib(n)=1                 n=1
Fib(n)=1 n=2
Fib(n)=Fib(n-1)+Fib(n-2) altrimenti

Esempio

Con N=5:

Fib(5) = Fib(4)+Fib(3)
       = [Fib(3)+Fib(2)]+[Fib(2)+Fib(1)]
       = [Fib(2)+Fib(1)]+1+1+1
       = 1+1+1+1+1
       = 5 coppie

Codifica

function FiboRic(N: LongInt): LongInt;
begin
  if(N <= 2) then
    FiboRic:=1
  else
    FiboRic:=FiboRic(N-1)+FiboRic(N-2);
end;

Soluzione iterativa

A partire dai valori noti si calcola, mese per mese, finché non si giunge al mese richiesto

Esempio

Con N=5:

Fib(1) = 1
Fib(2) = 1
Fib(3) = Fib(2)+Fib(1) = 1+1 = 2
Fib(4) = Fib(3)+Fib(2) = 2+1 = 3
Fib(5) = Fib(4)+Fib(3) = 3+2 = 5 coppie

Codifica

function FiboIter(N: Integer): LongInt;
Var
  I, A, B, C: LongInt;
begin
  if(N <= 2) then
    FiboIter:=1
  else
    begin
      A:=1;
      B:=1;
      for I:=3 to N do
        begin
          C:=A+B;
          A:=B;
          B:=C;
        end;
      FiboIter:=C;
    end;
end;

Complessità del problema

Collegamenti

www.vialattea.net/esperti/mat/fibonacci ViaLattea.net
www.liceoberchet.it/ricerche/sezioneaurea Liceo "G. Berchet"
www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci Dr. Ron Knott

Bibliografia

C. J. Snijders La sezione aurea Franco Muzzio Editore
T. A. Wentworth Crescita e forma Boringhieri

Numeri di Fibonacci - ApPuNtIdIuNiNfOrMaTiCo

Home • ECDL • Algoritmi • Java • Basi di dati • Seconda prova • Eccetera • Cerca nel sito

Precedente
SUPERIORE
Successiva