Số ván chơi tối đa của người thắng trong C++

Đề bài

Có N người chơi giải đấu. Tìm số ván chơi tối đa của người thắng. Quy tắc: hai người chỉ được chơi nhau nếu chênh lệch số ván đã chơi không quá 1.

Ví dụ

Nếu 3 người chơi thì cần 2 ván:

• Ván 1: người 1 vs người 2
• Ván 2: người 2 vs người thắng ván 1

Thuật toán

1. Tính số người tối thiểu cần thiết để người thắng chơi x ván. Gọi dp[i] = số người tối thiểu để người thắng chơi i ván
2. Quan hệ đệ quy: dp[i + 1] = dp[i] + dp[i - 1] vì á quân chơi (i-1) ván, quân thắng chơi i ván, và tất cả đối thủ đều khác nhau
3. Đây là dãy Fibonacci: dp[i] = dp[i-1] + dp[i-2]
4. Kết quả: chỉ số của số Fibonacci lớn nhất ≤ N

Chương trình C++

#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;
}

Kết quả

Maximum games required to decide winner = 2

Giải thích

Dãy Fibonacci: 1, 2, 3, 5, 8, 13, 21... Với N người, người thắng chơi tối đa F(k) ván với F(k) ≤ N < F(k+1).