C++でコインゲームの勝者を予測する方法

問題概要

このゲームには2人のプレイヤーXとYが登場します。両者が最適な戦略でプレイし、Xが先手である場合、どちらが勝利するかを予測するのが私たちのタスクです。

ゲームのルール

コインゲームでは、それぞれN枚とM枚のコインが入った2つの山が用意されています。プレイヤーの一方がゲームに使う山を1つ選び、選んだ山を半分ずつに分割していきます。これを、どちらかのプレイヤーがそれ以上分割できなくなるまで繰り返します。

具体例

問題を理解するために、具体例を見てみましょう。

Input: M = 2 , N = 2
Output: X

解説 − Xが先手でMの山を選び(どちらの山も同じ枚数)、山を2つに分割します。すると各山にはコインが1枚しか残らないため、Yは手詰まりとなり、Xの勝利が確定します。

解法のアプローチ

この問題を解くには、プレイヤーXが勝利する条件を見極める必要があります。Xが勝つのは、どちらかの山に偶数枚のコインがある場合です。両方の山が奇数枚であれば、Yが勝者となります。

このロジックを実装したプログラムが以下の通りです。

実装例

#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<<"Game Starts!\n";
   if(isXWinner(M,N))
      cout<<"Player X is the Winner";
   else
      cout<<"Player Y is the Winner";
   return 0;
}

出力

Game Starts!
Player X is the Winner