Числа Фибоначчи весьма интересная последовательность и используется в различных математических задачах. В ней каждый следующий элемент равен сумме двух предыдущих. Математики начинают эту последовательность с двух единиц, но мы же с вами программисты, поэтому привыкли вести счет с нуля.
Напишите генератор fibonacci
, который последовательно возвращает заданное количество чисел Фибоначчи по “правилам программистов”.
Примечание
Ваше решение должно содержать только функции.
В решении не должно быть вызовов требуемых функций.
Пример
Ввод
print(*fibonacci(5))
Вывод
0 1 1 2 3
Ввод
print(*fibonacci(10), sep=', ')
Вывод
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
Лирическое отступление
Надо сказать, что заявляя, что математики начинают последовательность с двух единиц, Яндекс выставляет себя не в лучшем свете. В его материалах в примерах с рекурсией указаны неправильные значения чисел Фибоначчи именно по той причине, что Яндекс сам начинает считать последовательность Фибоначчи с двух единиц прямо в теоретическом материале к этой задаче
Математики же как раз считают последовательность Фибоначчи с нуля и единицы.
Решение
Первая задача на генераторы. С учетом того, что функция по большому счету от генератора отличается только способом возрата значения, задача элементарна: Реализуем алгоритм вычисления последовательности Фибоначчи и на каждой итерации возвращаем полученое число с помощью yeld.
Посмотреть код
Решение
def fibonacci(num):
a = 0
b = 1
for _ in range(num):
yield a
a, b = b, a + b
Скажите, пожалуйста, уместно ли использование кеширования для сокращения времени вычисления? Ведь n может иметь существенную величину…
from functools import lru_cache
@lru_cache(maxsize=1000)
def fibonacci(n):
n_1, n_2 = 0, 1
for i in range(n):
yield n_1
n_1, n_2 = n_2, n_1 + n_2
Не сразу обратил внимание о том, что вопрос о генераторе, поэтому первый ответ был не совсем по теме.
Генераторы не имеет смысла кэшировать потому, что каждый проход генератора это уникальная последовательность, которая не будет содержаться в кэше – у каждого генератора будет свой собственный новый кэш.
Если же мы говорим о функциях, то кэширование с помощью @lru_cache имеет смысл только если количество посчитанных значений будет с большой вероятностью содержать запрашиваемые данные. В противном случае чаще всего прибегают к самостоятельной организации единожды или ранее посчитанных значений функции.
Таким образом, если в генератор поместить кэшированную функцию, то можно добиться некоторого прироста производительности.
А! Да! Точно. Спасибо!!!