一维反Nim游戏

无心人 · 发表于 2008-9-19 11:21:56

g函数转f函数的代码如何表示？

mathe · 发表于 2008-9-19 14:45:43

代码同采用的数据结构有关系呀. 其实主要就是判断当前局面是不是上面列出的特殊局面.如果不是,f(x)就等于g(x),如果是上面局面之一,那么f(x)=!g(x),其中!g(x)表示g(x)逻辑取反(有就是非零变0,0变非零)

mathe · 发表于 2008-9-20 13:45:05

另外，非常容易证明对于任意整数x,s[x]不是零，所以我们根据79#的结果，可以得出对于LZ的问题，当且仅当n是1,4,9,12,20时先手输

无心人 · 发表于 2008-9-20 16:09:24

很精妙的结论哦

mathe · 发表于 2008-9-20 16:30:14

结论是挺不错的,不过还没有证明.还需要写个程序来证明.不过现在公式已经得出,如果公式没有错误,后面用来证明的程序相对来说要容易写很多了.

mathe · 发表于 2008-9-23 18:37:24

关于这个题目，用计算机将这些模板全部拆分成简单模板。然后又让计算机将所有可以直接到达这些模板的状态计算出来如附件,分别给出了 Rules: (也就是所有上面的模板）和 Check List: (也就是上面两类的并集）

output.zip (7.21 KB, 下载次数: 3) 只要我们能够验证所有在Check List中状态全部符合上面的规律，那么这个结论就没有错了。初步用计算机分析结果来看应该没有问题，只是两类模板之间匹配的代码有点麻烦，我现在写的程序还不能完全处理。

mathe · 发表于 2008-9-25 16:02:29

弄了个计算机验证的程序，它可以过滤大部分情况的正确性，然后余下一下几个模板需要手工证明其正确性： +1*9+E*5+E*4+E*1 +1*12+E*5+E*4+E*1 +1*9+E*5+O*4+O*1 +1*12+E*5+O*4+O*1 +E*20+E*17+E*12+E*9+1*5+E*4+O*1 +E*20+E*17+E*12+O*9+O*4+O*1 +E*20+E*17+E*12+E*9+1*5+O*4+E*1 +E*20+E*17+E*12+O*9+E*4+E*1 +1*25+E*20+E*17+E*12+O*9+O*4+E*1 +1*25+E*20+E*17+E*12+O*9+E*4+O*1 程序见附件：

scode.zip (2.97 KB, 下载次数: 3) 程序运算过程中对于某些模板可能会输出"Difficult to test the rule ****", 这个表示这些模板过于复杂，这个程序分析不了，如果对于这些模板，最后程序输出fail to check rule ****,那么表示这些模板需要继续手工确认。但是如果某个模板程序没有输出"Difficult to test the rule ***",但是输出了"fail to check rule ****",那么表示模型不成立。而那些会显示"Difficult to test the rule ****"的是那些它的一部分会同某些规则匹配的情况，比如上面的 +1*9+E*5+E*4+E*1，其中部分1*9+E*4+E*1会同规则O*9+E*4+E*1匹配，对于这些模板，要计算机分析会比较复杂，所以很可能失败。而对于上面计算机不能验算的部分，可以手工验算不过现在感觉奇怪的是为什么还有几个规则计算机显示difficult to test,但是通过了。原因还没有细想: Difficult to test the rule:+E*20+E*17+E*12+O*9+O*4+O*1 Difficult to test the rule:+E*20+E*17+E*12+O*9+E*4+E*1 Difficult to test the rule:+1*25+E*20+E*17+E*12+O*9+O*4+E*1 Difficult to test the rule:+1*25+E*20+E*17+E*12+O*9+E*4+O*1 不过如果将这几个也手工检测一下就更加安全了。而所有手工检测过程中需要使用规则计算这个对象的胜负情况，然后产生它的所有可以直接到达的状态，也用规则计算胜负情况。如果结果匹配，就通过。

medie2005 · 发表于 2008-9-25 16:08:24

mathe不怕脱发？

mathe · 发表于 2008-9-25 16:09:36

比如我们先手工检测 +1*9+E*5+E*4+E*1 其中E*5中5的数目是0的情况被规则O*9+E*(4+1)覆盖，由于这部分已经被计算机检测通过，我们不需要在考虑，所以只要考虑5的数目不小于2的情况。对于这种情况，没有任何模板可以匹配，所以我们直接计算g值得到为s[9]=4!=0,也就是这个应该是先手胜的局面；所以只要找出一种先手败的直接到达局面就可以了。我们考虑将一个5拆分的局面，可以变成如： 1*9+O*5+O*4+E*1 1*9+O*5+E*4+3+E*1 .... 1*9+O*5+E*4+2*2+E*1 ... 其中1*9+O*5+E*4+2*2+E*1不能同任何规则匹配，而且其g值为s[9]^s[5]=0,所以是先手败的局面。也就是+1*9+E*5+E*4+E*1在5的数目不小于的情况检验通过。

mathe · 发表于 2008-9-25 16:13:18

同样对于局面+1*12+E*5+E*4+E*1，我们需要检测5的数目不小于2的情况。也需要证明其先手胜。由于这个局面可以到达+1*12+O*5+E*4+2*2+E*1，这个是先手败的局面，所以证明通过。同样对于局面+1*9+E*5+O*4+O*1，我们需要检测5的数目不小于2的情况。也需要证明其先手胜。由于这个局面可以到达+1*12+O*5+O*4+2*2+O*1，这个是先手败的局面，所以证明通过。同样对于局面+1*12+E*5+O*4+O*1，由于可以到达+1*12+E*5+O*4+2*2+O*1先手败局面，也通过证明

账号		自动登录	找回密码
密码			欢迎注册

[转载] 一维反Nim游戏