石拾いゲーム2
石をお互いに拾います。石を最後に取る人がゲームで勝ちます。ただし、相手が持っていった石の2倍を超えて拾うことができません。
石拾いパズルとフィボナッチ数列
例えば、最初に32個の石がある場合は、まず取ることは最初の1つから31個まで拾うされます。
コンピュータは、Fibonacci数列（1、1、2、3、5、8、13、21、34、…..）を使用して残す石の数を計算します。
Fibonacci数列（作られた原理）
1
1 = 1
2 = 1 + 1
3 = 1 + 2
5 = 2 + 3
8 = 3 + 5
13 = 5 + 8
21 = 8 + 13
34 = 13 + 21
… …
n1 …
n2 …
n3 = n1 + n2
例えば、石が32個であれば、32以下の最大Fibonacci数は21であり、32-21=11以下の最大Fibonacci数は8であり、32-21-8=3はFibonacci数であるため、32=21+8+3に表示されます。
そう、すべての数は、Fibonacci数の和として表すことができます。数列の各段階の下の数は上の2倍よりも大きいです。この点を利用すれば、コンピュータを打つことができます。
つまり、21は8の2倍よりも大きく、8は3の2倍よりも大きいです。
したがって、石の数が21+8+3つのといえば、コンピュータは3つの拾って、Fibonacci合計を維持させようとします。このような場合、ユーザは、8個を拾うことができなくなります。コンピュータがFibonacci数の合計を維持させると、最後に石を取る勝者は、コンピュータがされます。この戦略を使用していないのは、初めての石の数が偶然にFibonacci数だったときです。このとき、コンピュータは、方法がないため、一つ取り、たまたま相手の敗北を待ちます。
* 勝利の戦略：コンピュータの代わりに、ユーザがFibonacci合計を維持させていけばされます。詳細は直接見つけてください。