拈游戏

来自计算思维百科
跳转至: 导航搜索
拈游戏.jpg

拈游戏是一种博弈游戏:有一堆棋子,两个玩家轮流从这堆棋子中拿走一定数量(最少1个,最多的由所有玩家提前规定,游戏过程中不可改变)的棋子,每次拿走的棋子数量可以不同,哪个玩家能够胜利拿到最后那个棋子?是先走的还是后走的?

解决方案

拈游戏在1612年就出现在一本关于休闲数学的书中,作者是Claude-Gaspar Bachet,一位法国贵族数学家。

拈游戏中会有若干堆棋子,但是我们先来考虑一堆棋子的情况,假设一堆棋子的个数为n个,甲、乙两个玩家,规定每次只能拿走最少1个最多m个棋子,假设甲先拿。

情况一:如果棋子数量大于等于1,小于等于拿棋数量的上限,即1≤n≤m,那么甲只要第一次把所有的棋子拿走就赢了;

情况二:如果棋子数量刚好比拿棋数量上限多1,即n=m+1,那么甲第一次无论怎么拿都会使得剩下的棋子数在1~m之间,只要乙把所有的棋子拿走,甲就输了;

情况三:如果棋子数量与拿棋数量上限满足m+2≤n≤2m+1,那么甲只要第一次拿走棋子后使得剩下的棋子数n=m+1,那么下次乙拿的时候是属于情况二,所以乙一定会输。

根据上述三种情况的分析,只有当棋子数n不是m+1的倍数时,甲只要每次拿走

n mod (m+1)(n对m+1求余数)个棋子后,剩下的棋子数一定是m+1的倍数,那么甲就一定会赢。

可以体现的计算思维

找策略时是考虑规模最小的情况,找到最小规模问题的解决方案,然后再将大规模问题分解成小规模问题。拈游戏取胜的策略体现出“分解”的计算思维,从数量为n的棋子堆中分出数量为m+1最大倍数的棋子堆,取走余下的棋子就能获胜。分解是一种简化问题求解的方法,分解方法能够“自顶而下,逐步求精”,做出对问题本身的明确描述,并对问题揭发做出全局性决策,把问题分解成相对独立的子问题,再以同样的方式对每一个问题进行精细化,直到获得明确解答。拈游戏的解决方法体现了计算思维的“约简”特点。