关于搬山游戏的算法题

Question

题目：设有n座山，计算机与人作为比赛的双方，双方轮流搬山。规定每次搬山的数目不能超过k座，谁搬最后一座谁输，每次允许搬山的最大数目(k)。谁都可以先开始搬，双方轮流搬山直到最后一座山搬完为止。这是题目，设计一个程序不难，简单点，我们假设总数n=100，k=10。下边是难题，如何设一个计算机的搬山算法，不论在谁先开始搬的情况下，都是计算机获胜？欢迎大家讨论啊。

Answer 1

就是循环操作，n每次减k,当n<10时谁操作时谁获胜

Answer 2

其实如果把数字设置大  n=100  k=99的话必定先搬的赢我们假设k < n/2 -1  不考虑上边特殊情况会不会有算法让计算机必胜呢如果正常情况下  计算的搬山数量应该是 (剩余的山-1)/(k+1)  如果结果为0  就搬1个。但是这种情况不能保证计算机必胜。

Answer 3

这个问题叫做巴什博奕（Bash Game）只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。    显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m),那么先取者要拿走s个物品，如果后取者拿走k（≤m)个，那么先取者再拿走m+1-k个，结果剩下（m+1）（r-1）个，以后保持这样的取法，那么先取者肯定获胜。总之，要保持给对手留下（m+1）的倍数，就能最后获胜

Answer 4

这个用笔就可以算，100和10的话，只要求mod 11就好，mod 11 = 0的话，先手负，否则先手胜。
100 % 11 = 1，所以先拿的赢，先拿1个，之后无论对手拿多少个(设为k个)，你就拿11 - k个，最后就赢了。
这个属于最简单的nim问题，还有许多复杂的变化，比如只可以拿2的幂......

Answer 5

当k=10 就是mod  11了吧。  我知道这个规律，我意思是说不管怎么样，能不能总让一方赢呢？就算 mod 11=0的情况出现了？ 是不是无解了？

Answer 6

这个不可能，如果mod 11 = 0的话，只要对方不犯错，先手肯定会输的。
不过可以把规则弄复杂一些，是人都会犯错误的。

Answer 7

是啊，当时我就想了， 如果  k=10的时候  如果 mod 11 = 0 ，那就必输无疑了。哎，看来又是个无解了哦。

Answer 8

不可能100％赢的，胜率看m，先手的胜率为m/(m+1)，后手的胜率为1/(m+1)，m一般要大于1，所以，m越大，先手的胜率就越大，但不管如何，先手的胜率都大于50％。