数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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
更新于：2020年1月10日
443 次浏览
广告