【算法】博弈论
发布时间
阅读量：
阅读量
1. 巴什博奕
只有一堆n个物品，两个人轮流从这堆物品中取物， 规定每次至少取一个，最多取m个。最后取光者得胜。
方法：
最后取光者赢：n%(m+1) == 0 ，后手胜；
最后取光者输：(n-1)%(m+1) == 0 ，后手胜；
例题：本游戏是一个二人游戏,有一堆石子一共有n个,两人轮流进行,每走一步可以取走1…m个石子,最先取光石子的一方为胜,如果游戏的双方使用的都是最优策略，请输出哪个人能赢。
#先手胜则返回true
def bashGame(n,m):
if n%(m+1) != 0:
return True
else:
return False
2. Nim博弈
有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
方法：
先拿空者胜：取所有堆的石子个数的异或，结果为0 则先手赢。
例题：
现在有一个整数数组，其元素值均为1-n范围内的某个整数，现在你和你的朋友在玩一个游戏，游戏的目的是把数组清空，你们轮流操作，你是先手，每次操作你可以删除数组中值为某个数的元素任意多个(当然数组中值为这个数的元素个数应大于等于你删除的个数,且你至少要删除一个数)。最先把数组清空的人获得胜利。假设你们都采取最优策略，请你计算你能否获得胜利。
给定一个整数数组A和元素个数n。请返回一个整数，1代表你能获胜，0代表你不能获胜。
class Clear:
def getWinner(self, A, n):
#nim博弈
#所有堆所含数的个数取异或，为0先手胜，为1后手胜
if n <= 1:
return 1
A.sort()
setA = list(set(A))
counts = []
for item in setA:
counts.append(A.count(item))
num = counts[0]
for i in range(1,len(counts)):
num ^= counts[i]
return num!=0
全部评论 (0)
还没有任何评论哟~