| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 459 人关注过本帖
标题:wythoffGame 取石子游戏
只看楼主 加入收藏
红衣落桂花
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2011-2-13
收藏
 问题点数:0 回复次数:0 
wythoffGame 取石子游戏
有两堆石子,不妨先认为一堆有 10,另一堆有 15 个,双方轮流取走一些石子,合法的取法有如下两种:
1、在一堆石子中取走任意多颗;
2、在两堆石子中取走相同多的任意颗;
约定取走最后一颗石子的人为赢家,求必胜策略。

两堆石头地位是一样的,我们用余下的石子数(a,b)来表示状态,并画在平面直角坐标系上。和前面类似,(0,0)肯定是 P 态,又叫必败态或者奇异局势。(0,k),(k,0),(k,k) 系列的节点肯定不是 P 态,你面对这样的局面一定会胜,只要按照规则取一次就可以了。再看 y = x 上方未被划去的格点,(1,2)是 P 态。k > 2 时,(1,k)不是 P 态,比如你要是面对(1,3)的局面,你是有可能赢的。同理,(k,2),(1 + k,2 + k)也不是 P 态,划去这些点以及它们的对称点,然后再找出 y = x 上方剩余的点,你会发现(3,5)是一个 P 态,如此下去,如果我们只找出 a <= b 的 P 态,则它们是(0,0),(1,2),(3,5),(4,7),(6,10)。。。。。。它们有什么规律吗?
忽略(0,0),很快会发现对于第 i 个 P 态的 a,a = i * (sqrt(5) + 1)/2 然后取整。。。而 b = a + i。居然和黄金分割点扯上了关系。

假设面对的局势是(a,b),若 b = a,则同时从两堆中取走 a 个物体,就变为了奇异局势(0,0);假定当前奇异局势是(a[k],b[k]),如果 a = a[k] ,b > b[k],那么,取走 b - b[k] 个物体,即变为奇异局势;如果 a = a[k] , b < b[k] ,则同时从两堆中拿走 a[k] - a[b - a[k]] 个物体,变为奇异局势( a[b - a[k]] , a[b - a[k]] + b - a[k]);如果a > a[k] ,b= a[k] + k,则从第一堆中拿走多余的数量a - a[k] 即可;如果 a < a[k] ,b= a[k] + k,分两种情况,第一种,a=a[j] (j < k),从第二堆里面拿走 b - b[j] 即可;第二种,a=b[j] (j < k),从第二堆里面拿走 b - a[j] 即可。

从如上性质可知,两个人如果都采用正确操作,那么面对非奇异局势,先拿者必胜;反之,则后拿者取胜。

这里呢,有一个小程序,是判断这两堆是否是奇异局势:

void  main()
{
int a,b,c;
const double d=1.6180339887498948482045;
while(scanf("%d,%d",&a,&b)!=EOF)
{
if(a==b)printf("1/n");continue;
else if(a<b){c=b-a}
else (a>b)
{
c=a-b;a=b;
}
if(a==(int)c*d) printf("1/n");
else printf("0/n");
}
搜索更多相关主题的帖子: 游戏 
2011-07-01 15:30
快速回复:wythoffGame 取石子游戏
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.075769 second(s), 9 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved