「石取りゲーム１」の編集履歴（バックアップ）一覧はこちら

「石取りゲーム１」(2010/01/25 (月) 19:09:49) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

一山の石から交互に取り、最後に石を取った方が負けとなるゲーム。
ルールは以下のとおり。
-N個の石から交互に石を取る
-一回に取れる石はM個（ M < N ）である
-最後に石を取ったほうが負け
-パスはできない

石取りゲームのアルゴリズムは以下の通りである。 1回に取れる石数を3個とした時、相手が1, 2, 3個の石を取った時、自分は3, 2, 1個の石を取ることにする。そうすれば、石は毎回4個減ることになる。よって、残りの石数を (4k+1) 個にできれば、相手に最後の1個を残すことができる。 

一般に、1回に取れる石数がM個であれば、残りの石数を k×(M+1)+1個（kは任意の整数）にできれば、上記方法で勝つことができる。もし残りの石数が k×(M+1)+1個 でなければ、ランダムな個数をとって相手の敗着を待つ。 
#asciiart(blockquote){
#prompt
Dim n As Integer
Dim m As Integer
Dim x As Integer
Dim my_turn As Integer

Input "石の数 "; n
Input "1回に取れる石数 "; m
If n < 1 Or m < 1 Then
    Print "石数が足りません"
    End
End If

Randomize
my_turn = Int(Rnd() * 2)
While n <> 0
    my_turn = my_turn Xor 1
    If my_turn Then
        x = (n - 1) Mod (m + 1)
        If x = 0 Then
            Do
                x = Int(Rnd() * m) + 1
            Loop While x > n
        End If
        Print "コンピューターは"; x; "個の石を取ります"
    Else
        Do
            Input "何個の石を取りますか "; x
        Loop While x < 1 Or x > n Or x > m
    End If
    n = n - x
    Print "残りの石数は"; n; " 個です"
Wend

If my_turn Then
    Print "あなたの勝ちです"
Else
    Print "コンピューターの勝ちです"
End If
}