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.
Esempio di programma che visualizza la successione di Fibonacci con Scratch.
Ricordiamo che la successione di Fibonacci è una successione di numeri interi positivi in cui ciascun numero a cominciare dal terzo è la somma dei due precedenti e i primi due sono 1, 1.
Ad esempio se N=9 avremo i seguenti termini 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34.
Esempio di successione di Fibonacci con Scratch
Con Scratch è possibile realizzare un algoritmo che riesce a calcolare gli N termini della successione.
Per svilupparlo prendiamo uno sprite qualsiasi, ad esempio il gattino classico di Scratch e gli facciamo dire un messaggio del tipo: “Salve! Creiamo insieme la successione di Fibonacci”.
Successivamente chiediamo quanti termini della successione di Fibonacci visualizzare.
Permettiamo l’inserimento di valori per N maggiori di 1, in modo da visualizzare almeno due termini della successione di Fibonacci.
Per sviluppare questo controllo in Scratch inseriamo un ripeti fino a quando N è maggiore di 1, in questo modo se viene inserito un numero negativo si richiede nuovamente l’inserimento.
Creiamo poi due variabili di nome primo e secondo che rappresentano i primi due termini della successione di Fibonacci. Settiamo le due variabili appena create a 1 e le visualizziamo in output.
Dopo creiamo una variabile contatore che facciamo partire da 2 in quanto i primi due termini della successione sono stati già visualizzati.
Realizziamo dunque un ciclo che si ripete fino a quando il contatore (che abbiamo detto parte da due) raggiunge N e calcoliamo all’interno del ciclo il terzo numero della successione di Fibonacci. Creiamo quindi una variabile terzoche poniamo uguale alla somma di primo più secondo.
Scambiamo poi le variabili ponendo primo uguale a secondo e secondo uguale a terzo.
Di seguito l’algoritmo completo con Scratch:
Non ci resta che avviare il programma e provarlo!
Chiaramente ci possono essere tante altre soluzioni per la realizzazione dell’algoritmo. Proponete pure la vostra nei commenti sotto.
Sviluppiamo la successione di Fibonacci in linguaggio C.
Iniziamo con il chiedere in input N numeri per poi visualizzare a video i primi N numeri della successione di Fibonacci.
La successione di Fibonacci
Ricordiamo che la successione di Fibonacci è una successione di numeri interi positivi in cui ciascun numero a cominciare dal terzo è la somma dei due precedenti e i primi due sono 1, 1
Ad esempio se N=9 avremo i seguenti termini 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34
#include <stdio.h>
int main() {
int i,N,primo,secondo,terzo;
printf("Quanti numeri della successione vuoi visualizzare? ");
scanf("%d", &N);
primo=1;
secondo=1;
printf("%d\n",primo);
printf("%d\n",secondo);
for(i=2;i<N;i++) {
terzo=primo+secondo;
primo=secondo;
secondo=terzo;
printf("%d\n",terzo);
}
}
La successione di Fibonacci è una successione di numeri interi positivi in cui ciascun numero a cominciare dal terzo è la somma dei due precedenti e i primi due sono 1, 1.
Quindi ad esempio la successione di N numeri dove N è uguale a 10 sarà questa:
1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55
Per lo sviluppo dell’algoritmo prendiamo due variabili primo e secondo e ad entrambe assegniamo il valore 1, in quanto rappresentano i primi due termini della successione di Fibonacci, quindi avremo:
primo=1
secondo=1
Visualizziamo in output le due variabili.
Successione di Fibonacci
A questo punto prendiamo in input N che indica quanti numeri della successione di Fibonacci vogliamo calcolare. Di volta in volta sarà l’utente a decidere quanti termini vorrà visualizzare. Poniamo che N sia almeno uguale a 2, per poter stampare almeno due termini della successione di Fibonacci e quindi con un ciclo do-while richiediamo N qualora fosse minore di 2. In questo modo l’utente è obbligato per andare avanti ad inserire un numero maggiore o uguale a 2.
DO_WHILE IN N END DO_WHILE
Creiamo un ciclo definito che duri N volte meno 2, in quanto i primi due numeri sono stati inseriti (primo e secondo). Utilizziamo per tale scopo una variabile contatore che chiamiamo i e che facciamo partire da 2, per i motivi suddetti.
All’interno del ciclo calcoliamo il terzo numero della successione di Fibonacci, usando una variabile di nome terzo che poniamo uguale alla somma di primo più secondo, cambiamo le variabili primo che poniamo uguale a secondo e secondo che poniamo uguale a terzo, in questo modo si calcolano tutti i termini della successione di Fibonacci finché il contatore non raggiunge N.
terzo=primo + secondo
primo=secondo
secondo=terzo
Visualizziamo in output la variabile terzo e abbiamo terminato l’algoritmo.
Di seguito la pseudocodifica e il diagramma di flusso della successione di Fibonacci sviluppato con Algobuild:
PROG main
ASSIGN primo=1
ASSIGN secondo=1
OUT primo
OUT secondo
DO_WHILE //N<2
IN N
END DO_WHILE N<2
ASSIGN I=2
WHILE I<=N
ASSIGN terzo=primo+secondo
OUT terzo
ASSIGN primo=secondo
ASSIGN secondo=terzo
ASSIGN I=I+1
END WHILE //I<=N
END PROG //main
Sviluppiamo adesso l’algoritmo per il calcolo della successione di Fibonacci in C++.
Questo è un altro classico esercizio che viene generalmente creato a scopo didattico.
Per farlo, occorre ricordare che la successione di Fibonacci è una successione di numeri interi positivi in cui ciascun numero a cominciare dal terzo è la somma dei due precedenti e i primi due sono 1, 1.
Ad esempio se N=9 avremo i seguenti termini 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34
Programma per lo sviluppo della successione di Fibonacci in C++
Chiediamo in input di inserire quanti numeri visualizzare e facciamo un controllo su N che quantomeno deve essere maggiore o uguale a 3, in modo tale da visualizzare almeno i primi 3 termini.
#include <iostream>
using namespace std;
int main () {
int i, N, primo=1, secondo=1, terzo;
do {
cout<<"Quanti numeri vuoi inserire?: ";
cin>>N;
} while (N<3);
cout<<primo<<","<<secondo;
for(i=2;i<N;i++){
terzo=primo+secondo;
primo=secondo;
secondo=terzo;
cout<<","<<terzo;
}
return 0;
}
Chiaramente questo è solo un esempio di risoluzione dell’algoritmo sulla successione di Fibonacci in C++, proponete pure la vostra nei commenti sotto.
