Numerele Fibonacci în limbajul Python

Numerele Fibonacci sunt o anumită secvență în care prima valoare este pre-declarată ca 0 și a doua valoare este pre-declarată ca 1. Restul numerelor sunt produse din aceste două prin adăugarea celor două numere anterioare. Toate numerele Fibonacci sunt numere întregi pozitive, începând cu 0. Primele douăsprezece numere Fibonacci și modul în care sunt obținute sunt după cum urmează:

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

Fără expresiile de sumă, aceste numere Fibonacci pot fi puse într-un tabel după cum urmează:

Primul rând are numerele Fibonacci. Al doilea rând are indici bazați pe zero, presupunând că numerele Fibonacci sunt într-o matrice.

Numerele Fibonacci pot fi produse în timp O(n) și în timp O(1). În aceste expresii de complexitate temporală, n înseamnă n operații principale, iar 1 înseamnă o operație principală. Cu O(n), se produc n numere Fibonacci, începând de la 0. Cu O(1), se produce un număr Fibonacci dintr-un indice corespunzător. De aceea este nevoie de o singură operație principală în loc de n operații principale.

Scopul acestui articol este de a explica cum să produci numere Fibonacci, în orice caz, folosind Python.

Formula pentru un număr Fibonacci

Definiția formală a unui număr Fibonacci este:

unde F _n este numărul Fibonacci la baza zero n

Producerea numerelor Fibonacci în timp O(n).

Dacă n este 1, atunci numai 0 ar fi tipărit ca număr Fibonacci. Dacă n este 2, atunci 0 și 1 ar fi tipărite ca numere Fibonacci, în această ordine. Dacă n este 3, atunci 0, 1 și 1 ar fi tipărite ca numere Fibonacci în această ordine. Dacă n este 4, atunci 0, 1, 1 și 2 ar fi tipărite ca numere Fibonacci în această ordine. Dacă n este 5, atunci 0, 1, 1, 2 și 3 ar fi tipărite ca numere Fibonacci, în această ordine. Dacă n este 6, atunci 0, 1, 1, 2, 3 și 5 ar fi tipărite ca numere Fibonacci, în această ordine – și așa mai departe.

Funcția Python pentru a produce primele n numere Fibonacci este:

Începe prin a crea o matrice de n elemente, toate inițializate la zerouri. Această matrice va conține numerele Fibonacci. Primul număr Fibonacci, 0, este deja acolo. Al doilea număr Fibonacci, 1, este atribuit de următoarea instrucțiune (în funcție). Apoi există bucla for, care începe de la indicele 2 până chiar înainte de n. Are afirmația:

Aceasta adaugă cele două numere anterioare imediate.

Codul pentru a apela funcția și a imprima primele douăsprezece numere Fibonacci poate fi:

N = 12
A = Fibonacci(N)
pentru i în intervalul (N):
tipăriți (A[i], sfârșit=’ ‘)
imprimare()

Ieșirea este:

Producerea unui număr Fibonacci în timp constant

Există o formulă matematică care leagă un indice bazat pe zero cu numărul lui Fibonacci corespunzător. Formula este:

Rețineți că în partea dreaptă a ecuației, nu rădăcina pătrată a lui 5 este ridicată la puterea n; este expresia din paranteze care se ridică la puterea n. Există două astfel de expresii.

Dacă n este 0, Fibn ar fi 0. Dacă n este 1, Fib _n ar fi 1. Dacă n este 2, Fib _n ar fi 1. Dacă n este 3, Fib _n ar fi 2. Dacă n este 4, Fib _n ar fi 3 – și așa mai departe. Cititorul poate verifica matematic această formulă prin înlocuirea diferitelor valori pentru n și evaluând. n este un indice bazat pe zero în această formulă.

Codul Python pentru această formulă este:

import matematică

Modulul de matematică a fost importat. Are funcția rădăcină pătrată. Operatorul, ** este folosit pentru putere. Funcția fibNo() implementează formula direct. Un apel adecvat și o imprimare pentru funcția fibNo() este:

N = 11
dreapta = fibNo(N)
imprimare (retras)

Ieșirea este:

Este posibil să eliminați cifrele zecimale inutile din răspuns. Cu toate acestea, aceasta este o discuție pentru altă dată.

Dacă sunt necesare numere Fibonacci diferite pentru n indici diferiți, funcția fibNo() trebuie apelată o dată pentru fiecare dintre n indici pentru a returna diferitele numere Fibonacci corespunzătoare. Următorul program face acest lucru pentru indicii bazați pe zero, de la 7 la 9 (inclusiv):

import matematică

Ieșirea este:

Observați modul în care bucla for a fost codificată în Python. Primul indice este 7. Următorul indice este 8, iar ultimul indice este 9. 10 în argumentul interval este 9 + 1. Valoarea din poziția 10 trebuie să fie ultimul indice bazat pe zero plus 1. Primul argumentul, 7, este indexul de început bazat pe zero.

Concluzie

Numerele Fibonacci sunt o anumită succesiune de numere întregi (numere întregi pozitive). Începe cu 0, urmat de 1 necondiționat. Restul numerelor sunt dezvoltate de acolo prin adăugarea celor două numere anterioare imediate.

Pentru a obține primele n numere Fibonacci, acceptați 0 și 1 ca primele două, apoi pentru restul, utilizați o buclă for cu o declarație ca:

care adaugă cele două numere anterioare imediate.

Pentru a obține un singur număr Fibonacci dintr-un indice n bazat pe zero, utilizați formula: