La successione consì definita: Q(1)=1, Q(2)=1, Q(N+2)=Q(N)+Q(N+1) illustrata a fianco, nota come successione di Fibonacci, è stata presentata nel "Liber abaci" da Leonardo Pisano (vissuto a cavallo del 1200 e noto come Fibonacci) come modello matematico del seguente "problema dei conigli": |
|
|||||||
«quante coppie di conigli verranno
prodotte in N mesi a partire da un'unica coppia se ogni mese ogni coppia
dà alla luce una nuova coppia che diventa produttiva a partire dal
secondo mese di vita?». Q(N) rappresenta la quantità di coppie presenti dopo N mesi. Completa l'elenco dei termini della successione fino a |
È facile verificare che i valori della successione sino a Q(11)
sono 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.
Si può generare la successione facilmente anche con un semplice script (vedi, recursion-C).
I valori sono ottenibili facilmente anche con
questa calcolatrice online. Ecco a destra i valori da | 233 + 144 = 377 89 + 144 = 233 89 + 55 = 144 34 + 55 = 89 34 + 21 = 55 13 + 21 = 34 13 + 8 = 21 5 + 8 = 13 5 + 3 = 8 2 + 3 = 5 2 + 1 = 3 1 + 1 = 2 |
Posso generare la successione di Fibonacci anche con WolframAlpha. Vedi qui.
Ecco il calcolo dei valori con R (in R i valori di una variabile indiciata A si ottengono mettendo l'indice tra parentesi quadre invece che tonde, e gli indici partono da 1, non da 0): | |
## Svuoto Q e le assegno i primi 1000 termini della succ. Q <- NULL Q[1] <- 1; Q[2] <- 1; for (i in 3:1000) Q[i] <- Q[i-2]+Q[i-1] Q[c(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)] # 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ## Rappresento graficamente i primi 10 termini plot(c(0,10),c(0,Q[10]),type="n",xlab="",ylab="") abline(h=0,v=0,col="blue") for(i in 1:10) points(i,Q[i]) # ovvero: n <- 1:10; points(n,Q[n]); lines(n,Q[n]) ## Ovvero (se si vuole calcolare un solo output): F <- function(n) {if(n<3) U <- 1 else {a <- b <- 1; for(i in 3:n) {U <- a+b; a <- b; b <- U}}; U} F(400); Q[400] # 1.760237e+83 1.760237e+83 ## Si poteva anche dare una definizione ricorsiva: | |
F2 <- function(n) if (n==1 | n==2) 1 else Recall(n-1)+Recall(n-2) ## Le uscite sarebbero state le stesse F2(10); F(10); Q[10] # 55 55 55 ## ma i tempi sarebbero stati molto più lunghi: sec <-proc.time()[3]; F2(20); sec2 <- proc.time()[3]-sec; sec2 # 0.09 sec <-proc.time()[3]; F2(21); sec2 <- proc.time()[3]-sec; sec2 # 0.15 sec <-proc.time()[3]; F2(22); sec2 <- proc.time()[3]-sec; sec2 # 0.25 sec <-proc.time()[3]; F2(23); sec2 <- proc.time()[3]-sec; sec2 # 0.4 sec <-proc.time()[3]; F2(24); sec2 <- proc.time()[3]-sec; sec2 # 0.66 sec <-proc.time()[3]; F2(25); sec2 <- proc.time()[3]-sec; sec2 # 1.08 0.15/0.09; 0.25/0.15; 0.4/0.25; 0.66/0.4; 1.08/0.66 # 1.666667 1.666667 1.6 1.65 1.636364 ## All'aumento di 1 dell'input il tempo è moltiplicato per circa ## 1.6, ossia il tempo cresce circa come 1.6^n. |
Infatti ogni calcolo viene ricondotto ad altri, ciascuno dei quali, se non ha un risultato, viene ricondotto ad altri, e così via. Hanno un andamento simile le uscite: il rapporto tra Q[n] e Q[n-1] tende a stabilizzarsi, e ad assumere il valore 1.6180339887498 . Perchè? Prova a rifletterci. In un esercizio successivo troverai la risposta.
print(c( Q[10]/Q[9], Q[20]/Q[19], Q[40]/Q[39], Q[80]/Q[79] ),15) # 1.61764705882353 1.61803396316671 1.61803398874989 1.61803398874989