MiddleКодЧастоЕщё не отвечали
Вычислите Фибоначчи итеративно и как генератор
Реализуйте две вещи без экспоненциальной рекурсии.
Требования:
fib(n)возвращает n-е число Фибоначчи за O(n) времени и O(1) памяти.fib_gen()— бесконечный генератор, лениво выдающий0, 1, 1, 2, 3, ....
def fib(n: int) -> int:
# ваш код здесь
def fib_gen():
# ваш код здесьДопишите реализацию.
Итерируйте обменом кортежа: a, b = 0, 1; for _ in range(n): a, b = b, a + b; return a — O(n) время, O(1) память, без экспоненциальной рекурсии. Генератор выдаёт лениво: while True: yield a; a, b = b, a + b. Целые в Python произвольной точности, поэтому переполнения нет.
- ✗Наивная двойная рекурсия (экспоненциальное время)
- ✗Утверждать, что полный список — это O(1) память
- ✗Доверять, что формула Бине на float останется точной для больших n
- →Почему обмен кортежа
a, b = b, a + bработает за один шаг? - →Как генераторная версия позволяет вызывающему взять лишь первые k значений?
Оглавление
Задача
Реализуйте fib(n) за O(n)/O(1) и бесконечный генератор fib_gen() без экспоненциальной рекурсии.
Решение
def fib(n: int) -> int:
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
def fib_gen(): # бесконечный генератор
a, b = 0, 1
while True:
yield a
a, b = b, a + bКлючевые моменты
- Обмен кортежа
a, b = b, a + bобновляет оба значения за один шаг без временной переменной. - Итеративная версия — O(n) времени, O(1) памяти; наивная рекурсия экспоненциальна.
- Целые в Python имеют произвольную точность, поэтому Фибоначчи не переполняется.
Оглавление
