C++ में विजेता द्वारा खेले गए अधिकतम खेल

समस्या कथन

N खिलाड़ी हैं जो एक टूर्नामेंट खेल रहे हैं। हमें विजेता द्वारा खेले जा सकने वाले अधिकतम खेलों की संख्या ढूंढनी है। इस टूर्नामेंट में, दो खिलाड़ियों को एक-दूसरे के खिलाफ खेलने की अनुमति केवल तभी है जब उनके द्वारा खेले गए खेलों का अंतर एक से अधिक न हो।

उदाहरण

यदि 3 खिलाड़ी हैं तो विजेता तय करने के लिए 2 खेलों की आवश्यकता होती है -

खेल - 1: खिलाड़ी 1 बनाम खिलाड़ी 2

खेल - 2: खिलाड़ी 2 बनाम खेल - 1 का विजेता

एल्गोरिदम

• हम इस समस्या को हल कर सकते हैं पहले यह गणना करके कि विजेता द्वारा x खेल खेलने के लिए न्यूनतम कितने खिलाड़ियों की आवश्यकता है। एक बार इसकी गणना हो जाने पर वास्तविक समस्या इसका व्युत्क्रम है। अब मान लें कि dp[i] न्यूनतम खिलाड़ियों की संख्या दर्शाता है ताकि विजेता i खेल खेले
• हम dp मानों के बीच एक पुनरावर्ती संबंध लिख सकते हैं: dp[i + 1] = dp[i] + dp[i - 1] क्योंकि यदि उपविजेता ने (i - 1) खेल खेले हैं और विजेता ने i खेल खेले हैं और वे सभी खिलाड़ी जिनके खिलाफ उन्होंने मैच खेला है वे असंयुक्त हैं, तो विजेता द्वारा खेले गए कुल खेल उन दो सेट के खिलाड़ियों का योग होंगे।
• उपरोक्त पुनरावर्ती संबंध को इस प्रकार लिखा जा सकता है: dp[i] = dp[i - 1] + dp[i - 2] जो फाइबोनैचि श्रृंखला के समान संबंध है, इसलिए हमारा अंतिम उत्तर उस अधिकतम फाइबोनैचि संख्या का इंडेक्स होगा जो इनपुट में दिए गए खिलाड़ियों की संख्या से कम या बराबर है

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 

int getMaxGamesToDecideWinner(int n) {
    int dp[n];
    dp[0] = 1;
    dp[1] = 2;
    int idx = 2;
    do {
        dp[idx] = dp[idx - 1] + dp[idx - 2];
    } while (dp[idx++] <= n);
    return (idx - 2);
}

int main() {
    int players = 3;
    cout << "Maximum games required to decide winner = " << getMaxGamesToDecideWinner(players) << endl;
    return 0;
}

आउटपुट

जब आप उपरोक्त प्रोग्राम को कंपाइल और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है -

Maximum games required to decide winner = 2