La successione di Fibonacci

La successione di Fibonacci

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

Successione di Fibonacci con Scratch

Successione di Fibonacci con Scratch

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.

fibonacci in scratch

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 terzo che 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:

 

Fibonacci 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.

Alcuni link utili:

Numeri primi in Scratch

Massimo fra tre numeri in Scratch

Minimo tra 3 numeri in Scratch

Numeri perfetti con algobuild

Numeri amicabili

Selecion sort in Scratch

Esempio di successione di Fibonacci con Algobuild

La successione di Fibonacci in C++

Sviluppo con Algobuild della successione di Fibonacci

La successione di Fibonacci in C

La successione di Fibonacci in C

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

Link Utili:

Esempio di successione di Fibonacci con Scratch

Successione di Fibonacci in C++

Sviluppo con Algobuild della successione di Fibonacci

La successione di Fibonacci con Algobuild

La successione di Fibonacci con Algobuild

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

successione di fibonacci

Alcuni link utili

Indice argomenti diagramma a blocchi

Numeri primi da 1 a 100

Array con algobuild

Divisori di un numero con algobuild

Algoritmi di selezione sugli angoli

Algoritmi di selezione

Triangoli con algobuild

Fibonacci con algobuild

Serie buffa con algobuild

Numeri amicabili con algobuild

Numeri perfetti con algobuild

Massimo fra tre numeri

Minore fra tre numeri

Successione di Fibonacci in C++

Successione di Fibonacci in C++

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.

Alcuni link utili

Esempio di successione di Fibonacci con Scratch

Sviluppo con Algobuild della successione di Fibonacci

Operatori logici in C++

Esercizi con switch case in C++

Switch case in C++

If else in C++

Casting in C++

Variabili in C++

Tutorial C++