Numero di Fibonacci, verificare se un numero è Fibonacci

In questa lezione analizzeremo alcuni algoritmi per verificare se un numero appartiene alla successione di Fibonacci.

Nella lezione precedente abbiamo studiato come stampare una successione di Fibonacci di lunghezza variabile, di volta in volta decisa dall’utente.

Abbiamo sviluppato sia una soluzione iterativa sia ricorsiva, utilizzando anche le funzioni.

In questa lezione invece chiediamo ad utente di inserire un intero ed il programma sarà in grado di dire se è un numero di Fibonacci oppure no.

Svilupperemo delle soluzioni differenti e le analizzeremo.

Numero di Fibonacci – prima soluzione

Studiamo un primo approccio ad una possibile soluzione al problema proposto.

La prima cosa che ci viene in mente, senza conoscere nessuna regola, è quella di generare i numeri di Fibonacci fino all’input inserito dall’utente e verificare se questo numero è contenuto in esso.

Sviluppiamo la soluzione facendo uso di una soluzione iterativa che si fermerà quando la condizione sarà soddisfatta, nel nostro caso quando si trova il numero inserito oppure si generano dei numeri non superiori ad esso.

Creiamo una variabile sentinella, che chiameremo ad esempio trovato e la impostiamo a False. Dopo, questa variabile cambierà il suo valore, diventando True solo se il valore è compreso nella successione.

Ecco dunque una possibile soluzione:


def check_fib(num):
    trovato = False

    a = 1
    b = 1
    c = a + b
    print(a,  end=' ')
    print(b,  end=' ')

    while(c <= num):
        print(c, end=' ')
        a = b
        b = c
        c = a + b        
        if(c == num):
            trovato = True

    if(trovato):
        print('trovato')
    else:
        print('non trovato')
        

n = int(input('Inserisci un numero: ' ))
check_fib(n)

Numero di Fibonacci – seconda soluzione

In questa seconda soluzione applichiamo invece delle note regole matematiche.

In particolare si dice che N è un numero di Fibonacci se e solo se 5 N^2 + 4 oppure 5 N^2 – 4 è un numero quadrato.

Sviluppiamo dunque un algoritmo che soddisfi queste condizioni importando il modulo math al fine di poter utilizzare la funzione radice quadrata (sqrt). Se la radice quadrata è un intero allora vuole dire che è un numero quadrato e dunque appartiene alla successione, altrimenti non vi appartiene.


def check_fib(n):
    import math
    a = (5 * (n**2)) + 4
    b = (5 * (n**2)) - 4
    return (math.sqrt(a)).is_integer() or (math.sqrt(b)).is_integer()

n = int(input('Inserisci un numero: ' ))
result = check_fib(n)
if (result):
    print('il numero è di Fibonacci')
else:
    print('il numero non è di Fibonacci')

Conclusione

In questa lezione abbiamo appreso come verificare se un numero appartiene o no alla sequenza di Fibonacci. Nelle prossime lezioni parleremo di liste in Python.