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

Cisla Fibonacci Na Azyke Python



«Если к 1 прибавить 0, ответ будет 1. Если ответ 1 и слагаемое (не авгенд) сложить вместе, новый ответ будет 2. Если этот новый ответ и его слагаемое сложить вместе, ответ будет 3. Если сложить этот новый ответ и его дополнение, ответ будет 5».

Числа Фибоначчи представляют собой особую последовательность, в которой первое значение предварительно объявлено как 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







Без выражений суммы эти числа Фибоначчи можно поместить в таблицу следующим образом:



0 1 1 два 3 5 8 13 двадцать один 3. 4 55 89
0 1 два 3 4 5 6 7 8 9 10 одиннадцать

В первой строке находятся числа Фибоначчи. Вторая строка имеет индексы, отсчитываемые от нуля, при условии, что числа Фибоначчи находятся в массиве.



Числа Фибоначчи могут быть получены за время 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 чисел Фибоначчи:

определение Фибоначчи ( н ) :
прибытие = [ 0 ] * ( н )
обр [ 1 ] знак равно 1
за я в диапазон ( два , н ) :
обр [ я ] = обр. [ я - 1 ] + обр. [ я - два ]
возвращаться обр

Он начинается с создания массива из n элементов, инициализированных нулями. Этот массив будет содержать числа Фибоначчи. Первое число Фибоначчи, 0, уже есть. Второе число Фибоначчи, 1, присваивается следующим оператором (в функции). Затем идет цикл for, который начинается с индекса 2 и заканчивается непосредственно перед n. В нем есть утверждение:

обр [ я ] = обр. [ я - 1 ] + обр. [ я - два ]

Это добавляет два ближайших предыдущих числа.

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

N = 12
А = Фибоначчи (Н)
для я в диапазоне (N):
напечатать (A[i], end='')
Распечатать()

Результат:

0 1 1 два 3 5 8 13 двадцать один 3. 4 55 89

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

Существует математическая формула, которая связывает индекс, начинающийся с нуля, с соответствующим ему числом Фибоначчи. Формула:

Обратите внимание, что в правой части уравнения не квадратный корень из 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 для этой формулы:

импортировать математику

деф фибНет ( н ) :
Фибоначчи = ( ( ( 1 +math.sqrt ( 5 ) ) / два ) ** н - ( ( 1 -math.sqrt ( 5 ) ) / два ) ** н ) / math.sqrt ( 5 )
возвращаться Фибоначчи

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

N = 11
справа = фибнет(N)
печать (возврат)

Результат:

89.00000000000003

Из ответа можно убрать ненужные десятичные цифры. Впрочем, это разговор как-нибудь в другой раз.

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

импортировать математику

деф фибНет ( н ) :
Фибоначчи = ( ( ( 1 +math.sqrt ( 5 ) ) / два ) ** н - ( ( 1 -math.sqrt ( 5 ) ) / два ) ** н ) / math.sqrt ( 5 )
возвращаться Фибоначчи

за я в диапазон ( 7 , 10 ) :
Распечатать ( фибнет ( я ) , конец знак равно ' ' )
Распечатать ( )

Результат:

13 000000000000002 21 000000000000004 34 00000000000001

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

Вывод

Числа Фибоначчи — это определенная последовательность целых чисел (положительных целых чисел). Он начинается с 0, за которым безоговорочно следует 1. Остальные числа получаются оттуда путем добавления двух предыдущих чисел.

Чтобы получить первые n чисел Фибоначчи, примите 0 и 1 в качестве первых двух, а затем для остальных используйте цикл for с оператором вроде:

обр [ я ] = обр. [ я - 1 ] + обр. [ я - два ]

который добавляет два ближайших предыдущих числа.

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