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

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

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

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

• रेस :=0

• Fibo :=मानों वाली एक सूची [1, 1]

• जबकि फाइबो का अंतिम तत्व <=n, करते हैं

  • x :=फाइबो के अंतिम दो तत्वों का योग

  • Fibo में x डालें

  • जबकि n शून्य नहीं है, करें

    • जबकि फाइबो का अंतिम तत्व> n, करें

      • Fibo से अंतिम तत्व हटाएं

    • n :=n - फाइबो का अंतिम तत्व

    • रेस :=रेस + 1

• रिटर्न रेस

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

उदाहरण

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