ধরুন আমাদের একটি সংখ্যা 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
