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