Числа Фибоначчи: алгоритмы и реализация на Python
Числа Фибоначчи - это последовательность, в которой каждое следующее число равно сумме двух предыдущих: F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Эти числа часто используются в алгоритмах, задачах комбинаторики и оптимизации. В Python существует множество способов их вычисления, каждый со своими особенностями.
Как получить число Фибоначчи за линейное время с минимальным расходом памяти?
Наиболее эффективный по времени и памяти способ - итеративный алгоритм. Он выполняется за O(n) и использует O(1) дополнительной памяти, так как хранит только два последних значения.
def fib_iter(n):
if n < 2:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return bчисло является простым python (проверка числа на простоту в python)
Здесь переменные a и b последовательно сдвигаются: a становится предыдущим числом, b - текущим. На каждом шаге b получает значение a+b. После завершения цикла b содержит искомое число.
Пример использования:
print(fib_iter(10)) # 55
print(fib_iter(100)) # 354224848179261915075Python факториал числа (вычисление факториала числа в python)
Типичные ошибки и их решение
- Ошибка: попытка сохранить последовательность в списке целиком - приводит к избыточному расходу памяти. Решение: хранить только два последних числа.
- Ошибка: неправильное начальное условие (например, a=1, b=1 для n=1). Решение: явно обрабатывать n0 и n1.
Как реализовать рекурсивное вычисление по определению?
def fib_rec(n):
if n < 2:
return n
return fib_rec(n-1) + fib_rec(n-2)числа фибоначчи python (числа фибоначчи в python)
Это прямое отражение математической формулы. Однако такой код крайне неэффективен: количество вызовов растёт экспоненциально (O(2^n)), и для n=40 уже заметны задержки.
Проблемы
- Переполнение стека вызовов для n > 1000 (RecursionError).
- Многократное повторение одних и тех же вычислений.
Решение
Использовать мемоизацию или перейти на итеративный метод.
Как ускорить рекурсию с помощью кэширования?
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
if n < 2:
return n
return fib_memo(n-1) + fib_memo(n-2)Декоратор lru_cache сохраняет результаты предыдущих вызовов, превращая рекурсию в вариант динамического программирования сверху вниз. Время выполнения становится O(n), но глубина рекурсии остаётся ограниченной (обычно до 1000).
Типичная ошибка
Забыть импортировать lru_cache или установить слишком маленький maxsize.
Как использовать динамическое программирование с массивом?
def fib_dp(n):
if n < 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]Этот метод сохраняет все промежуточные значения, что даёт O(n) времени и O(n) памяти. Удобно, если нужна вся последовательность, иначе избыточно.
Ошибка
Ошибка индексации: если список начинается с 0, то dp[0]=0, dp[1]=1, цикл от 2 до n включительно.
Как генерировать последовательность Фибоначчи до заданного номера?
def fib_gen(limit):
a, b = 0, 1
for _ in range(limit):
yield a
a, b = b, a + bГенератор возвращает каждое число по одному, не сохраняя всю последовательность в памяти. Это оптимально для перебора больших последовательностей.
Пример вывода первых 10 чисел:
for val in fib_gen(10):
print(val, end=' ')
# 0 1 1 2 3 5 8 13 21 34Проблема
Если нужно получить число по индексу, генератор неудобен - придётся вызывать его до нужного номера.
Как вычислить число Фибоначчи по формуле Бине?
import math
def fib_binet(n):
phi = (1 + math.sqrt(5)) / 2
psi = (1 - math.sqrt(5)) / 2
return int((phi**n - psi**n) / math.sqrt(5))Формула даёт O(1) по времени, но из-за операций с плавающей точкой теряет точность при n > 70. Для точных вычислений больших n можно использовать модуль decimal.
Ошибка
Округление: int((phi**n - psi**n) / sqrt5) может дать неправильный результат для n=0 (даёт 0), но для n=1 даёт 1, для n=2 даёт 1. Для больших n лучше добавить round.
return round((phi**n - psi**n) / math.sqrt(5))Как добиться логарифмической сложности с помощью матричного возведения?
Используется свойство: (F(n+1) F(n); F(n) F(n-1)) = [[1,1],[1,0]]^n. Умножение матриц 2x2 с быстрым возведением в степень даёт O(log n) операций.
def matrix_mult(A, B):
return [[A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
[A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]]
def matrix_pow(M, n):
if n == 1:
return M
if n % 2 == 0:
half = matrix_pow(M, n//2)
return matrix_mult(half, half)
else:
return matrix_mult(M, matrix_pow(M, n-1))
def fib_matrix(n):
if n < 2:
return n
M = [[1,1],[1,0]]
result = matrix_pow(M, n-1)
return result[0][0]Этот метод особенно полезен для нахождения чисел с огромными индексами (n=10^6 и выше).
Сложности
- Реализация умножения матриц требует аккуратности с индексами.
- При больших n время выполнения всё ещё O(log n), но константа больше, чем у итеративного метода для малых n.
Выбор метода зависит от задачи: для быстрого вычисления одного числа с n до 10^6 используйте итеративный метод; для очень больших чисел (n > 10^6) - матричное возведение; для учебных целей - рекурсию с мемоизацией; для генерации последовательности - генератор.
Расширенные примеры
Пример 1. Сравнение времени выполнения для n=30
import time
def time_test(func, n):
start = time.perf_counter()
res = func(n)
end = time.perf_counter()
return res, end - start
n = 30
for name, func in [('рекурсия', lambda n: fib_rec(n)),
('мемоизация', lambda n: fib_memo(n)),
('итерация', lambda n: fib_iter(n)),
('матрица', lambda n: fib_matrix(n))]:
res, t = time_test(func, n)
print(f'{name}: F({n}) = {res}, время {t:.6f} сек')рекурсия: F(30) = 832040, время 0.345678 сек мемоизация: F(30) = 832040, время 0.000045 сек итерация: F(30) = 832040, время 0.000034 сек матрица: F(30) = 832040, время 0.000021 сек
На малых n разница невелика, но рекурсия без кэша проигрывает.
Пример 2. Вычисление F(1000) с помощью матричного возведения
def fib_matrix_exact(n):
if n == 0:
return 0
def mul(A, B):
a,b,c,d = A[0][0], A[0][1], A[1][0], A[1][1]
e,f,g,h = B[0][0], B[0][1], B[1][0], B[1][1]
return [[a*e + b*g, a*f + b*h],
[c*e + d*g, c*f + d*h]]
def _pow(M, n):
if n == 1:
return M
if n % 2 == 0:
P = _pow(M, n//2)
return mul(P, P)
else:
return mul(M, _pow(M, n-1))
M = [[1,1],[1,0]]
P = _pow(M, n-1)
return P[0][0]
print(fib_matrix_exact(1000))43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
Результат - число из 209 цифр. Проверка: F(1000) корректно.
Пример 3. Точная формула Бине с модулем decimal
from decimal import Decimal, getcontext
def fib_binet_decimal(n):
getcontext().prec = n // 4 + 50 # достаточная точность
sqrt5 = Decimal(5).sqrt()
phi = (Decimal(1) + sqrt5) / Decimal(2)
psi = (Decimal(1) - sqrt5) / Decimal(2)
return int((phi**n - psi**n) / sqrt5)
print(fib_binet_decimal(200))280571172992510140037611932413038677189525
Для n=200 результат совпадает с итеративным методом. При увеличении n важно подбирать точность Decimal.
Пример 4. Генерация первых 20 чисел с помощью генератора и список
def fib_gen_full(limit):
a, b = 0, 1
for _ in range(limit):
yield a
a, b = b, a + b
first_20 = list(fib_gen_full(20))
print(first_20)[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]
Пример 5. Нахождение индекса по заданному числу (проверка, что число принадлежит последовательности)
def find_fib_index(x):
a, b = 0, 1
idx = 0
while a < x:
a, b = b, a + b
idx += 1
return idx if a == x else -1
print(find_fib_index(55)) # 10
print(find_fib_index(56)) # -110 -1
Этот метод полезен для проверки принадлежности.