Sviluppiamo l’algoritmo della successione di Fibonacci in Python. Ricordiamone la definizione.
La successione di Fibonacci è una successione di numeri interi positivi, in cui ciascun numero, a cominciare dal terzo, è la somma dei due precedenti eccetto i primi due che sono 1, 1.
Ad esempio se N=9, i termini della successione sono: 1, 1, 2, 3, 5, 8, 13, 21, 34.
La successione di Fibonacci in Python
Realizziamo dunque un algoritmo dapprima iterativo.
Prendere in input un numero N e visualizzare gli N termini della successione di Fibonacci.
Per realizzare questo algoritmo innanzitutto prendiamo due variabili a e b e ad entrambe assegniamo il valore 1. Creiamo così i primi due termini della successione che andremo subito a stampare.
Quindi, utilizziamo un ciclo for per visualizzare gli N termini con un indice i che varia da 0 ad N-1. Dopo, all’interno del ciclo calcoliamo il terzo termine c e poi scambiamo a con b e b con c. Infine stampiamo c.
Ecco dunque una possibile soluzione:
n = int(input('Quanti numeri?: ' ))
a, b = 1, 1
print(a)
print(b)
for i in range(N):
c = a + b
a = b
b = c
print(c, end=' ')Una volta capito il procedimento, riscriviamo l’algoritmo sulla successione di Fibonacci in Python in maniera più elegante. Dunque evitiamo un pò di istruzioni, come ad esempio i print iniziali e realizziamo lo scambio delle variabili in un’unica riga.
Ecco dunque la soluzione:
n = int(input('Quanti numeri?: ' ))
a, b = 1, 1
for i in range(n):
print(a, end=' ')
a, b = b, a + b
print()Potremmo anche definire una funzione da richiamare all’occorrenza.
def print_fibonacci(length):
a = 1
b = 1
for i in range (length):
print(a, end=" ")
a, b = b, a + b
n = int(input('Quanti numeri?: ' ))
while(n < 0):
n = int(input('Quanti numeri? Inserisci un numero positivo: ' ))
print_fibonacci(n)Migliora le tue capacità di programmazione Python seguendo i nostri corsi in diretta!
La successione di Fibonacci in Python – soluzione ricorsiva
Implementiamo anche una soluzione ricorsiva dell’algoritmo. Ricordiamo che si ha ricorsione quando all’inerno della propria definizione si richiama la funzione stessa. Nel nostro caso, infatti, chiamiamo la funzione rec_fib all’interno della stessa funzione rec_fib.
def rec_fib(n):
if n > 1:
return rec_fib(n - 1) + rec_fib(n - 2)
return n
n = int(input('How many numbers?: ' ))
for i in range(1, n+1):
print(rec_fib(i))Conclusione
In questa lezione abbiamo studiato una soluzione iterativa ed una ricorsiva all’algoritmo per la successione di Fibonacci in Python. Nelle prossime lezioni introdurremo il concetto di lista in Python.
Alcuni link utili
Indice tutorial sul linguaggio Python
1 – Introduzione al linguaggio Python
2 – Le variabili
3 – Operatori aritmetici e di assegnazione
8 – Errori in Python
9 – Script Python
10 – Scambio di variabili in python
11 – Modulo math
12 – Operatori di confronto e booleani in python