इस समस्या में, हमें एक नंबर K दिया जाता है। हमारा कार्य K के बराबर योग के साथ न्यूनतम फिबोनाची शब्द खोजना है। ।
फाइबोनैचि श्रृंखला दो पिछली संख्याओं को जोड़कर बाद की संख्याएँ उत्पन्न करती है। फाइबोनैचि श्रृंखला दो संख्याओं - F0 और F1 से शुरू होती है। F0 और F1 के प्रारंभिक मान क्रमशः 0, 1 या 1, 1 लिए जा सकते हैं।
फाइबोनैचि सीरीज 0 1 1 2 3 5 8 13
. हैसमस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
K = 5
आउटपुट
2
स्पष्टीकरण
The sum 5 can be made using 3 and 2.
समाधान दृष्टिकोण
फाइबोनैचि संख्याओं का उपयोग करके हम योग प्राप्त कर सकते हैं क्योंकि कोई भी संख्या 1 एक फाइबोनैचि संख्या है। 1 n बार जोड़ने पर योग n के रूप में मिल सकता है। हमारा काम फिबोनाची संख्याओं की संख्या को कम करना है जो योग देता है। हम सिक्का परिवर्तन समस्या से आधार लेकर समाधान प्राप्त कर सकते हैं जहां सिक्कों में फाइबोनैचि संख्या मान होते हैं। प्रोग्रामिंग भाषा में, इस समस्या को हल करने की तकनीक को लालची दृष्टिकोण कहा जाता है।
सबसे पहले, हम फाइबोनैचि संख्याओं को योग n से कम या उसके बराबर तक जोड़ते हैं। फिर अंतिम पद से शुरू करके हम उस पद को n से n>kवें पद तक घटाते हैं। और साथ-साथ, पदों की संख्या की संख्या बढ़ाएँ। उस बिंदु पर जब n
फिबोनाची शब्दों की गणना के लिए एक फ़ंक्शन बनाएं।
उन सभी फाइबोनैचि शब्दों की गणना करें जो n से कम या उसके बराबर हों।
यदि अगला पद n से बड़ा है, तो इसे सदिश में न धकेलें और वापस लौटें।
n के बराबर योग वाले फाइबोनैचि पदों की न्यूनतम संख्या ज्ञात करने के लिए एक फ़ंक्शन बनाएं।
फिबोनाची शब्दों को संग्रहीत करने के लिए एक वेक्टर प्रारंभ करें।
योग n से योग>0 तक फाइबोनैचि शब्दों को घटाएं।
योग में योगदान करने वाले शब्दों की संख्या ज्ञात करने के लिए योग n को jth फाइबोनैचि शब्द से विभाजित करें।
प्राप्त गणना को आउटपुट के रूप में प्रिंट करें।
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रमएल्गोरिदम
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void findFiboTerms(vector<int>& fiboVals, int K){
int i = 3, nextTerm;
fiboVals.push_back(0);
fiboVals.push_back(1);
fiboVals.push_back(1);
while (1) {
nextTerm = fiboVals[i - 1] + fiboVals[i - 2];
if (nextTerm > K)
return;
fiboVals.push_back(nextTerm);
i++;
}
}
int findTermForSum(int K){
vector<int> fiboVals;
findFiboTerms(fiboVals, K);
int termCount = 0, j = fiboVals.size() - 1;
while (K > 0) {
termCount += (K / fiboVals[j]);
K %= (fiboVals[j]);
j--;
}
return termCount;
}
int main(){
int K = 11;
cout<<"Minimum Fibonacci terms with sum equal to K is "<<findTermForSum(K);
return 0;
} आउटपुट
Minimum Fibonacci terms with sum equal to K is 2