一道ACM博弈题，交互比较麻烦
第一关：巴什博弈
两人取石子，总共n个，每次拿 1 - m 个，问先手胜还是负，胜的话输出每一步策略
第二关：威佐夫博弈
两人取石子，总共两堆，可以从两堆里拿相同的数目，也可以从一堆中拿任意多个，问先手胜还是负，胜的话输出每一步策略
先上代码吧
import math
'''
for k in xrange(1,10):
a = int(k * (sq5 + 1) / 2)
b = a + k
print k,a,b
1 1 2
2 3 5
3 4 7
4 6 10
5 8 13
6 9 15
7 11 18
8 12 20
9 14 23
'''
def weizuofu(a,b):
if (a==b):
return a,2
elif a==0:
return b,1
elif b==0:
return a,0
swp = 0
if a>b:
a,b = b,a
swp = 1
sq5 = math.sqrt(5.0)
k = b - a
ak = int(k * (sq5 + 1) / 2)
bk = ak + k
print a,b,k,ak,bk
if (ak == a) and (bk == b):
return -1,-1
elif (a > ak) and (b > bk):
return b - bk,2
else:
for i in range(b):
newa = a
newb = b - i
if newa > newb:
newa,newb = newb,newa
newk = newb - newa
sa = int(newk * (sq5 + 1) / 2)
sb = sa + newk
if (sa == newa) and (sb == newb):
return i,1^swp
break
#print weizuofu(1,2)
#print weizuofu(2,2)
#print weizuofu(2,3)
#print weizuofu(4,87)
#print weizuofu(2,6)
#print weizuofu(3,10)
#print weizuofu(50,100)
#print weizuofu(74,83)
#a = 19127
#b = 20155
a = 1581
b = 397
T = 0
while 1:
T += 1
print '<',T,'>',
x,y = weizuofu(a,b)
#print x,y
if x == 100 and y == 100:
print 'WIN'
break
elif x == -1 and y == -1:
print 'GG'
break
else:
if y==1:
b -= x
if a>b:
a,b = b,a
print 'sub b'
elif y==0:
a -= x
print 'sub a'
else:
a -= x
b -= x
print 'sub a b'威佐夫博弈分析及结论：https://blog.csdn.net/qq_34374664/article/details/52814983
首先判断是不是先手必败态：k = abs（a - b），然后根据公式算ak和bk，对应相等就是必败态，否则：
如果a和b都比ak和bk要大，说明先手策略是：在两个石堆里拿相同数目min（a，b） - min（ak，bk）个
不满足，就需要从大的里枚举减掉多少个，可以让后手满足必败态
举例子：
（2，3） -> （1，2）
（3，4） -> （3，2）
（15，23） -> （15，9）
（12，19） -> （11，18）
第三关：NIM博弈
两人取石子，n堆，每堆xi个，每次可以从任意一堆拿任意多个，问先手胜负态和方案
NIM博弈：https://blog.csdn.net/u012925008/article/details/45476629
小学奥数结论：都异或起来为0，先手必败；否则，先手在某一堆中拿掉异或结果，后手进入先手必败态
最后代码：
http://bendawang.site/2018/05/28/SUCTF-2018-%E9%83%A8%E5%88%86%E9%A2%98%E8%A7%A3/n
京公网安备 11010502036488号