一道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