石取りゲーム２ - abwiki @ ウィキ (ActiveBasic非公式wiki)

一山の石から交互に石を取り、最後に石を取ったものが勝ちである。
ルールは以下のとおり。
N個の石から交互に石を取る
一回に取れる石は、相手が直前に取った石数の2倍以内
最初に全ての石を取ってはならない
最後に石を取ったほうが勝ち
パスはできない

例えば、最初に20個の石があったとすれば、先手が取れるのは1～19個である。 仮に3個とったとすれば、後手は2倍の6個までの石を取ることができる。

コンピューターの取る石数は Fibonacci(フィボナッチ)数列 （この数列に含まれている数をFibonacci数という）[1]を使って、以下のように定めている。
まず、残りの石数を下記方法を用いてFibonacci数の和として表す（ex:N=20）
石数を超えない最大のFibonacci数を求める（ex:最大Fibonacci数=13）
上記Fibonacci数と石数との差を求める（ex:差=20-13=7）
その差を越えない最大のFibonacci数を求め、さらに差を求める（ex:最大Fibonacci数=5⇒差=7-5=2）
上記差を求め続け、元の石数をFibonacci数の和として表す（ ex：20 = 13 + 5 + 2 ）
最小のFibonacci数の石数を取る

Fibonacci数列の定義より、この和のなかには隣り合う2つのFibonacci数が現れることは無い。そのため、和（ex：20=13+5+2）の各項は右隣の項の2倍よりも大きいことは自明である。したがって、石の数が13+5+2であれば、コンピュータが2個取った時、相手は5個取ることができないので Fibonacci数の個数を減らすことができない。よって、最後の石を取るのはコンピュータとなる。ただし、最初の石数がFibonacci数であったときはこの限りではないので、適当な数だけ取って相手の敗着を待つこととする。

#prompt
Dim i As Integer
Dim n As Integer
Dim x As Integer
Dim max As Integer '取ることのできる最大の石数
Dim my_turn As Integer
Dim f[21] As Integer

'Fibonacci数列の作成
f[1] = 1
f[2] = 1
For i = 3 To 20
f[i] = f[i - 1] + f[i - 2]
Next i

Input "石の数は(2 - 10000)"; n
If n < 2 Or n > 10000 Then
Print "石数が足りません"
End
End If

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

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