一字棋盘相邻数为素数的博弈棋题

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

长度为N的一字棋盘，初始全为空格，空格用0表示。另外有N张字牌，分别写有数字1,2,3，。。。，，N-1,N。现在，有两人依次任意选一张字牌放入棋盘的任意一格空格，要求，如果边上已经有字牌的话，两者相加必须为素数。如：103，当中放2是可以的，因为分别和两边的数相加都是素数。最后总有一人最先没法再操作了就算输。
举例：N=3，先者可放成：1 0 0 或：0 1 0 或：0 0 1 或：2 0 0 或：0 2 0 或：0 0 2 或：3 0 0 或：0 3 0 或：0 0 3 共9种不同的放法，可见只有 0 2 0 这一种放法是胜利放法，所以本题先者胜。
现出3题，问：先者胜还是负？如果胜的话，第一步怎样放？
题1：N=5
题2：N=7
题3：N=9

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：胜利 怎样

有意思，研究下

用matlab一步步推的。
N=5时，1必胜，共有12个必胜策略。
0     0     0     0     2
     0     0     0     0     5
     0     0     0     1     0
     0     0     0     2     0
     0     0     0     3     0
     0     0     2     0     0
     0     0     5     0     0
     0     1     0     0     0
     0     2     0     0     0
     0     3     0     0     0
     2     0     0     0     0
     5     0     0     0     0
由于lz没说“一个4，两边都是0”算不算加起来素数，那我就算他不是素数了

N=7 N=9 方法也一样 结果不列了

总体思路就是，
1，先写个函数f判断一个1*N矩阵是否可加，（可加就是可以把其中的0换成一个没在这矩阵里的数，还能满足左右加起来都素），可加则返回m*N的结果，不可加返回empty；
2，对【0 0 0 0 0】使用f，迭代，得到每一轮可能出现的所有结果S1，S2，S3，S4，S5；
3，把所有可加的S4定义为player1的胜利矩阵A，另外为player2的胜利矩阵B,（即AUB=S4）；
4，player1为了不让事情发展到被p2控制，必须阻止所有可能发展成为B的S3，那么S3中可能发展成B的成为p2的新胜利矩阵B2，其他为A2;
5，重复这个思路，最后到S1，S1共20种情况，其中12种是p1的胜利矩阵，另外8种是p2的。

本质是本办法，欢迎拍砖。

先按爪。

智力游戏挺好,可以研究

有点意思

keensword 发表于 2012-1-13 22:05
用matlab一步步推的。
N=5时，1必胜，共有12个必胜策略。
0     0     0     0     2

悲剧的是，4是可以单独放进去的的~
请看题，LZ给出的范例里，1 0 0已经允许了，同理可知在N=5时，4 0 0 0 0 也是可以的~其实LZ题目里已经提到了“有两人依次任意选一张字牌放入棋盘的任意一格空格，要求，如果边上已经有字牌的话，两者相加必须为素数”

keensword 发表于 2012-1-13 22:22
总体思路就是，
1，先写个函数f判断一个1*N矩阵是否可加，（可加就是可以把其中的0换成一个没在这矩阵里的 ...

1.感觉复杂度很高（请教该算法的复杂度，阶乘级别？）
2.思路上有漏洞，按你的思路，只考虑到在第N回合结束的情况，事实上，还有可能在小于N的某回合使得B无子可放从而A获胜。

另外，倒退过程的实现似乎有些麻烦，还要保留Si推Si+1时的信息？这样才能倒推回去？
可否把源码PM给我，或者直接把m文件发邮箱让在下拜读一番

handsome8848 发表于 2012-2-8 09:30
1.感觉复杂度很高（请教该算法的复杂度，阶乘级别？）
2.思路上有漏洞，按你的思路，只考虑到在第N回合结 ...

你意思是1不是素数？我以为楼主说是呢。我和特地加了一句判定isprime（1）为真。。。关于4这个改起来其实也就多个设定。
关于漏洞问题说的很好。应当将不可add的情况直接计入对手方的获胜矩阵。我确实只在第N步这么做了，前面漏掉了。感谢指正。