पायथन में n तक जोड़ने के लिए न्यूनतम फाइबोनैचि संख्याओं की संख्या ढूंढने का प्रोग्राम

मान लीजिए हमारे पास एक संख्या n है; हमें n तक जोड़ने के लिए आवश्यक न्यूनतम फाइबोनैचि संख्याओं की संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट n = 20 है, तो आउटपुट 3 होगा, क्योंकि हम फाइबोनैचि संख्याओं [2, 5, 13] का उपयोग करके 20 तक जोड़ सकते हैं।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे

• res := 0
• fibo := मान [1, 1] वाली एक सूची
• जब तक fibo का अंतिम तत्व <= n, करें
  • x := fibo के अंतिम दो तत्वों का योग
  • x को fibo में डालें
  • जब तक n नॉन-ज़ीरो है, करें
    • जब तक fibo का अंतिम तत्व > n, करें
      • fibo से अंतिम तत्व हटाएं
    • n := n - fibo का अंतिम तत्व
    • res := res + 1
• res लौटाएं

बेहतर समझ के लिए निम्न कार्यान्वयन देखें

उदाहरण

class Solution:    def solve(self, n):       res = 0       fibo = [1, 1]       while fibo[-1] <= n:          fibo.append(fibo[-1] + fibo[-2])       while n:          while fibo[-1] > n:             fibo.pop()          n -= fibo[-1]          res += 1       return res ob = Solution() n = 20 print(ob.solve(n))

इनपुट

20

आउटपुट

3