アルゴリズムの学習(003/XXX)

　コンピュータ科学を学ぶべくアルゴリズムを学んでいく。参考として定番書であり古典的名著でもある

［改訂新版］C言語による標準アルゴリズム事典 Software Technology

作者:奥村晴彦
技術評論社

を用いる。実装には勉強もかねてC#を使う。

4.　石取りゲーム1

以下のルールで石取りゲームを行う：

	(1)	石の数 $n$ および1回で取れる石の最大数 $m$ を決めた上で、相手→自分の順番で石を取っていく。
	(2)	最後の1個を取った方が負けになる。
	(3)	パスはできない。

このゲームは残った石の数を $(m+1)k+1$ 個( $k\in\mathbb{N})にできれば、相手の取った数と自分の取った数が[tex:m+1$ になるように自分の取る数を決めることで必ず勝つことができる。このような形にできなければ $1$ 個だけ取って相手の敗着を待つ。

using System;
using System.Collections.Generic;
using System.Linq;

namespace Ishitori
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, m, r, my_turn;
            int x = 1;

            Console.WriteLine("石の数は?");
            n = int.Parse(Console.ReadLine());

            Console.WriteLine("1回で取れる石の最大数は?");
            m = int.Parse(Console.ReadLine());

            // 例外処理
            if(n < 1)
            {
                throw new Exception("石の数は正の整数を指定してください。");
            }

            if (m < 1)
            {
                throw new Exception("1回で取れる石の最大数は正の整数を指定してください。");
            }

            for (my_turn =1; n !=0; my_turn ^= 1) //^=は排他的論理和で左辺と右辺が一致すれば0,そうでなければ1を返す
            {
                if (my_turn == 1)
                {
                    x = (n - 1) % (m - 1);
                    if (x == 0) x = 1;
                    Console.WriteLine("私は{0}個の石を取ります。",x);
                }
                else
                {
                    do
                    {
                        Console.WriteLine("あなたは何個取りますか?");
                        r = int.Parse(Console.ReadLine());
                        x = r;
                    } while (r < 1 || x <= 0 || x > m || x > n);
                }
                n -= x;
                Console.WriteLine("残りは{0}個です。", n);
            }
            if (my_turn==1) {
                Console.WriteLine("あなたの負けです。");
            }
            else
            {
                Console.WriteLine("あなたの勝ちです。");
            }
        }
    }
}

　結果は以下のとおり：

4. 石取りゲーム1

4.　石取りゲーム1