Python挑战100题（31~33）

31、取石子问题

题目：有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，
一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。
现在给出初始的两堆石子的数目a和b，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。
如果你是胜者，输出Win,否则输出Loose。
例如，a=3,b=1, 则输出Win(你先在a中取一个，此时a=2，b=1,此时无论对方怎么取，你都能将所有石子都拿走).
参考答案：
威佐夫博弈
版权声明：本文为CSDN博主「ojshilu」的原创文章，遵循CC 4.0 by-sa版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/ojshilu/article/details/16812173

a=3
b=1
if a<b:
    tmp=a
    a=b
    b=tmp
k=a-b
a=(int)(k*(1+5.0**0.5)/2.0);
if a==b:
    print('Loose')
else:
    print('Win')

平衡状态（奇异局势）：

平衡状态的概念：
引入一个概念，平衡状态，又称作奇异局势。当面对这个局势时则会失败。任意非平衡态经过一次操作可以变为平衡态。每个玩家都会努力使自己抓完石子之后的局势为平衡，将这个平衡局势留给对方。因此，玩家A能够在初始为非平衡的游戏中取胜，玩家B能够在初始为平衡的游戏中取胜。

玩法三（2堆石子每次从一或两堆取一样数目的石子）：

最后一个奇异局势是(0,0)。紧接着的奇异局势有(1,2),(3,5),(4,7),(6,10)......

现在把它们看成一个奇异局势组成的序列(0,0),(1,2),(3,5),(4,7),(6,10)......

奇异局势的判定：

我们会发现这个序列的规律，设序列第k个奇异局势元素为(Ak,Bk)，k为自然数。那么，初始条件k=0时是，A0=B0=0，递推关系为下一个奇异局势的Ak是未在前面出现过的最小自然数，且Ak = Bk + k。

上面发现了奇异局势的递推公式，那么给出一个局势，如何判断其是否是奇异局势呢？

黄金分割数：

数学真奇妙，竟然发现，这个序列跟黄金分割数有关系。黄金分割数是2/(1+sqrt(5))=(sqrt(5)-1)/2，其小数约等于0.61803398875，其倒数是(1+sqrt(5))/2，约等于1.61803398875。

这个奇异局势的序列的通项公式可以表示为：

Ak = [k*(1+sqrt(5.0)/2]
Bk = Ak + k
其中k=0，1，2，...,n ，方括号表示int取整函数。

有了这个通项式子，逆向的，对于某一个局势，只需要判断其A是否是黄金分割数的某个k的倍数，然后再确认B是否等于A+k即可。

32、杨辉三角

题目：还记得中学时候学过的杨辉三角吗？具体的定义这里不再描述，你可以参考以下的图形：
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
..............
先在给你一个正整数n，请你输出杨辉三角的前n层
注意：层数从1开始计数,每层数字之间用一个空格隔开，行尾不要有空格。
如n=2,则输出：
1
1 1
参考答案：

n= 6
L = [1]
i = 1
print(1)
while i < n:
    L.append(0)
    L = [L[j]+L[j-1] for j in range(len(L))]
    i += 1
    result = ' '.join([str(x) for x in L])
    print(result)

33、砝码问题Ⅱ

题目：有一组砝码，重量互不相等，分别为m1、m2、m3……mn；每种砝码的数量有无限个。
现要用这些砝码去称物体的重量,给你一个重量n,请你判断有给定的砝码能否称出重量n。
现在给你一个正整数列表w和一个正整数n，列表w中的第i个元素w[i]表示第i种砝码的重量，
n表示要你判断的重量。如果给定砝码能称出重量n，输出Yes，否则输出No。
例如，w=[2,5,11], n=9,则输出Yes（取两个2，一个5）。
参考答案：

''' 利用减法求解，通俗易懂，耗时短'''
w=[2,5,11]
n=9
flag = False

while n:
    n = min([n-x for x in w if n-x >= 0])
    if n == 0:
        flag = True
        break
    elif n <min(w):
        break

if flag:
    print('Yes')
else:
    print('No')