Numeri di fibonacci in lingua Python

“Se 0 viene aggiunto a 1, la risposta sarebbe 1. Se la risposta 1 e l'addend (non il rialzo) vengono aggiunti insieme, la nuova risposta sarebbe 2. Se questa nuova risposta e il suo addend vengono aggiunte insieme, la risposta sarebbe 3. Se questa nuova risposta e il suo addend vengono aggiunte insieme, la risposta sarebbe 5."

I numeri di fibonacci sono una sequenza particolare in cui il primo valore è pre-declassato come 0 e il secondo valore è pre-declassato come 1. Il resto dei numeri è prodotto da questi due aggiungendo i due numeri precedenti. Tutti i numeri di Fibonacci sono numeri interi positivi, a partire da 0. I primi dodici numeri di Fibonacci e il modo in cui sono ottenuti 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 messi in una tabella come segue:

0	1	1	2	3	5	8	13	21	34	55	89
0	1	2	3	4	5	6	7	8	9	10	11

La prima riga ha i numeri Fibonacci. La seconda riga ha indici a base zero, supponendo che i numeri di Fibonacci siano in un array.

I numeri di Fibonacci possono essere prodotti nel tempo di O (n) e in O (1). In queste espressioni di complessità temporale, n significa n operazioni principali e 1 significa 1 operazione principale. Con O (n), vengono prodotti numeri di n fibonacci, a partire da 0. Con O (1), un numero di fibonacci viene prodotto da un indice corrispondente. Ecco perché ci vuole solo un'operazione principale anziché n operazioni principali.

Lo scopo di questo articolo è di 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 al n basato sullo zero

Producendo numeri di fibonacci in o (n) tempo

Se n è 1, solo 0 verrebbe stampato come numero di fibonacci. Se n è 2, allora 0 e 1 verrebbero stampati come numeri di fibonacci, in quell'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 quell'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 il primo numero di n fibonacci è:

def fibonacci (n):
arr = [0] * (n)
arr [1] = 1
per i nell'intervallo (2, n):
arr [i] = arr [i - 1] + arr [i - 2]
RITORNO ARR

Inizia creando una matrice di n elementi, tutti inizializzati su zeri. Questo array terrà i numeri Fibonacci. Il primo numero di fibonacci, 0, è già lì. Il secondo numero di fibonacci, 1, è assegnato dalla prossima istruzione (nella funzione). Poi c'è il per loop, che inizia dall'indice 2 a poco prima di N. Ha la dichiarazione:

arr [i] = arr [i - 1] + arr [i - 2]

Questo aggiunge i due numeri precedenti immediati.

Codice per chiamare la funzione e stampare i primi dodici numeri di fibonacci può essere:

N = 12
A = fibonacci (n)
per i in gamma (n):
Stampa (a [i], end = ")
stampa()

L'output è:

0 1 1 2 3 5 8 13 21 34 55 89

Producendo un numero di fibonacci in tempo costante

Esiste una formula matematica che mette in relazione un indice basato su zero con il corrispondente numero di fibonacci. La formula è:

Si noti che sul lato destro dell'equazione, non è la radice quadrata di 5 che viene sollevata al potere n; è l'espressione tra parentesi che viene sollevata al potere 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 questa formula matematicamente sostituendo valori diversi per N e valutando. n è un indice basato su zero in questa formula.

Il codice Python per questa formula è:

Importa matematica

def fibno (n):
FIBN = (((1+matematica.sqrt (5))/2) ** n - ((1 math.sqrt (5)) / 2) ** n) / matematica.SQRT (5)
restituire fibn

Il modulo matematico è stato importato. Ha la funzione di radice quadrata. L'operatore, ** viene utilizzato per l'alimentazione. La funzione fibno () implementa direttamente la formula. Una chiamata e una stampa adeguate per la funzione Fibno () è:

N = 11
ret = fibno (n)
Stampa (ret)

L'output è:

89.00000000000003

È possibile rimuovere le cifre decimali non necessarie dalla risposta. Tuttavia, questa è una discussione per qualche altra volta.

Se sono necessari numeri di fibonacci diversi per diversi indici N, la funzione Fibno () deve essere chiamata una volta per ciascuno dell'indice N per restituire i diversi numeri di fibonacci corrispondenti. Il seguente programma lo fa per gli indici a base zero, da 7 a 9 (inclusi):

Importa matematica

def fibno (n):
FIBN = (((1+matematica.sqrt (5))/2) ** n - ((1 math.sqrt (5)) / 2) ** n) / matematica.SQRT (5)
restituire fibn
Per i nell'intervallo (7, 10):
print (fibno (i), end = ")
stampa()

L'output è:

13.000000000000002 21.000000000000004 34.00000000000001

Nota il modo in cui il per loop è stato codificato in Python. Il primo indice è 7. Il prossimo indice è 8 e l'ultimo indice è 9. 10 nell'argomento di portata è 9 + 1. Il valore nella posizione di 10 deve essere l'ultimo indice basato su zero più 1. Il primo argomento, 7, è l'indice di inizio zero basato.

Conclusione

I numeri di Fibonacci sono una sequenza particolare di numeri interi (numeri interi positivi). Inizia con 0, seguito da 1 incondizionatamente. Il resto dei numeri viene sviluppato da lì aggiungendo i due numeri precedenti.

Per ottenere i primi numeri N Fibonacci, accetta 0 e 1 come i primi due, quindi per il resto, usa un per loop con una dichiarazione come:

arr [i] = arr [i - 1] + arr [i - 2]

che aggiunge i due numeri precedenti immediati.

Per ottenere solo un numero di fibonacci da un indice basato su zero N, utilizzare la formula: