Урок 12.8
Числа Фибоначчи по определению считаются рекурсией: каждая следующая — сумма двух предыдущих.
def fib(n, memo={}):
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]
fib(50) это
уже очень долго;memo — словарь результатов: сначала проверяем, не считали ли уже;memo, и в следующий раз вернём сразу;memo = {} внутри функции обнулит память на каждом вызове.Проверка даёт число n. Напишите fib с запоминанием в словарь memo из memo = {}
наверху. Напечатайте fib(n) и memo: в словаре видно, какие числа пришлось считать
и запомнить: все числа от 2 до n.
Запоминание — словарь снаружи функции.
Первым делом проверьте, нет ли n в memo, — тогда вернуть готовое.
База — n < 2. Иначе посчитайте сумму двух предыдущих и сохраните её в
memo, прежде чем вернуть.