পাইথনে nম মেয়াদ পর্যন্ত ফিবোনাচি সিরিজের ফলাফল খোঁজার প্রোগ্রাম

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

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

m :=10^8+7
মেমো :=একটি নতুন মানচিত্র
একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি n, m
যদি n মেমোতে থাকে, তাহলে
- রিটার্ন মেমো[n]
মেমো[n] :=n যখন n <2 অন্যথায় (solve(n-1, m) +solve(n-2, m)) mod m
রিটার্ন মেমো[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]))