找回密码
 欢迎注册
楼主: medie2005

[转载] 一维反Nim游戏

[复制链接]
发表于 2008-9-13 20:53:53 | 显示全部楼层
先手输的最有意义了
能判定很多局面的胜
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-13 21:48:50 | 显示全部楼层
我还没有整理出来。
scode2.cpp (13.03 KB, 下载次数: 4)
你可以看一下附件中代码,所有这些检查对于我现在产生的数据都能够通过
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-13 21:56:06 | 显示全部楼层
有点乱
呵呵
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-14 05:53:07 | 显示全部楼层
就看main函数就可以了,其它部分代码都没有用,是挺乱的。数据格式看那些printf里面的内容应该可以猜出来。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-14 07:02:21 | 显示全部楼层
晕,你起这么早做什么啊
似乎你的代码能简化掉
可以不用这么多的判断
做个函数么?

另外,呵呵
混合C和C++
感觉真怪,呵呵
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-14 14:53:37 | 显示全部楼层
这个代码只是一个临时用于过滤一些数据的小程序,我从一个比较复杂的代码上修改过来,大部分代码没有用处(除了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)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-14 15:02:20 | 显示全部楼层
有了这些信息,我们就可以知道面对一个最大数不超过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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-15 19:08:46 | 显示全部楼层


现在问题是是否存在一个最小集
比如3+2+1和4+1+1就能决定9的先手负

所以是否存在这么个集合
使得能决定某种范围的局面的状态
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-16 18:37:25 | 显示全部楼层
=======
3+2+1和4+1+1就能决定9的先手负
=======
这个要看你分析到多少步了,比如所有的步骤最终都可以决定于1+1+1+...+1的情况
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-16 20:29:04 | 显示全部楼层


我这么解析
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就是先手负了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 17:43 , Processed in 0.045125 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表