পাইথনে n পর্যন্ত যোগ করার জন্য ফিবোনাচি সংখ্যার ন্যূনতম সংখ্যা খুঁজে বের করার প্রোগ্রাম?

ধরুন আমাদের একটি সংখ্যা n আছে; n পর্যন্ত যোগ করার জন্য প্রয়োজনীয় ফিবোনাচি সংখ্যার ন্যূনতম সংখ্যা আমাদের খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট n =20 এর মত হয়, তাহলে আউটপুট হবে 3, যেমন আমরা ফিবোনাচি সংখ্যাগুলি [2,5, 13] ব্যবহার করে যোগফল 20 করতে পারি।

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

res :=0
fibo :=মান সহ একটি তালিকা [1, 1]
যখন fibo এর শেষ উপাদান <=n, do
- x :=ফিবোর শেষ দুটি উপাদানের যোগফল
- ফাইবোতে x ঢোকান
- যখন n অ-শূন্য, কর
  - যখন fibo> n, do
    এর শেষ উপাদান
    - fibo
      থেকে শেষ উপাদান মুছুন
  - n :=n - ফাইবোর শেষ উপাদান
  - res :=res + 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))