C++ में योग K के बराबर न्यूनतम फाइबोनैचि पद

समस्या विवरण

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

फाइबोनैचि श्रृंखला पिछली दो संख्याओं को जोड़कर बाद की संख्याएं उत्पन्न करती है। फाइबोनैचि श्रृंखला दो संख्याओं से शुरू होती है - F0 और F1। F0 और F1 के प्रारंभिक मान 0, 1 या 1, 1 लिए जा सकते हैं।

फाइबोनैचि श्रृंखला: 0, 1, 1, 2, 3, 5, 8, 13, ...

उदाहरण

इनपुट

K = 5

आउटपुट

2

व्याख्या: योग 5 को 3 और 2 का उपयोग करके बनाया जा सकता है।

हल का दृष्टिकोण

फाइबोनैचि संख्याओं का उपयोग करके हम किसी भी संख्या का योग प्राप्त कर सकते हैं क्योंकि 1 एक फाइबोनैचि संख्या है। 1 को n बार जोड़ने से योग n प्राप्त हो सकता है। हमारा कार्य योग देने वाली फाइबोनैचि संख्याओं की गिनती को न्यूनतम करना है। हम इसे सिक्का परिवर्तन समस्या से आधार लेकर हल कर सकते हैं जहां सिक्कों के मान फाइबोनैचि संख्याएं हैं। प्रोग्रामिंग भाषा में, इस समस्या को हल करने की तकनीक को लालची दृष्टिकोण (greedy approach) कहा जाता है।

सबसे पहले, हम फाइबोनैचि संख्याओं को n से कम या बराबर होने तक जोड़ते हैं। फिर अंतिम पद से शुरू करके हम उस पद को n से घटाते हैं जब तक n > kवां पद। साथ-साथ, पदों की संख्या की गिनती बढ़ाते हैं। जब n < kवां पद हो जाता है, तो उस आसन्न फाइबोनैचि पद पर जाएं जो n से कम या बराबर हो और उस गिनती का मान प्रिंट करें।

एल्गोरिदम

1. K तक के सभी फाइबोनैचि पदों की गणना करने के लिए एक फंक्शन बनाएं
2. K से कम या बराबर सभी फाइबोनैचि पदों की गणना करें
3. यदि अगला पद K से बड़ा है, तो उसे वेक्टर में न डालें और वापस लौटें
4. न्यूनतम फाइबोनैचि पदों को खोजने के लिए एक फंक्शन बनाएं जिनका योग K के बराबर हो
5. फाइबोनैचि पदों को संग्रहीत करने के लिए एक वेक्टर प्रारंभ करें
6. योग K से फाइबोनैचि पदों को घटाएं जब तक योग > 0
7. योग K को jवें फाइबोनैचि पद से विभाजित करके उन पदों की संख्या खोजें जो योग में योगदान करते हैं
8. प्राप्त गिनती को आउटपुट के रूप में प्रिंट करें

C++ कार्यान्वयन

#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 (true) {
        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 << "K के बराबर योग वाले न्यूनतम फाइबोनैचि पद हैं " << findTermForSum(K);
    return 0;
}

आउटपुट

K के बराबर योग वाले न्यूनतम फाइबोनैचि पद हैं 2

व्याख्या: 11 = 8 + 3 (2 पद)

जटिलता विश्लेषण

• समय जटिलता: O(log K) - फाइबोनैचि संख्याएं घातीय रूप से बढ़ती हैं
• स्पेस जटिलता: O(log K) - फाइबोनैचि पदों को संग्रहीत करने के लिए

महत्वपूर्ण अंतर्दृष्टि

लालची दृष्टिकोण यहां काम करता है क्योंकि फाइबोनैचि संख्याएं एक विहित सिक्का प्रणाली बनाती हैं जहां प्रत्येक संख्या पिछले दो के योग से बड़ी होती है, जिससे लालची चयन इष्टतम होता है।