คำชี้แจงปัญหา
มีผู้เล่น 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
