फाइबोनैचि संख्याओं की न्यूनतम संख्या ज्ञात कीजिए जिनका योग C++ में K है

मान लीजिए कि हमारे पास एक संख्या k है, हमें फाइबोनैचि संख्याओं की न्यूनतम संख्या ज्ञात करनी है, जिनका योग k के बराबर है, क्या एक फाइबोनैचि संख्या का कई बार उपयोग किया जा सकता है।

इसलिए, यदि इनपुट k =7 जैसा है, तो आउटपुट 2 होगा, क्योंकि फाइबोनैचि संख्याएँ हैं:1, 1, 2, 3, 5, 8, 13, ... k =7 के लिए हम 2 + का उपयोग कर सकते हैं। 5 =7.

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

एक सरणी को परिभाषित करें f
f के अंत में 0 डालें
f के अंत में 1 डालें
जबकि f <=k का अंतिम अवयव, −
. करें
- f
  . में डालें (f का अंतिम तत्व + f का दूसरा अंतिम तत्व)
रिट:=0
j :=f का अंतिम सूचकांक
जबकि (j>=0 और k> 0) करते हैं −
- अगर f[j] <=k, तो -
  - के:=के - एफ [जे]
  - (रिटर्न 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));
}