I numeri di Fibonacci sono una sequenza particolare in cui il primo valore è pre-dichiarato come 0 e il secondo valore è pre-dichiarato come 1. Il resto dei numeri viene prodotto da questi due sommando i due numeri precedenti. Tutti i numeri di Fibonacci sono numeri interi positivi, a partire da 0. I primi dodici numeri di Fibonacci e come si ottengono sono i seguenti:
0
1
1 + 0 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
21 + 13 = 34
34 + 21 = 55
55 + 34 = 89
Senza le espressioni di somma, questi numeri di Fibonacci possono essere inseriti in una tabella come segue:
| 0 | 1 | 1 | Due | 3 | 5 | 8 | 13 | ventuno | 3. 4 | 55 | 89 |
| 0 | 1 | Due | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | undici |
La prima riga contiene i numeri di Fibonacci. La seconda riga ha indici a base zero, supponendo che i numeri di Fibonacci siano in una matrice.
I numeri di Fibonacci possono essere prodotti in tempo O(n) e in tempo O(1). In queste espressioni di complessità temporale, n indica n operazioni principali e 1 indica 1 operazione principale. Con O(n), vengono prodotti n numeri di Fibonacci, a partire da 0. Con O(1), viene prodotto un numero di Fibonacci da un indice corrispondente. Ecco perché basta un'operazione principale invece di n operazioni principali.
Lo scopo di questo articolo è spiegare come produrre numeri di Fibonacci, in entrambi i casi, usando Python.
Formula per un numero di Fibonacci
La definizione formale di un numero di Fibonacci è:
dove F n è il numero di Fibonacci all'indice n Se n è 1, allora solo 0 verrebbe stampato come numero di Fibonacci. Se n è 2, allora 0 e 1 verrebbero stampati come numeri di Fibonacci, in quest'ordine. Se n è 3, allora 0, 1 e 1 verrebbero stampati come numeri di Fibonacci in quell'ordine. Se n è 4, allora 0, 1, 1 e 2 verrebbero stampati come numeri di Fibonacci in quell'ordine. Se n è 5, allora 0, 1, 1, 2 e 3 verrebbero stampati come numeri di Fibonacci, in quest'ordine. Se n è 6, allora 0, 1, 1, 2, 3 e 5 verrebbero stampati come numeri di Fibonacci, in quell'ordine – e così via. La funzione Python per produrre i primi n numeri di Fibonacci è: Inizia creando una matrice di n elementi, tutti inizializzati a zero. Questa matrice conterrà i numeri di Fibonacci. Il primo numero di Fibonacci, 0, è già lì. Il secondo numero di Fibonacci, 1, è assegnato dall'istruzione successiva (nella funzione). Poi c'è il ciclo for, che parte dall'indice 2 fino a poco prima del n. Ha la dichiarazione: Questo somma i due numeri immediatamente precedenti. Il codice per chiamare la funzione e stampare i primi dodici numeri di Fibonacci può essere: N = 12 L'uscita è: Esiste una formula matematica che mette in relazione un indice in base zero con il suo numero di Fibonacci corrispondente. La formula è: Si noti che sul lato destro dell'equazione, non è la radice quadrata di 5 che viene elevata alla potenza n; è l'espressione tra parentesi che viene elevata alla potenza n. Ci sono due di queste espressioni. Se n è 0, Fibn sarebbe 0. Se n è 1, Fib n sarebbe 1. Se n è 2, Fib n sarebbe 1. Se n è 3, Fib n sarebbe 2. Se n è 4, Fib n sarebbe 3 – e così via. Il lettore può verificare matematicamente questa formula sostituendo valori diversi per n e valutando. n è un indice in base zero in questa formula. Il codice Python per questa formula è: importa la matematica Il modulo matematico è stato importato. Ha la funzione radice quadrata. L'operatore, ** è utilizzato per l'alimentazione. La funzione fibNo() implementa direttamente la formula. Una chiamata e una stampa adatte per la funzione fibNo() sono: N = 11 L'uscita è: È possibile rimuovere le cifre decimali non necessarie dalla risposta. Tuttavia, questa è una discussione per un'altra volta. Se sono richiesti numeri di Fibonacci diversi per n indici diversi, la funzione fibNo() deve essere chiamata una volta per ciascuno degli n indici per restituire i diversi numeri di Fibonacci corrispondenti. Il seguente programma esegue questa operazione per gli indici in base zero, da 7 a 9 (inclusi): importa la matematica L'uscita è: Nota il modo in cui il ciclo for è stato codificato in Python. Il primo indice è 7. L'indice successivo è 8 e l'ultimo indice è 9. 10 nell'argomento intervallo è 9 + 1. Il valore nella posizione 10 deve essere l'ultimo indice in base zero più 1. Il primo argomento, 7, è l'indice iniziale in base zero. I numeri di Fibonacci sono una particolare sequenza di numeri interi (interi positivi). Inizia con 0, seguito da 1 incondizionatamente. Il resto dei numeri viene sviluppato da lì sommando i due numeri immediatamente precedenti. Per ottenere i primi n numeri di Fibonacci, accetta 0 e 1 come i primi due, quindi per il resto, usa un ciclo for con un'istruzione come: che somma i due numeri immediatamente precedenti. Per ottenere un solo numero di Fibonacci da un indice n a base zero, utilizzare la formula: Produzione di numeri di Fibonacci in tempo O(n).
arri = [ 0 ] * ( n )
arr [ 1 ] = 1
per io in gamma ( Due , n ) :
arr [ io ] = arr [ io - 1 ] + arr [ io - Due ]
Restituzione arr
A = Fibonacci(N)
per i nell'intervallo (N):
stampa (A[i], fine=' ')
Stampa() Produzione di un numero di Fibonacci in tempo costante
FibN = ( ( ( 1 +math.sqrt ( 5 ) ) / Due ) ** n - ( ( 1 -math.sqrt ( 5 ) ) / Due ) ** n ) / math.sqrt ( 5 )
Restituzione Fib N
destra = fibNo(N)
stampa (ret)
FibN = ( ( ( 1 +math.sqrt ( 5 ) ) / Due ) ** n - ( ( 1 -math.sqrt ( 5 ) ) / Due ) ** n ) / math.sqrt ( 5 )
Restituzione Fib N
per io in gamma ( 7 , 10 ) :
Stampa ( fib n ( io ) , fine = ' ' )
Stampa ( )
Conclusione
