石拾いゲーム 2

石拾いゲーム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合計を維持させていけばされます。詳細は直接見つけてください。