Источник: https://docs.python.org/3/tutorial/introduction.html

Задача

Напечатать первые n чисел Фибоначчи: 0, 1, 1, 2, 3, 5, … Каждое следующее число равно сумме двух предыдущих. Одна из самых первых задач в любом курсе алгоритмов.

Решение

Храним два последних числа и на каждом шаге сдвигаем их. Так мы избегаем рекурсии, которая для этой задачи работает заметно медленнее.

def fibonacci(n: int) -> list[int]: a, b = 0, 1 result = [] for _ in range(n): result.append(a) a, b = b, a + b # сдвигаем пару вперёд  return result print(fibonacci(10))

Как это работает

В начале a = 0, b = 1. На каждой итерации мы записываем a в результат, а затем одновременно обновляем обе переменные: новое a — это старое b, новое b — сумма старых a + b. Одна строка a, b = b, a + b делает всю работу.

Пример работы 

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Сложность

O(n) по времени, O(n) по памяти под список результата.

Читайте также: https://docs.python.org/3/tutorial/introduction.html

Related: