import sys
d = {(1,) : False, (2,) : True}
def check(new):
new.sort()
nnode = tuple(new)
if not d.has_key(nnode):
gen(nnode)
return not d[nnode]
def gen(node):
v = 0
for i in range(len(node)):
if node[i] <= v:
continue
v = node[i]
base = list(node)
del base[i]
if v 1:
if check(base + [v - 1]):
d[node] = True
return
if v > 2:
if check(base + [v - 2]):
d[node] = True
return
for j in range(1, (node[i] + 1) / 2):
if check(base + [j, v - 1 - j]):
d[node] = True
return
for j in range(1, node[i] / 2):
if check(base + [j, v - 2 - j]):
d[node] = True
return
d[node] = False
test = int(sys.argv[1])
print 1, ":", d[(1,)]
print 2, ":", d[(2,)]
for i in range(3, test + 1):
gen((i,))
print i, ":", d[(i,)]
s = { (1,):0 }
def perm(L):
for i in range(len(L)):
for j in range((L[i]+1)/2):
yield sorted(k for k in L[:i]+[j,L[i]-j-1]+L[i+1:] if k>0)
yield sorted(k for k in L[:i]+[j,L[i]-j-2]+L[i+1:] if k>0)
def win(L):
k = tuple(L)
r = s.get(k)
if r is not None:
return r
for l in perm(L):
if not win(l):
s[k] = 1
return 1
s[k] = 0
return 0
for i in range(1, 100):
print i, win([i])
print len(s)
枚硬币排成一排，两人轮流取，每人每次可取其中一枚或者相邻的两枚。
)是今天软件实验班的招生考试试题。
是先取一枚 然后剩7枚，再然后剩4枚吗？
搞过OI的似乎很有优势
问题稍微有点笼统， 如果只管最后一个的话，硬币数为奇数，则先取币的人获胜，偶数则后取币的获胜。
首先有两个问题，你的答案针对哪一个？
其次，无论针对哪一个，你的答案都是不正确的
n=8时，最关键的是第5个，而n=4时，最关键的是第2个，所以，先取的人一定会取1，2两个，后取的人一定失败
第二个问题有O(1)或者O(n)算法么?
先说第二种情况吧，如果硬币数是3k+1，那么只要对手不出错误，先取的人肯定失败；否则，他先取一枚或者两枚，使得剩下的硬币数为3k+1，下面他只要盯着对手，保证每次他取完后剩下的硬币都可以表示成3k+1的形式，那么最后一枚硬币肯定是对手的。
第一种情况类似，只要初始硬币数不是3k的形式，那么他就可以取胜，原因不再赘述。
说实话，这是我小学时候看的题～
very good, but it is not the answer we want。
我明白你的意思，不过注意题目要求取２枚硬币时要求这两枚硬币是相邻的
就是说取一枚的时候可以跳着取，但取两枚有一个前提就是这两枚必须连在一起，换言之当没有连着的两枚硬币时就只能取一枚了，是这个意思吗？
对于1，甲方总有取胜策略：如果n是奇数，甲先取中间的一枚；如果n是偶数，甲先取中间的2枚。剩下的两部分左右对称，无论乙采用何种取子策略，甲都在对称位置取子。所以最后取完的肯定是甲方了。
这个问题不能具体问题具体分析，只能抽象思维，我比较弱
查一下“堆”的问题
从题目的描述看，最后肯定会出现将这一排硬币被分割成m个小段的情况。在此，将各段硬币的数量用逗号分开标记，各段的顺序不会影响结果，关键看各段硬币数量的组合数。
为了让自己一定能赢，必须使得对手在最后的一（对于第一种情况）两（对于第二种情况）次取币中没有选择（指只有一种取法）或者无法挽回（指有多中取法，但造成的结果一样）。
对于第一种情况——取到最后一枚硬币的赢：
那么我必须给对手造成这样的状态——1，1（最后剩下两枚，分开的）。因为只有这样，才能保证最后一枚硬币总会是自己的。这是一样从结果状态往前推的方法。为了让〈1，1〉这种状态是对手遇到而不让自己有机会遇到，这就与初始状态下的硬币数量以及过程中的取法有关系了。能造成这样状态的前一状态是〈3〉，〈1，2〉，〈1，3〉，〈1，1，1〉，〈1，1，2〉。这里说明一下〈3〉，指的是最后剩下三个，并且是连在一起的，取中间一个就造成了〈1，1〉的状态。这里每一种状态在往前推都会出现多中情况，但只有给对手造成了〈1，1〉的状态，那才是有绝对取胜的把握。
对于第二种情况——取到最后一枚硬币的输：
为了让自己一定能赢就要给对手造成〈1，1，1〉这种状态。道理和上面相似。
如果不考虑“相邻的”这一条件，那么就是魔群月光的留言中说的道理了。
第二种情况的答案和平方数有关系吗？
期待楼主给出答案和理论
当你先取的时候，记住：当n＝3x时，取2，当n＝3x＋2时取1，这样你就稳赢，当你遇到n＝3x＋1时，认输吧。
同样，当你后取时，尽量争取非n＝3x＋1的局面。（x＝0，1，2，3...）
第一个问题比较简单，cuckoo已经给出答案了。
第二个问题我也不知道怎么做
放在这里群策群力。
当n等于4，先手输.当n为5到8，都可以用cuckoo的取中间方法?
我和我同学做出来是1，4，9先手输，所以怀疑是平方数的时候先手输。
归纳法呀~~
做着做着就好像挖雷一样。到n等于9的时候有点头晕了，不过大家好像都还没有抽象出什么规律~~
me too!
如果有人能写个程序算算，看看结果，或许能发现一下规律。
程序可以写啊，就是看所有整数拆分的情形是先手赢还是输，比如考虑1是先手输，2是先手赢，1+1是先手赢，等等，比如我们要考虑9的情况，那么如果8，1+7，2+6，3+5，4+4，7，1+6，2+5，3+4都是先手胜，那么9就是先手输。再比如我们要考虑2+6的情况，如果1+6，2+5，2+1+4，2+2+3，6，2+4，2+1+3，2+2+2中有一个是先手输，那么2+6就是先手赢了。通过这种方法就可以编程解决了，不过复杂度，以及存储的方法都让我觉得很不爽，所以我不编程了，现在的结果就是1，4，9先手输，2，3，5，6，7，8先手胜。
你好强悍
如果光写程序的话，有很简单的算法。
具体思路是使用Sprague-Grundy函数。相关介绍可见1，2。计算可以在O(
)的时间内完成，程序也很好写。
但最后算出来是什么结果就不知道，也许对n没有简单的刻画。
但最后算出来是什么结果就不知道?
试下Google浏览器
前70只有1,4,9,12,20
用python写的很慢的程序, 而且**没有经过自己的review** 也没有优化, 前40算得挺快, 后面很慢
靠! 《＝
____几行
____》
不见了, "#"也不见了
如下代码是 "if v 1:" 的中间的不见的那块
________if v 《＝ 2:
____________if check(base + []):
________________d[node] = True
________________return
________if v 》 1:
我不确定你用的方法。但是我前面所说的那个算法是非常非常快的.
f(n)为游戏的Sprague-Grundy函数。f(n)为0表示先手败。
伪代码：其中^表示C++中的位异或运算。
这是个O(
)的算法。你可以用这个算法看一看。
这个似乎我搞错了。please skip it.
用Roy的方法写出的程序算得很慢啊，楼主有啥更快的法子？
TopLanguage Group也讨论过这个问题，他们还有个程序，速度一样，但比较简洁：
s = { (1,):0 } def perm(L): for i in range(len(L)): for j in range((L[i]+1)/2): yield sorted(k for k in L[:i]+[j,L[i]-j-1]+L[i+1:] if k>0) yield sorted(k for k in L[:i]+[j,L[i]-j-2]+L[i+1:] if k>0) def win(L): k = tuple(L) r = s.get(k) if r is not None: return r for l in perm(L): if not win(l): s[k] = 1 return 1 s[k] = 0 return 0 for i in range(1, 100): print i, win([i]) print len(s)不过我都没试过。
跑到大概n=78就挂掉了。进程耗掉超过1G内存后崩溃。
这个应该算SAT问题吧，没有多项式时间的解法吧？