time 
设为首页】【收藏本站
当前位置: 主页 > 程序设计 > C\C++\VC > C语言 > C语言编程——取石子游戏实例解答

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

时间:2009-09-20 23:31 点击:3503次 字体:[ ]




  <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)的两个分量同时减少,则由于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势。



本文地址 : http://www.fengfly.com/plus/view-77338-1.html
标签: 石子游戏 C编程
------分隔线----------------------------
最新评论 查看所有评论
发表评论 查看所有评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码:
本栏分类