Числата на Фибоначи на езика Python

Числата на Фибоначи са конкретна последователност, при която първата стойност е предварително декларирана като 0, а втората стойност е предварително декларирана като 1. Останалите числа се получават от тези две чрез добавяне на предходните две числа. Всички числа на Фибоначи са цели положителни числа, започващи от 0. Първите дванадесет числа на Фибоначи и как се получават са както следва:

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

Без изразите за сума, тези числа на Фибоначи могат да бъдат поставени в таблица, както следва:

Първият ред съдържа числата на Фибоначи. Вторият ред има индекси, базирани на нула, като се приема, че числата на Фибоначи са в масив.

Числата на Фибоначи могат да бъдат произведени за O(n) време и за O(1) време. В тези изрази за времева сложност n означава n основни операции, а 1 означава 1 основна операция. С O(n) се произвеждат n числа на Фибоначи, като се започне от 0. С O(1) се произвежда едно число на Фибоначи от съответния индекс. Ето защо е необходима само една основна операция вместо n основни операции.

Целта на тази статия е да обясни как да произвеждаме числа на Фибоначи, така или иначе, с помощта на Python.

Формула за числото на Фибоначи

Официалната дефиниция на числото на Фибоначи е:

където F _н е числото на Фибоначи при базирания на нула индекс n

Произвеждане на числата на Фибоначи за O(n) време

Ако n е 1, тогава само 0 ще бъде отпечатано като число на Фибоначи. Ако n е 2, тогава 0 и 1 ще бъдат отпечатани като числа на Фибоначи в този ред. Ако n е 3, тогава 0, 1 и 1 ще бъдат отпечатани като числа на Фибоначи в този ред. Ако n е 4, тогава 0, 1, 1 и 2 ще бъдат отпечатани като числа на Фибоначи в този ред. Ако n е 5, тогава 0, 1, 1, 2 и 3 ще бъдат отпечатани като числа на Фибоначи в този ред. Ако n е 6, тогава 0, 1, 1, 2, 3 и 5 ще бъдат отпечатани като числа на Фибоначи, в този ред – и така нататък.

Функцията на Python за генериране на първите n числа на Фибоначи е:

Започва със създаване на масив от n елемента, всички инициализирани на нули. Този масив ще съдържа числата на Фибоначи. Първото число на Фибоначи, 0, вече е там. Второто число на Фибоначи, 1, се присвоява от следващия оператор (във функцията). След това има for-цикъл, който започва от индекс 2 до точно преди n. Има изявлението:

Това добавя предходните две числа.

Кодът за извикване на функцията и отпечатване на първите дванадесет числа на Фибоначи може да бъде:

N = 12
A = фибоначи (N)
за i в диапазон (N):
печат (A[i], край=’ ‘)
печат ()

Резултатът е:

Произвеждане на едно число на Фибоначи за постоянно време

Има математическа формула, която свързва базиран на нула индекс със съответното му число на Фибоначи. Формулата е:

Обърнете внимание, че от дясната страна на уравнението не е корен квадратен от 5, който е повдигнат на степен n; това е изразът в скобите, който се повдига на степен n. Има два такива израза.

Ако n е 0, Fibn ще бъде 0. Ако n е 1, Fib _н ще бъде 1. Ако n е 2, Fib _н ще бъде 1. Ако n е 3, Fib _н ще бъде 2. Ако n е 4, Fib _н ще бъде 3 – и така нататък. Читателят може да провери тази формула математически, като замести различни стойности за n и оцени. n е базиран на нула индекс в тази формула.

Кодът на Python за тази формула е:

импортиране на математика

Математическият модул беше импортиран. Има функция за квадратен корен. Операторът ** се използва за мощност. Функцията fibNo() имплементира директно формулата. Подходящо извикване и отпечатване за функцията fibNo() е:

N = 11
дясно = fibNo(N)
отпечатване (повторно)

Резултатът е:

Възможно е да премахнете ненужните десетични цифри от отговора. Това обаче е дискусия за друг път.

Ако се изискват различни числа на Фибоначи за различни n индекси, функцията fibNo() трябва да бъде извикана веднъж за всеки от n индекса, за да върне различните съответстващи числа на Фибоначи. Следната програма прави това за индексите, базирани на нула, от 7 до 9 (включително):

импортиране на математика

Резултатът е:

Обърнете внимание на начина, по който for-цикълът е кодиран в Python. Първият индекс е 7. Следващият индекс е 8, а последният индекс е 9. 10 в аргумента за обхвата е 9 + 1. Стойността на позиция 10 трябва да бъде последният базиран на нула индекс плюс 1. Първият аргумент, 7, е началният индекс, базиран на нула.

Заключение

Числата на Фибоначи са определена последователност от цели числа (положителни цели числа). Започва с 0, последвано от 1 безусловно. Останалите числа се развиват оттам чрез добавяне на непосредствено предишните две числа.

За да получите първите n числа на Фибоначи, приемете 0 и 1 като първите две, след това за останалите използвайте for-цикъл с израз като:

което събира предходните две числа.

За да получите само едно число на Фибоначи от базиран на нула индекс n, използвайте формулата: