Python挑战100题（27~30）

27、分拆素数和

题目：把一个偶数拆成两个不同素数的和，有几种拆法呢？
现在来考虑考虑这个问题，给你一个不超过10000的正的偶数n，
计算将该数拆成两个不同的素数之和的方法数，并输出。
如n=10，可以拆成3+7，只有这一种方法，因此输出1.
参考答案：

def isPrime(n):
    if n<=1:
        return False
    for i in range(2,n):
        if n % i == 0:
            return False
    return True
n = int(input('输入偶数n:'))

count = 0
for i in range(3,n):
    if isPrime(i) and isPrime(n-i):
        count += 1
print(count//2)

28、斐波那契数列

题目：斐波那契数列为1,1,2,3,5,8...。数列从第三项起满足，该项的数是其前面两个数之和。现在给你一个正整数n（n < 10000), 请你求出第n个斐波那契数取模20132013的值（斐波那契数列的编号从1开始）。
例如：
n=1, 则输出：1
n=4, 则输出：3
参考答案：

def fib(n):
   x,y = 0,1
   while (n):
       x,y,n = y,x+y,n-1
   return x
print(fib(n)%20132013)

29、超级楼梯

题目：有一楼梯共n级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第n级，共有多少种走法？
参考答案：

#找规律，发现随着n增加符合feib序列
def feib(n):
    if n==1 or n==2:
        return 1
    elif n>2:
        return feib(n-1)+feib(n-2)
    else:
        return 0
print(feib(11))

30、砝码问题

题目：有一组砝码，重量互不相等，分别为m1、m2、m3……mn；它们可取的最大数量分别为x1、x2、x3……xn。
现要用这些砝码去称物体的重量,问能称出多少种不同的重量。
现在给你两个正整数列表w和n， 列表w中的第i个元素w[i]表示第i个砝码的重量，列表n的第i个元素n[i]表示砝码i的最大数量。i从0开始，请你输出不同重量的种数。
如：w=[1,2], n=[2,1], 则输出5（分析：共有五种重量：0,1,2,3,4）
提示：enumerate()函数的用法：函数用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。

>>>seq = ['one', 'two', 'three']
>>> for i, element in enumerate(seq):
...     print i, element
... 
0 one
1 two
2 three

参考答案（很难想到）：

w=[1,2,4]
n=[2,1,5]
s=[0,]
a=[0,]
for i,ele in enumerate(n):
    for j in range(ele+1):
        a.append(j*w[i])
    s=[x+y for x in s for y in a]
    a=[0]
print(len(set(s)))

更清楚一些的：

from functools import reduce
#此处以w=[1,2,4],n=[4,2,1]为例解释
L = []
for i in range(len(w)):
    L.append([])
    for j in range(n[i]+1):
        L[i].append(w[i]*j)
#此处L==[[0,1,2,3,4],[0,2,4],[0,4]]，表示每种砝码能提供的重量
#后面就简单了，每种砝码提供一个重量，消除重复的，但是一一列出有这么多可能性：len(L[0]) * len(L[1]) *……* len(L[n]),而且想不到要怎样表达
def x(a,b):
    X = []
    for i in a:
        for j in b:
            c = i + j
            if c not in X:
                X.append(c)
    return X
#这里就把前两种的可能性列出来，看作新的，再用reduce大法搞定 
L = reduce(x,L)
print (len(L))