C++中获胜者参与的最大游戏场数

问题陈述

有N个玩家正在参加一个锦标赛。我们需要找到获胜者可能参加的最大游戏场数。在这个锦标赛中，只有当两个玩家参加的游戏场数之差不大于1时，他们才允许互相比赛。

示例

如果有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

Narendra Kumar

更新于：2020年1月10日

443 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习