পাইথনে nth টার্ম পর্যন্ত ফিবোনাচি সিরিজের যোগফল বের করার প্রোগ্রাম

ধরুন আমাদের একটি সংখ্যা n আছে। আমাদের প্রথম n টি ফিবোনাচি টার্মের যোগফল বের করতে হবে (n টার্ম পর্যন্ত ফিবোনাচি সিকোয়েন্স)। যদি ফলাফল খুব বড় হয়, তবে ফলাফলটি 10^8 + 7 দিয়ে মডুলো করে রিটার্ন করতে হবে।

উদাহরণস্বরূপ, যদি ইনপুট n = 8 হয়, তবে আউটপুট হবে 33 কারণ প্রথম ৮টি ফিবোনাচি টার্ম হলো 0 + 1 + 1 + 2 + 3 + 5 + 8 + 13 = 33।

সমাধানের ধাপসমূহ

m := 10^8 + 7
memo := একটি নতুন ম্যাপ (ডিকশনারি)
solve() ফাংশন ডিফাইন করুন যা n, m প্যারামিটার নেবে
যদি n মেমোতে থাকে, তবে memo[n] রিটার্ন করুন
memo[n] := n যদি n < 2 হয়, অন্যথায় (solve(n-1, m) + solve(n-2, m)) % m
memo[n] রিটার্ন করুন
মেইন মেথড থেকে মেমো ভ্যালুগুলোর লিস্ট নিয়ে তাদের যোগফল বের করুন

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বুঝার জন্য:

m = 10**8 + 7
memo = {}

def solve(n, m):
    if n in memo:
        return memo[n]
    memo[n] = n if n < 2 else (solve(n-1, m) + solve(n-2, m)) % m
    return memo[n]

n = 8
solve(n, m)
print(sum(list(memo.values())[:n]))