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