Press ESC to close

La successione di Fibonacci

0 2295

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)

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))

Conclusion

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

4 – Stringhe in python

5 – Casting in python

6 – Input e print in python

7 – Primi esercizi in python

8 – Errori in Python

9 – Script Python

10 – Scambio di variabili in python

11 – Modulo math

12 – Operatori di confronto e booleani in python

Other stories

Algoritmo Euclideo

Next Story

Numero di Harshad

Previous Story