คำอธิบายปัญหา
มีผู้เล่น 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] ซึ่งเป็นความสัมพันธ์เดียวกับลำดับฟีโบนัชชี (Fibonacci series) ดังนั้นคำตอบสุดท้ายจะเป็นดัชนีของจำนวนฟีโบนัชชีที่มากที่สุดซึ่งน้อยกว่าหรือเท่ากับจำนวนผู้เล่นที่ให้มาในนำเข้า
ตัวอย่างโค้ด
#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
