मान लीजिए कि हमारे पास एक संख्या n है। हमें पहले n फाइबोनैचि पदों का योग (n पदों तक फाइबोनैचिक्वेंस) ज्ञात करना है। अगर उत्तर बहुत बड़ा है तो परिणाम मॉड्यूलो 10^8 + 7 लौटाएं।
इसलिए, यदि इनपुट n =8 जैसा है, तो आउटपुट 33 होगा क्योंकि पहले कुछ फाइबोनैचि शब्द 0 + 1 + 1 +2 + 3 + 5 + 8 + 13 =33 हैं
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- म :=10^8+7
- ज्ञापन:=एक नया नक्शा
- एक फ़ंक्शन को हल करें() परिभाषित करें। इसमें n, m . लगेगा
- यदि n ज्ञापन में है, तो
- वापसी ज्ञापन[n]
- ज्ञापन[n] :=n जब n <2 अन्यथा (हल करें(n-1, m) +हल करें(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])) इनपुट
8
आउटपुट
33