JAVA算法:一排石头的游戏(博弈过程详细分析)
问题描述
N块石头排成一行,每块石头都有各自固定的位置和编号。两名玩家依次取石头,每个玩家每次可以取其中任意一块石头,或者相邻的两块石头,石头在游戏过程中不能移位(即编号不会改变),最后能将剩下的石头一次取光的玩家获胜。
问:这个游戏有必胜的策略吗?
问题分析
N块石头排成一排,我们不知道N是多少,所以我们从最简单的数入手来试图找到一些规律。
限制条件是每个玩家每次可以取其中任意一块石头,或者相邻的两块石头;石头不能移位(即编号不会改变)。
- 当 N=0 时,没得玩,不讨论。
- 当 N=1 时,先手者获胜。(即谁先取,谁获胜。)
- 当 N=2 时,先手者获胜,可以一次取相邻的两块石头。(即谁先取,谁获胜。)
- 当 N=3 时,我们为石头编号为:1,2,3,如下图所示:
| 1 | 2 | 3 |