找回密码
 欢迎注册
查看: 137783|回复: 101

[转载] 一维反Nim游戏

[复制链接]
发表于 2008-9-10 10:15:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
精华
一条线上连续地放有n个棋子, 两个人轮流拿1个或者相邻的2个棋子(拿走后两边的棋子就不相邻了)
拿最后一颗棋子者为输,对方胜。

问n为多少时先拿的输?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 10:35:11 | 显示全部楼层
这个是/thread-513-1-1.html
的一个特例

=====================================
最终答案可以参考79#84#
以及命令行判断先后手胜以及先手胜的方案的windows程序: cnext.rar (5.98 KB, 下载次数: 3)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-10 10:42:58 | 显示全部楼层
拿最后一颗棋子者为输。
反Nim游戏。

要是Nim游戏就简单了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:07:42 | 显示全部楼层
据说等价于某个特定大小的Nim游戏。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:26:23 | 显示全部楼层

步步为营

Σ先手必胜先手必输
11
22,1□1
33,1□21□1□1
41□3,1□1□2,1□1□1□14,2□2
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:29:25 | 显示全部楼层
Σ先手必胜先手必输
55,4□1,3□2,3□1□1,2□2□1,2□1□1□11□1□1□1□1
66,4□2,2□2□2,3□1□1□1,2□1□1□1□15□1,4□1□1,3□3,3□2□1,2□2□1□1
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:32:27 | 显示全部楼层
n = 7
看上表可知先手胜,因可以做成3□3或者5□1
n = 8
看上表可知先手胜,因可以做成3□3或者5□1
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:34:05 | 显示全部楼层
你改得好快嘛
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 11:36:11 | 显示全部楼层
呵呵
你来分析7以上的情况吧

定理  如果n先手必输,则n + 1, n + 2先手必赢

[ 本帖最后由 无心人 于 2008-9-10 11:37 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-10 13:32:08 | 显示全部楼层
这类问题一弄不好就NPC了,只有某些可以很简单的判别。
这个问题感觉还有可能有较简单的方法,我分析了一下初始的情况:
对一个分划 n=n1+n2+n3+...+nk, n1≥n2≥n3≥...≥nk≥1,
Count(x)表示其中等于x的ni数量。
称每个先手必败局势为"奇异的"。
1、n1=1时,所有奇异局势为:k为奇数
2、n1=2时,所有奇异局势为:k为偶数,并且Count(1)、Count(2)皆为偶数.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-28 21:50 , Processed in 0.049904 second(s), 19 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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