Serie di Fibonacci in Python | Codice, Algoritmo e Altro

Fibonacci Series in Python | Code, Algorithm and More

Introduzione

La serie di Fibonacci in python è una sequenza matematica che inizia con 0 e 1, con ogni numero successivo che è la somma dei due precedenti. In Python, generare la serie di Fibonacci non è solo un classico esercizio di programmazione ma anche un ottimo modo per esplorare soluzioni ricorsive e iterative.

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) per n > 1

Cos’è la serie di Fibonacci?

La serie di Fibonacci è una sequenza in cui ogni numero è la somma dei due numeri che lo precedono, a partire da 0 e 1.

Vuoi imparare Python gratuitamente? Esplora il nostro corso gratuito oggi stesso!

Formula matematica per la sequenza di Fibonacci

La formula matematica per calcolare la sequenza di Fibonacci è:

F(n) = F(n-1) + F(n-2)

Dove:

  • F(n) è l’n-esimo numero di Fibonacci
  • F(n-1) è il (n-1)-esimo numero di Fibonacci
  • F(n-2) è il (n-2)-esimo numero di Fibonacci

Definizione ricorsiva

La definizione ricorsiva della serie di Fibonacci dipende dal sistema ricorsivo.

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2) per n > 1

Quindi, ogni numero nella serie di Fibonacci è calcolato includendo i due numeri che lo precedono. Questo metodo ricorsivo continua a generare l’intera sequenza, a partire da 0 e 1.

Leggi anche: Le 10 principali applicazioni di Python nel mondo reale con esempi

Serie di Fibonacci ricorsiva in Python

Numero di Fibonacci ricorsivamente in Python utilizzando funzionalità ricorsive. Ecco un codice Python per calcolare l’n-esimo numero di Fibonacci utilizzando la ricorsione:

Def fibonacci(n):
    if n <= 0:
        return 0 
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci (n-2)
#import csv

Serie di Fibonacci iterativa in Python

Un metodo iterativo per calcolare i numeri di Fibonacci in Python implica l’uso di cicli per costruire la sequenza in modo iterativo.

Algoritmo iterativo di Fibonacci in Python:

def fibonacci_iterative(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    Else:
        fib_prev = 0  # Inizializza il primo numero di Fibonacci
        fib_current = 1  # Inizializza il secondo numero di Fibonacci
        For _ in range(2, n + 1):
            fib_next = fib_prev + fib_current  # Calcola il prossimo numero di Fibonacci
            fib_prev, fib_current = fib_current, fib_next  # Aggiorna i valori per la prossima iterazione 
        return fib_current
#import csv

Confronto con l’approccio ricorsivo

Base di distinzione Approccio ricorsivo Approccio iterativo
Efficienza Questo approccio è più efficiente per valori “n” grandi, calcolando i numeri di Fibonacci in modo iterativo e senza calcoli ridondanti. Questo approccio è meno efficiente, soprattutto per “n” grandi in quanto causa calcoli ridondanti.
Complessità temporale 0(n) (Lineare) 0 (2^n) (Esponenziale)
Complessità spaziale 0(1) (Costante) 0(n) (Lineare)

Memoizzazione per un Calcolo Efficiente

La memoizzazione è un metodo che velocizza i programmi o gli algoritmi informatici memorizzando i risultati di costose chiamate di funzione e restituendo il risultato memorizzato quando si verificano nuovamente gli stessi input. È utile nell’ottimizzazione dei calcoli di Fibonacci poiché l’approccio ricorsivo ricalcola molte volte gli stessi numeri di Fibonacci, portando a inefficienza.

Come la Memoizzazione Riduce i Calcoli Ridondanti

Nei calcoli di Fibonacci, senza memoizzazione, l’algoritmo ricorsivo ricalcola gli stessi numeri ancora e ancora. La memoizzazione risolve questo problema memorizzando i risultati. Quando la funzione viene chiamata nuovamente con lo stesso input, utilizza il risultato calcolato per il problema.

Implementazione della Memoizzazione in Python per Fibonacci

Ecco come si implementa la memoizzazione in Python per ottimizzare i calcoli di Fibonacci:

# Crea un dizionario per memorizzare i numeri di Fibonacci calcolati.
Fib_cache = {}
def fibonacci_memoization(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1

    # Controlla se il risultato è già presente nella cache.
    if n in fib_cache:
        return fib_cache[n]

    # Se non lo è, calcolalo in modo ricorsivo e memorizzalo nella cache.
    fib_value = fibonacci_memoization(n - 1) + fibonacci_memoization(n - 2)
    fib_cache[n] = fib_value

    return fib_value
#import csv

Programmazione Dinamica per la Serie di Fibonacci in Python

La programmazione dinamica è una strategia utilizzata per risolvere problemi suddividendoli in sottoproblemi più piccoli e risolvendo ciascun sottoproblema una sola volta, memorizzando i risultati per evitare calcoli ridondanti. Questo approccio è molto efficace per risolvere problemi complessi come il calcolo dei numeri di Fibonacci.

Spiegazione dell’Approccio della Programmazione Dinamica a Fibonacci:

La programmazione dinamica prevede di memorizzare i numeri di Fibonacci in un array o dizionario quando vengono calcolati, in modo che possano essere riutilizzati quando necessario. Invece di ricalcolare gli stessi numeri di Fibonacci, la programmazione dinamica li memorizza una volta e li recupera quando necessario.

Utilizzo di un Array o Dizionario per Memorizzare i Risultati Intermedi

L’approccio della programmazione dinamica può essere utilizzato sia con un array che con un dizionario (tabella hash) per memorizzare i numeri di Fibonacci intermedi.

def fibonacci_dynamic_programming(n):
    fib = [0] * (n + 1)  # Inizializza un array per memorizzare i numeri di Fibonacci.
    fib[1] = 1  # Imposta i casi base.
    
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]  # Calcola e memorizza i numeri di Fibonacci.
    return fib[n]  # Restituisce l'n-esimo numero di Fibonacci.
#import csv

Vantaggi della Programmazione Dinamica in Termini di Complessità Temporale

Il metodo della programmazione dinamica per il calcolo dei numeri di Fibonacci offre diversi vantaggi in termini di complessità temporale:

Complessità Temporale Ridotta: La programmazione dinamica riduce la complessità temporale dei calcoli di Fibonacci da esponenziale (O(2^n)) nell’approccio ricorsivo ingenuo a lineare (O(n)).

Riutilizzo Efficiente: Memorizzando i risultati intermedi, la programmazione dinamica evita calcoli ridondanti. Ogni numero di Fibonacci viene calcolato una volta e quindi recuperato dalla memoria quando necessario, migliorando l’efficienza.

Scalabilità Migliorata: Il metodo della programmazione dinamica rimane efficiente anche per valori grandi di “n”, rendendolo adatto per applicazioni pratiche.

Ottimizzazione dello Spazio per Fibonacci

Le strategie di ottimizzazione dello spazio per il calcolo dei numeri di Fibonacci mirano a ridurre l’utilizzo della memoria memorizzando solo i valori precedenti importanti anziché l’intera sequenza. Queste tecniche sono particolarmente utili quando l’efficienza della memoria è una preoccupazione.

Utilizzo di Variabili per Memorizzare Solo i Valori Precedenti Necessari

Una delle strategie di ottimizzazione dello spazio più utilizzate per Fibonacci consiste nell’utilizzare variabili per memorizzare solo i due numeri di Fibonacci più recenti anziché un array per memorizzare l’intera sequenza.

def fibonacci_space_optimized(n):
    if n <= 0:
        return 0
    elif n == 1:
        return 1

    fib_prev = 0  # Inizializza il numero di Fibonacci precedente.
    fib_current = 1  # Inizializza il numero di Fibonacci corrente.

    for _ in range(2, n + 1):
        fib_next = fib_prev + fib_current  # Calcola il prossimo numero di Fibonacci.
        fib_prev, fib_current = fib_current, fib_next  # Aggiorna i valori per la prossima iterazione.

    return fib_current  # Restituisce l'n-esimo numero di Fibonacci.

#import csv

Compromessi tra complessità spaziale e temporale

Le tecniche ottimizzate in termini di spazio per il calcolo dei numeri di Fibonacci comportano dei compromessi tra la complessità spaziale e temporale:

Efficienza spaziale: Le approcci ottimizzati in termini di spazio utilizzano meno memoria perché memorizzano solo poche variabili (in genere due) per tenere traccia degli ultimi numeri di Fibonacci. Questo è relativamente efficiente in termini di spazio, rendendolo adatto per ambienti con limitazioni di memoria.

Efficienza temporale: Sebbene queste strategie non siano lineari (O(n)) in termini di complessità temporale, potrebbero essere leggermente più lente rispetto alla programmazione dinamica con un array a causa delle assegnazioni di variabili. Tuttavia, la differenza è generalmente trascurabile per valori pratici di “n”.

Generazione dei numeri di Fibonacci fino a N

La generazione dei numeri di Fibonacci fino a N in Python può essere fatta attraverso un ciclo. Ecco un codice Python che genera i numeri di Fibonacci fino a N:

def genera_fibonacci(restrizione):
    if restrizione <= 0:
        return []

    sequenza_fibonacci = [0, 1]  # Inizializza con i primi due numeri di Fibonacci.
    while True:
        prossimo_fib = sequenza_fibonacci[-1] + sequenza_fibonacci[-2]
        if prossimo_fib > restrizione:
            break
        sequenza_fibonacci.append(prossimo_fib)
    return sequenza_fibonacci
#import csv

Applicazioni della generazione di sequenze di Fibonacci in un intervallo

  • Analisi di serie di numeri: Generare i numeri di Fibonacci entro un limite può essere utile per analizzare e studiare sequenze di numeri, identificare pattern ed esplorare proprietà matematiche.
  • Analisi delle prestazioni: In informatica e valutazione degli algoritmi, le sequenze di Fibonacci possono essere utilizzate per analizzare le prestazioni degli algoritmi e delle strutture dati, principalmente in termini di complessità temporale e spaziale.
  • Testing delle applicazioni: Nel testing delle applicazioni, i numeri di Fibonacci possono essere utilizzati per creare casi di test con diverse dimensioni di input per valutare le prestazioni e la robustezza delle applicazioni software.
  • Modellazione finanziaria: Le sequenze di Fibonacci hanno applicazioni nella modellazione finanziaria, in particolare nello studio delle tendenze di mercato e dei movimenti dei prezzi in settori come il trading azionario e l’analisi degli investimenti.

Applicazioni della serie di Fibonacci

La sequenza di Fibonacci ha molte applicazioni nel mondo reale. Nella natura, descrive l’arrangiamento di foglie, petali e semi nelle piante, esemplificando un’imballaggio efficiente. Il rapporto aureo derivato dalle proporzioni di Fibonacci viene utilizzato per creare composizioni e design esteticamente desiderabili. Nella tecnologia, i numeri di Fibonacci giocano un ruolo nell’ottimizzazione degli algoritmi, come la programmazione dinamica e la memoizzazione, migliorando le prestazioni in responsabilità come il calcolo di valori di Fibonacci massicci o la risoluzione di problemi di ottimizzazione. Inoltre, le sequenze di Fibonacci vengono utilizzate nella modellazione finanziaria, contribuendo all’analisi di mercato e alla previsione delle tendenze dei prezzi. Queste applicazioni del mondo reale sottolineano l’importanza della serie di Fibonacci in matematica, natura, arte e risoluzione dei problemi.

Rapporto aureo di Fibonacci

Il rapporto aureo di Fibonacci, spesso indicato come Phi (Φ), è un intervallo irrazionale approssimativamente uguale a 1,61803398875. Questa costante matematica è profondamente intrecciata con la sequenza di Fibonacci. Man mano che si procede nella sequenza di Fibonacci, il rapporto tra i numeri di Fibonacci consecutivi approssima sempre di più Phi. Questa connessione dà origine a principi estetici nel design, dove gli elementi sono spesso proporzionati a Phi, creando composizioni visivamente armoniose. Esempi pratici includono l’architettura del Partenone, opere d’arte come la Mona Lisa e le proporzioni del viso umano, mettendo in evidenza l’ampio utilizzo del rapporto aureo nella creazione di design esteticamente affascinanti ed equilibrati in numerosi settori, dall’arte e l’architettura al design grafico e web.

Fibonacci nel trading e nella finanza

Il ruolo di Fibonacci nel trading e nella finanza consiste nei livelli di ritracciamento ed estensione di Fibonacci nell’analisi tecnica. I trader utilizzano questi livelli per identificare potenziali punti di supporto e resistenza nei mercati finanziari. La serie di Fibonacci aiuta a prevedere le tendenze del mercato azionario identificando i livelli di prezzo chiave in cui sono probabili inversioni o estensioni. Le tecniche di trading di Fibonacci prevedono l’utilizzo di questi livelli in combinazione con indicatori tecnici per prendere decisioni di trading consapevoli. I trader cercano regolarmente modelli di Fibonacci, come il rapporto aureo, per aiutare a prevedere i movimenti dei prezzi.

Conclusioni

Pur sembrando radicata nella matematica, la serie di Fibonacci ha anche rilevanza nella scienza dei dati. Comprendere i principi di generazione delle sequenze e il riconoscimento di pattern intrinseci alla serie di Fibonacci può aiutare i data scientist a riconoscere e analizzare pattern ricorrenti nei dataset, un aspetto fondamentale dell’analisi dei dati e della modellazione predittiva nella scienza dei dati. Iscriviti al nostro corso gratuito di Python per migliorare le tue competenze di Python.

Domande Frequenti