PythonTip 里未攻克的题目,如取石子游戏,如今积累工作经验之后从新挑战,成功了。把过程记录分享下。

描述:

有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法, 一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。 现在给出初始的两堆石子的数目a和b,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。 如果你是胜者,输出Win,否则输出Loose。 例如,a=3,b=1, 则输出Win(你先在a中取一个,此时a=2,b=1,此时无论对方怎么取,你都能将所有石子都拿走).

分析(动态规划):

我的思路是转变成图形化表示,二维表中点(x,y)用W表示会赢,L表示为输。

(x,y)的结果显然决定与前面已填好的(m,n) , 其中m,n 分别小于 x,y 。 所以可以用动态规划。 根据之前失败坐标的集合推算本行的失败坐标。

并且每行至多有一个失败坐标。所以能保证动态规划的时间复杂度不会很高。

当我从(0,0)开始,填到(a,b)时就知道结果了。

明显(x,y)和(y,x)结果一样,因此我刚开始只填半个表,导致结果不准,看了其他人的奇异坐标才明白到自己的错误。从新填好。

错误填表分析过程

错误填表图1

错误填表图2

错误填表图3

我根据这个过程写出版本一代码。

正确填表分析过程

正确填表图1

正确填表图2

正确填表图3

我本来猜测需要推到前面代码从来。幸运的是,运行正常的版本二的代码只在版本一加一行就可以了。

下面是我的算法代码,比较简洁。动态规划确实强大,另外还有分治法也强。

Python代码:

################################################################################
# print "T: 二维坐标表示法, 每行至多有一个失败坐标。二维表只填半边导致失误,改正" 
################################################################################
if a < b: a,b = b,a

m = [(0,0)]  # 失败的坐标纪录池
for i in range(1,a+1):
    for j in range(i+1):
        # if i == j or j == 0: # win
        #     continue

        for x in m:
            if (i-x[0]) == (j-x[1]) or i == x[0] or j == x[1]: # win
                break
        else:  # else 是for的部分,break for的时候也break了else
            m.append((i,j)) # 版本一:二维表只填半边,所以只有这行代码
            m.append((j,i)) # 版本二:二维表两边都填,多加这一行就OK了
        #print i,j,m

print "Loose" if (a,b) in m else "Win"


原文出自发表的https://blog.pythonwood.com/2017/12/威佐夫博弈:取石子游戏算法——挑战PythonTip/



扩展阅读