Q(1) = 1, Q(2) = 1, Q(N+2) = Q(N)+Q(N+1) descrive la successione Q(1), Q(2), Q(3), Q(4), Q(5), Q(6), ...
i cui valori sono 1, 1, 2, 3, 5, 8, ... È 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
•
Scrivi un programma, nel linguaggio che preferisci, che stampi i valori fino a
Q(1) = 1,
Q(2) = 1,
Q(3) = 1 + 1 = 2,
Q(4) = 1 + 2 = 3,
Q(5) = 2 + 3 = 5,
Q(6) = 3 + 5 = 8,
Vediamo i programmi prima nel semplice Basic (vedi QUI), ma si poteva usare un qualunque linguaggio:
Uno:
10 print "1 1 "; : a=1 : b=1 : c=a+b : n=3 20 for i=3 to 20 : print c+" "; : a=b : b=c : c=a+b : n=n+1 : next 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
Due:
10 print "Q(1) = 1": print "Q(2) = 1"
20 a=1 : b=1 : c=a+b : n=3
30 for i=3 to 20
40 print "Q("+n+") = "+a+" + "+b+" = "+c
50 a=b : b=c : c=a+b : n=n+1
60 next
Q(1) = 1
Q(2) = 1
Q(3) = 1 + 1 = 2
Q(4) = 1 + 2 = 3
Q(5) = 2 + 3 = 5
Q(6) = 3 + 5 = 8
Q(7) = 5 + 8 = 13
Q(8) = 8 + 13 = 21
Q(9) = 13 + 21 = 34
Q(10) = 21 + 34 = 55
Q(11) = 34 + 55 = 89
Q(12) = 55 + 89 = 144
Q(13) = 89 + 144 = 233
Q(14) = 144 + 233 = 377
Q(15) = 233 + 377 = 610
Q(16) = 377 + 610 = 987
Q(17) = 610 + 987 = 1597
Q(18) = 987 + 1597 = 2584
Q(19) = 1597 + 2584 = 4181
Q(20) = 2584 + 4181 = 6765
Tre:
10 input N
20 a=1 : b=1 : c=a+b : k=3
30 for i=3 to N-1
40 a=b : b=c : c=a+b : k=k+1
50 next
60 print "Q("+N+") = " + c
? 80
Q(80) = 23416728348467684
Vediamo come usare dei programmi in JavaScript (vedi):
Uno:
q1=1; q2=1; document.write(q1+" "+q2+" "); n=20
for(i=0; i<n-2; i=i+1) {s=q1+q2; q1=q2; q2=s; document.write(q2+" ")}
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
Due:
a=1; b=1; c=a+b; n=3
document.write("Q(3) = "+a+"+"+b+" = "+c+"<br>")
for(i=4;i<=20;i=i+1)
{ a=b; b=c; c=a+b; n=n+1
document.write("Q("+n+") = "+a+"+"+b+" = "+c+"<br>") }
Q(3) = 1+1 = 2
Q(4) = 1+2 = 3
Q(5) = 2+3 = 5
Q(6) = 3+5 = 8
Q(7) = 5+8 = 13
Q(8) = 8+13 = 21
Q(9) = 13+21 = 34
Q(10) = 21+34 = 55
Q(11) = 34+55 = 89
Q(12) = 55+89 = 144
Q(13) = 89+144 = 233
Q(14) = 144+233 = 377
Q(15) = 233+377 = 610
Q(16) = 377+610 = 987
Q(17) = 610+987 = 1597
Q(18) = 987+1597 = 2584
Q(19) = 1597+2584 = 4181
Q(20) = 2584+4181 = 6765
Tre:
N=80
q1=1; q2=1; n=80
for(i=0; i<n-2; i=i+1) {s=q1+q2; q1=q2; q2=s}; document.write(q2)
23416728348467684 (≈ 2.3*10^16)
Facciamo un altro esperimento. Stampiamo il rapporto tra Q(N) e Q(N-1). Facciamolo (ad es. in Basic) per diversi valori di N:
10 a=1 : b=1 : c=a+b : n=3
20 for i=3 to 50
30 if i=30 or i=35 or i=40 or i=45 or i=50 then print "Q(";n;")/Q(";n-1;") = ";c/b
40 a=b : b=c : c=a+b : n=n+1
50 next
Q(30)/Q(29) = 1.6180339887482036
Q(35)/Q(34) = 1.6180339887499087
Q(40)/Q(39) = 1.6180339887498947
Q(45)/Q(44) = 1.618033988749895
Q(50)/Q(49) = 1.618033988749895
Le uscite si stabilizzano su 1.618033988749895. Proviamo a vedere se esso ha qualche particolarità. Ricorriamo a WolframAlpha. Ottengo:
Se introduco phi ottengo "is the golden ratio" = (1+√5)/2.
In italiano viene chiamato "rapporto aureo". Se calcolo (1+√5)/2 ottengo proprio 1.618033988749894848204...