一维反Nim游戏

无心人

先手输的最有意义了 能判定很多局面的胜

mathe

我还没有整理出来。 scode2.cpp (13.03 KB, 下载次数: 4)

2008-9-13 21:48 上传

点击文件名下载附件

你可以看一下附件中代码，所有这些检查对于我现在产生的数据都能够通过

无心人

有点乱 呵呵

mathe

就看main函数就可以了，其它部分代码都没有用，是挺乱的。数据格式看那些printf里面的内容应该可以猜出来。

无心人

晕，你起这么早做什么啊 似乎你的代码能简化掉 可以不用这么多的判断 做个函数么？ 另外，呵呵 混合C和C++ 感觉真怪，呵呵

mathe

这个代码只是一个临时用于过滤一些数据的小程序,我从一个比较复杂的代码上修改过来,大部分代码没有用处(除了main函数),每找到一个规律,我就添加一个条件语句,所以比较乱: 现在已经分析出$n<=10$的所有规律。 我们采用类似前面的记号，但是用O表示奇数，E表示偶数(数字0也算偶数)，A表示不小于1的任意整数 表示2+2*3表示1个2和两个3的局面 2*2+O*1表示两个2和奇数个1 A*5+4表示至少一个5再加上一个4。 另外我们采用一种扩充方案，比如O*(1+4+9)代表1，4，9的数目之和为奇数的局面，比如2*4+1*1就包含在其中,还有对于同时满足多个规律的状态,采用第一个满足的规律 于是有: f(O*(1+4+9))=0,f(E*(1+4+9))=1, f(2)=1,f(2+O*1)=2,f(2+E*1)=3,f(E*2+E*1)=0,f(E*2+O*1)=1,f(O*2+O*1)=3,f(O*2+E*1)=2 f(3+O*1)=3,f(3+E*1)=2,f(3+E*2+E*1)=3,f(3+E*2+O*1)=2,f(3+O*2+O*1)=0,f(3+O*2+E*1)=1 f(3+O*(9+4+1))=3,f(3+E*(9+4+1))=2,f(2+O*(9+4+1))=2,f(2+E*(9+4+1))=3 f(A*5+O*(4+1))=0,f(A*5+E*(4+1))=1,f(A*5+2+O*(4+1))=2,f(A*5+2+E*(4+1))=3,f(A*5+3+O*(4+1))=3,f(A*5+3+E*(4+1))=2 f(6+O*(9+4+1))=3,f(6+E*(9+4+1))=2,f(6+A*5+O*(4+1))=3,f(6+A*5+E*(4+1))=2 f(7+O*(9+4+1))=2,f(7+E*(9+4+1))=3,f(7+A*5+O*(4+1))=2,f(7+A*5+E*(4+1))=3 f(10+A*5+O*(4+1))=2,f(10+A*5+E*(4+1))=3,f(10+O*(9+4+1))=2,f(10+E*(9+4+1))=3 ... 当然最后还有一个规律,f(A)=g(A),也就是所有不满足上面规律的都直接套用46#的g函数. 这样,对于每个状态我们都可以得出一个状态数,状态数为0的状态是先手负,其它状态是先手胜(总可以通过一次变换成为状态0)

mathe

有了这些信息,我们就可以知道面对一个最大数不超过10的状态时候,应该采用何种策略. 比如遇上2*5,我们查询上面状态,知道f(A*5+E*(4+1))=1,所以是先手胜的状态. 2*5可以变换出来状态有5+4,5+3,5+3+1,5+2*2,5+2+1 分别查询它们的函数值有f(5+4)=0,f(5+3)=2,f(5+3+1)=3,f(5+2*2)=s[5]=4,f(5+2+1)=2 所以我们知道只能变换到5+4

无心人

现在问题是是否存在一个最小集 比如3+2+1和4+1+1就能决定9的先手负 所以是否存在这么个集合 使得能决定某种范围的局面的状态

mathe

======= 3+2+1和4+1+1就能决定9的先手负 ======= 这个要看你分析到多少步了,比如所有的步骤最终都可以决定于1+1+1+...+1的情况

无心人

我这么解析 9先手后局面列表 8 7 1+7 2+6 3+5 4+4 1+6 2+5 3+4 前两个均先手胜 后面的均能拆分成 1+2+3或者1+1+4 所以都是先手胜 既然9的先手局面都是先手胜 所以9就是先手负了