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

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

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

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

एक ऐरे f परिभाषित करें
0 को f के अंत में डालें
1 को f के अंत में डालें
जब f का अंतिम एलिमेंट <= k, करें -
- (f का अंतिम एलिमेंट + f का दूसरा अंतिम एलिमेंट) को f में डालें
ret := 0
j := f का अंतिम इंडेक्स
जब (j >= 0 और k > 0), करें -
- यदि f[j] <= k, तो -
  - k := k - f[j]
  - (ret को 1 से बढ़ाएं)
- अन्यथा
  - (j को 1 से घटाएं)
ret लौटाएं

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

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