جواب «Memoized Fibonacci» چالش 6 از جلسهی 17
سؤال
تابع بازگشتی fib(n) را با memoization بنویس (fib(0)=0، fib(1)=1) — با دیکشنری دستی یا lru_cache. یک n تا ۹۰ بخوان و fib(n) را چاپ کن. بدون حافظه، این برنامه برای n=90 تمام نمیشود.
راهنما
قبل از محاسبه، جواب را در حافظه جستوجو کن و بعد از محاسبه ذخیرهاش کن.
یک جواب درست
memo = {0: 0, 1: 1}
def fib(n):
if n not in memo:
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(int(input())))
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن