Dự đoán người thắng cuộc trong trò chơi đồng xu trong C++

Trong trò chơi này, có hai người chơi X và Y. Nhiệm vụ của chúng ta là dự đoán ai sẽ thắng trò chơi nếu cả hai chơi tối ưu và X bắt đầu trò chơi.

Trò chơi

Trong trò chơi đồng xu, có hai đống với N và M số đồng xu. Một trong các người chơi chọn bất kỳ đống nào cho trò chơi. Sau đó nhiệm vụ là chia đống thành hai nửa cho đến khi bất kỳ người chơi nào không thể chia thêm đống nữa.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào: M = 2 , N = 2
Đầu ra: X

Giải thích - X bắt đầu trò chơi và chọn đống M (cả hai giống nhau), và chia đống thành hai. Bây giờ mỗi đống chỉ chứa một đồng xu, nên Y sẽ không còn nước đi. Điều này khiến X thắng.

Để giải quyết bài toán này, chúng ta cần xem cơ hội mà người chơi X thắng. Trường hợp người chơi X thắng là khi bất kỳ đống nào có số đồng xu chẵn. Ngược lại, Y sẽ là người thắng.

Chương trình minh họa triển khai logic của chúng ta

Ví dụ

#include <iostream>
using namespace std;
int isXWinner(int M, int N) {
    if (M % 2 == 0 || N % 2 == 0)
        return 1;
    return 0;
}
int main() {
    int M = 1, N = 2;
    cout<<"Trò chơi bắt đầu!\n";
    if(isXWinner(M,N))
        cout<<"Người chơi X là Người thắng";
    else
        cout<<"Người chơi Y là Người thắng";
    return 0;
}

Kết quả

Trò chơi bắt đầu! Người chơi X là Người thắng