C语言编程——取石子游戏实例解答

　　<1>小红是个游戏迷，他和小蓝一起玩拿石子游戏。游戏规则为2个人轮流拿石子。一次可以拿1颗或3颗，规定谁取到最后一颗石子谁就胜出。最后决定由小红先取。两人都是游戏高手，该赢的绝不会输。问在知道石子总数的情况下，怎样快速预测谁将会胜出。
　
　　分析：
　
　　小红和小蓝各取一次共有三种情况：
　
　　①共取走2颗石子
　
　　②共取走4颗石子
　
　　③共取走6颗石子
　
　　设方案①取了N1次，方案②取了N2次，方案③取了N3次后，还剩下K个石子。最后K的取值有三种情况：0，1，3.设有石子S.则S=2*N1+4*N2+6*N3+K.其中2*N1+4*N2+6*N3=（1+1）*N1+（1+3）*N2+（3+3）*N3，说明取的过程为偶数次，所以剩下K时该最先取石子的人取。K=1，3则先取方胜。反之，另一方胜。又2*N1+4*N2+6*N3=2*（N1+2*N2+3*N3）为偶数，所以S的奇偶性取决于K，当K为偶数时，后取方胜，反之，线取方胜。
　
　　<2>有一种很有意思的游戏，就是有物体若干堆，可以是火柴棍或是围棋子等等均可。两个人轮流从堆中取物体若干，规定最后取光物体者取胜。这是我国民间很古老的一个游戏，别看这游戏极其简单，却蕴含着深刻的数学原理。下面我们来分析一下要如何才能够取胜。
　
　　（一）巴什博奕（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）的倍数，就能最后获胜。
　
　　这个游戏还可以有一种变相的玩法：两个人轮流报数，每次至少报一个，最多报十个，谁能报到100者胜。
　
　　（二）威佐夫博奕（Wythoff Game）：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
　
　　这种情况下是颇为复杂的。我们用（ak，bk）（ak ≤ bk ，k=0，1，2，……，n）表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。
　
　　可以看出，a0=b0=0，ak是未在前面出现过的最小自然数，而 bk= ak + k，奇异局势有如下三条性质：
　
　　1.任何自然数都包含在一个且仅有一个奇异局势中。
　
　　由于ak是未在前面出现过的最小自然数，所以有ak > ak-1 ，而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 .所以性质1.成立。
　
　　2.任意操作都可将奇异局势变为非奇异局势。
　
　　事实上，若只改变奇异局势（ak，bk）的某一个分量，那么另一个分量不可能在其他奇异局势中，所以必然是非奇异局势。如果使（ak，bk）的两个分量同时减少，则由于其差不变，且不可能是其他奇异局势的差，因此也是非奇异局势。