資料結構
網路
關係資料庫管理系統(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 次瀏覽
廣告