«Если к 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 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
В первой строке находятся числа Фибоначчи. Вторая строка имеет индексы, отсчитываемые от нуля, при условии, что числа Фибоначчи находятся в массиве.
Числа Фибоначчи могут быть получены за время O(n) и за время O(1). В этих выражениях временной сложности n означает n основных операций, а 1 означает 1 основную операцию. При O(n) получается n чисел Фибоначчи, начиная с 0. При O(1) одно число Фибоначчи получается из соответствующего индекса. Вот почему вместо n основных операций требуется только одна основная операция.
Цель этой статьи — объяснить, как создавать числа Фибоначчи любым способом с помощью Python.
Формула числа Фибоначчи
Формальное определение числа Фибоначчи:
где F n — число Фибоначчи в отсчитываемом от нуля индексе n<supth. 0 и 1 объявлены заранее. Последняя строка показывает, как из первых двух получаются остальные числа. Он показывает, что два ближайших предыдущих числа добавляются, чтобы получить текущее число.
Получение чисел Фибоначчи за время 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 чисел Фибоначчи:
def fibonacci(n):
arr = [0] * (n)
arr[1] = 1
for i in range(2, n):
arr[i] = arr[i — 1] + arr[i — 2]
return arr
Он начинается с создания массива из n элементов, инициализированных нулями. Этот массив будет содержать числа Фибоначчи. Первое число Фибоначчи, 0, уже есть. Второе число Фибоначчи, 1, присваивается следующим оператором (в функции). Затем идет цикл for, который начинается с индекса 2 и заканчивается непосредственно перед n. В нем есть утверждение:
arr[i] = arr[i — 1] + arr[i — 2]
Это добавляет два ближайших предыдущих числа.
Код для вызова функции и вывода первых двенадцати чисел Фибоначчи может быть таким:
N = 12
A = fibonacci(N)
for i in range(N):
print (A[i], end=’ ‘)
print()
Результат:
0 1 1 2 3 5 8 13 21 34 55 89
Получение одного числа Фибоначчи за постоянное время
Существует математическая формула, которая связывает индекс, начинающийся с нуля, с соответствующим ему числом Фибоначчи. Формула:
Обратите внимание, что в правой части уравнения не квадратный корень из 5 возводится в степень n; это выражение в скобках, возведенное в степень n. Таких выражений два.
Если n равно 0, Fibn будет равно 0. Если n равно 1, Fib n будет равно 1. Если n равно 2, Fib n будет равно 1. Если n равно 3, Fib n будет равно 2. Если n равно 4, Fib n будет 3 — и так далее. Читатель может проверить эту формулу математически, подставляя различные значения для n и оценивая. n — индекс в этой формуле, отсчитываемый от нуля.
Код Python для этой формулы:
импортировать математику
def fibNo(n):
FibN = (((1+math.sqrt(5))/2)**n — ((1-math.sqrt(5))/2)**n) / math.sqrt(5)
return FibN
Математический модуль был импортирован. Он имеет функцию квадратного корня. Оператор ** используется для мощности. Функция fibNo() напрямую реализует формулу. Подходящим вызовом и выводом функции fibNo() является:
N = 11
ret = fibNo(N)
print(ret)
Результат:
89.00000000000003
Из ответа можно убрать ненужные десятичные цифры. Впрочем, это разговор как-нибудь в другой раз.
Если для разных n индексов требуются разные числа Фибоначчи, функция fibNo() должна быть вызвана один раз для каждого из n индексов, чтобы вернуть различные соответствующие числа Фибоначчи. Следующая программа делает это для индексов, отсчитываемых от нуля, от 7 до 9 (включительно):
импортировать математику
def fibNo(n):
FibN = (((1+math.sqrt(5))/2)**n — ((1-math.sqrt(5))/2)**n) / math.sqrt(5)
return FibNfor i in range(7, 10):
print(fibNo(i), end=‘ ‘)
print()
Результат:
13.000000000000002 21.000000000000004 34.00000000000001
Обратите внимание, как цикл for написан в Python. Первый индекс равен 7. Следующий индекс равен 8, а последний индекс равен 9. 10 в аргументе диапазона равно 9 + 1. Значение в позиции 10 должно быть последним индексом, начинающимся с нуля, плюс 1. Первый индекс Аргумент 7 является начальным индексом, начинающимся с нуля.
Заключение
Числа Фибоначчи — это определенная последовательность целых чисел (положительных целых чисел). Он начинается с 0, за которым безоговорочно следует 1. Остальные числа получаются оттуда путем добавления двух предыдущих чисел.
Чтобы получить первые n чисел Фибоначчи, примите 0 и 1 в качестве первых двух, а затем для остальных используйте цикл for с оператором вроде:
arr[i] = arr[i — 1] + arr[i — 2]
который добавляет два ближайших предыдущих числа.
Чтобы получить только одно число Фибоначчи из индекса n, отсчитываемого от нуля, используйте формулу:
