C++-এ ফিবোনাচ্চি নাম্বার দিয়ে K বানাতে ন্যূনতম সংখ্যা

একটি সংখ্যা k দেওয়া আছে। ফিবোনাচ্চি সংখ্যা ব্যবহার করে (বарবার ব্যবহার করা যায়) k বানাতে ন্যূনতম কতটি ফিবোনাচ্চি সংখ্যা লাগবে তা বের করতে হবে।

ইনপুট: k = 7 → আউটপুট: 2 (২ + ৫ = ৭)

সমাধানের ধাপগুলো (লালची/গ্রিডি):

ফিবোনাচ্চি সিকোয়েন্স k পর্যন্ত জেনারেট করব
সবচেয়ে বড় ফিবোনাচ্চি থেকে শুরু করে k কমানো
প্রতি বারের মতো সাবট্র্যাক্ট করলে কাউন্ট বাড়াব
এই গ্রিডি পদ্ধতিই অপ্টিমাম (জেকendorf থিওরেম)

উদাহরণ

নিচের কোডটি দেখুন −

#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;
    }
};

int main() {
    Solution ob;
    cout << (ob.findMinFibonacciNumbers(7));
}