Soluzione 1
Il primo esempio di programmazione nella home page di python.org visualizza la sequenza dei numeri di Fibonacci minori di 1000 (parte da 0…):
def fib(n): a, b = 0, 1 while a < n: print(a, end=' ') a, b = b, a+b print() fib(1000) # I numeri di Fibonacci minori di 1000
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987
Soluzione 2
Algoritmo iterativo: a partire dai valori noti (1, 1) si calcola un nuovo valore finché non si giunge all’indice richiesto
def fibonacci(n): if(n <= 2): return 1 else: a=1 b=1 for i in range(n-2): c=a+b a=b b=c return c fibonacci(10) # Il 10° numero di Fibonacci
Soluzione 3
Codice più corto
def fibonacci(n): a=1 b=1 for i in range(n-2): c=a+b a=b b=c return b fibonacci(10) # Il 10° numero di Fibonacci
Soluzione 4
Algoritmo ricorsivo: è molto sintetico
def fibonacci(n): if(n <= 2): return 1 else: return fibonacci(n-1)+fibonacci(n-2)
Soluzione 5
Con formula: non è necessario alcun algoritmo iterativo o ricorsivo se si utilizza la formula
import math def fibonacci(n): r5=math.sqrt(5) r =1/r5 * (math.pow((1+r5)/2, n) - math.pow((1-r5)/2, n)) return round(r)
Soluzione 6
Il contributo del secondo termine è così piccolo che può essere trascurato: si ottiene il valore esatto calcolando il primo termine e arrotondando all’intero più vicino
import math def fibonacci(n): r5=math.sqrt(5) r =1/r5 * math.pow((1+r5)/2, n) return round(r)