ধরুন আমাদের একটি সংখ্যা k আছে, আমাদের ফিবোনাচি সংখ্যার ন্যূনতম সংখ্যা খুঁজে বের করতে হবে যার যোগফল k এর সমান, একটি ফিবোনাচি সংখ্যা একাধিকবার ব্যবহার করা যেতে পারে কিনা।
সুতরাং, যদি ইনপুটটি k =7 এর মতো হয় তবে আউটপুট হবে 2, যেমন ফিবোনাচি সংখ্যাগুলি হল:1, 1, 2, 3, 5, 8, 13, ... k =7 এর জন্য আমরা 2 + ব্যবহার করতে পারি 5 =7।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি অ্যারে f
সংজ্ঞায়িত করুন -
f
এর শেষে 0 ঢোকান -
f
এর শেষে 1 সন্নিবেশ করান -
যখন f <=k, do −
এর শেষ উপাদান-
f
-এ (f-এর শেষ উপাদান + f-এর দ্বিতীয় শেষ উপাদান) সন্নিবেশ করান
-
-
ret :=0
-
j :=f
এর শেষ সূচক -
যখন (j>=0 এবং k> 0), করবেন −
-
যদি f[j] <=k, তাহলে −
-
k :=k - f[j]
-
(রেট 1 দ্বারা বাড়ান)
-
-
অন্যথায়
-
(j 1 দ্বারা কমিয়ে দিন)
-
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h> using namespace std; class Solution { public: int findMinFibonacciNumbers(int k) { vector<int> f; f.push_back(0); f.push_back(1); while (f.back() <= k) { f.push_back(f[f.size() - 1] + f[f.size() - 2]); } int ret = 0; int j = f.size() - 1; while (j >= 0 && k > 0) { if (f[j] <= k) { k -= f[j]; ret++; } else j--; } return ret; } }; main(){ Solution ob; cout << (ob.findMinFibonacciNumbers(7)); }
ইনপুট
7
আউটপুট
2