小练习：20160808 考察英国货币面值的组合问题

冬雪雪冬

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块，可能有些鱼油还没注意到。
什么是欧拉计划：http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了81道题，这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势，可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站：https://projecteuler.net/archives
这里已经有了500余题。

                               
登录/注册后可看大图

好了言归正传，我们开始做小练习。




题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在一周内完成，即8.15 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。

----除列出程序外，请给出输出的结果。----



题目：

在英国，货币是由英镑 ￡，便士 p 构成的。一共有八种钱币在流通：

1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p) 和 ￡2 (200p).
要构造 ￡2 可以用如下方法：

1×￡1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

允许使用任意数目的钱币，一共有多少种构造 ￡2 的方法？

题目非常简单，看看大家能不能高效的完成，我试了大约用时0.3s，相信你能用更短的时间做出。

冬雪雪冬

1. from time import time
   
2. start = time()
   
3. count = 0
   
4. for p200 in range(0, 201, 200):
   
5.     for p100 in range(0, 201 - p200, 100):
   
6.         for p50 in range(0, 201 - p200 - p100, 50):
   
7.             for p20 in range(0, 201 - p200 - p100 - p50, 20):
   
8.                 for p10 in range(0, 201 - p200 - p100 - -p50 - p20, 10):
   
9.                     for p5 in range(0, 201 - p200 - p100 - -p50 - p20 - p10, 5):
   
10.                         for p2 in range(0, 201 - p200 - p100 - -p50 - p20 - p10 - p5, 2):
    
11.                             if p200 + p100 + p50 + p20 + p10 + p5 + p2  <= 200:
    
12.                                 count += 1
    
13. print(count)
    
14. print(time() - start)
    

复制代码

思考一下，11行为什么是 <=

sunqiangzai

1. ##python 2.7
   
2. target = 200
   
3. coins = [ 1, 2, 5, 10, 20, 50, 100, 200 ]
   
4. total_ways = [0] * (target + 1)
   
5. total_ways[0] = 1
   
6. 
   
7. for i in range(0, len(coins)):
   
8.   for j in range(coins[i], target + 1):
   
9.     total_ways[j] += total_ways[j - coins[i]]
   
10. 
    
11. print total_ways[target]

复制代码

运行结果：
>>>
============== RESTART: C:/Users/Administrator/Desktop/coin.py ==============
73682

huomqh

1. import time
   
2. tt=time.time()
   
3. s=0
   
4. for i1 in range(0,200//200+1):
   
5.     for i2 in range(0,(200-i1*200)//100+1):
   
6.         for i3 in range(0,(200-i1*200-i2*100)//50+1):
   
7.             for i4 in range(0,(200-i1*200-i2*100-i3*50)//20+1):
   
8.                 for i5 in range(0,(200-i1*200-i2*100-i3*50-i4*20)//10+1):
   
9.                     for i6 in range(0,(200-i1*200-i2*100-i3*50-i4*20-i5*10)//5+1):
   
10.                         for i7 in range(0,(200-i1*200-i2*100-i3*50-i4*20-i5*10-i6*5)//2+1):
    
11.                             i8=200-i1*200-i2*100-i3*50-i4*20-i5*10-i6*5-i7*2
    
12.                             if i8>=0:
    
13.                                 s+=1
    
14. print('答案：%d,用时：%.4f s'%(s,time.time() - tt))
    

复制代码

1. 答案：73682,用时：0.0520 s

复制代码

GhostJane

好有意思

mather

思路是动态规划的思想，把整个过程分为8个阶段，即当只有1p的时候1p到200p分别只有一种凑法，然后计算既有1p又有2p的时候1p到200p各有多少种凑法，然后在计算加多个5p的时候，1p到200p各有多少种凑法。。依次类推到200p
这里可以用递归的方法，缺点是比较慢（递归都是这通病）。理解了递归的思路后，用列表从正面求比较快。
算法1（递归思路）：

1. import time
   
2. on = time.time()
   
3. s = [0,1,2,5,10,20,50,100,200]
   
4. def f(x,y):
   
5.     if x<0 or y<=0:
   
6.         return 0
   
7.     if x==0:
   
8.         return 1
   
9.     return f(x,y-1) + f(x-s[y],y)
   
10. 
    
11. print(f(200,8))
    
12. print(time.time()-on)

复制代码

结果：73682
时间：1.3372275829315186
算法2（列表正面求解）：

1. import time
   
2. on = time.time()
   
3. 
   
4. target = 200
   
5. coins = [1, 2, 5, 10, 20, 50, 100, 200]
   
6. ways = [1] + [0]*target
   
7. 
   
8. for coin in coins:
   
9.     for i in range(coin, target+1):
   
10.         ways[i] += ways[i-coin]
    
11. print(ways[target])
    
12. 
    
13. print(time.time()-on)

复制代码

结果：73682
时间：0.03

飘飞的白杨

1. l = [1, 2, 5, 10, 20, 50, 100, 200]
   
2. n = [1]*201
   
3. for i in range(1,8):
   
4.     for j in range(l[i],len(n)):
   
5.         n[j] += n[j - l[i]]
   
6. print(n[-1])
   

复制代码

答案：73682

小剑剑

1. import time
   
2. begin=time.time()
   
3. current=[100,50,20,10,5,2]
   
4. def recusion(num,ti):
   
5.        if num==0:
   
6.               return 1
   
7.        if ti ==6:
   
8.               return 1
   
9.        su=0
   
10.        value=current[ti]
    
11.        ti+=1
    
12.        while num>=0:
    
13.               su+=recusion(num,ti)
    
14.               num-=value
    
15.        return su
    
16. print(recusion(200,0),time.time()-begin)
    

复制代码

1. 答案73681
   
2. 我机子上时间0.04682016

复制代码

bacon6581

1. from time import time
   
2. start=time()
   
3. 
   
4. result=0
   
5. 
   
6. for j7 in range(0,2):
   
7.     k6=int(1 + (200-j7*200)/100)
   
8.     for j6 in range(0,k6):
   
9.         k5=int(1+ (200-j7*200-j6*100)/50)
   
10.         for j5 in range(0,k5):
    
11.             k4=int(1+ (200-j7*200-j6*100-j5*50)/20)
    
12.             for j4 in range(0,k4):
    
13.                 k3=int(1+ (200-j7*200-j6*100-j5*50-j4*20)/10)
    
14.                 for j3 in range(0,k3):
    
15.                     k2=int(1+ (200-j7*200-j6*100-j5*50-j4*20-j3*10)/5)
    
16.                     for j2 in range(0,k2):
    
17.                         k1=int(1+ (200-j7*200-j6*100-j5*50-j4*20-j3*10-j2*5)/2)
    
18.                         for j1 in range(0,k1):
    
19.                             result+=1
    
20. print(result)
    
21. print(time()-start)

复制代码

1. >>>
   
2. 73682
   
3. 0.17255878448486328

复制代码

一不小心写的程序跑的时间比斑猪的还要短，表达下思路：

A列代表货币的种类：200、100.....
B列：当大于1分的货币选定了（如：全部选"0"），那么一分的货币只有一种情况（只能选'200'，要不然就凑不够200了）
C列：当大于2分的货币全部选"0",那么两分的货币有1+200/2=101种选择（可以选0、1、2...99、100）
         1分的货币只有一种选择了，凑够200分（1个2分时，1分的只能取198个....100个2分时，1分的只能取0个）
D列：当大于5分的货币全部选"0"，5分的货币选1个，那么两分货币有1+int((200-5)/2)=98种选择（可以选0、1、....97）

所以：
200分的货币能取0个或1个
当200分的货币取0个时，100分的货币能取0、1、2；当200分的货币取1个时，100分的货币只能取0个
当200分、100分货币均取0个时，50分的货币能取0、1、2、3、4(1+int((200-200*0-100*0)/50)=5种)
当取0个200分、1个100分时，50分的货币只能取0,1,2（1+int((200-200*0-100*1)/50)=3种）
........
当取0个200分、100、50、20、10、5分的货币都取1个时，2分货币的取法有1+int((200-200*0-100*1-50*1-20*1-10*1-5*1)/2)=3种

再看代码应该清楚点了吧！

van314159

1. from time import clock as now
   
2. time1=now()                                #开始计时
   
3. count=1                                        #已计入一个200的取法
   
4. #'''
   
5. for i in range(3):                #优先考虑大面值
   
6.         x1=200-i*100               
   
7.         a=int(x1/50)+1                #确定下一面值的张数的上限
   
8.         for j in range(a):
   
9.                 x2=x1-50*j                #以此类推
   
10.                 b=int(x2/20)+1       
    
11.                 for k in range(b):
    
12.                         x3=x2-20*k
    
13.                         c=int(x3/10)+1
    
14.                         for l in range(c):
    
15.                                 x4=x3-10*l
    
16.                                 d=int(x4/5)+1
    
17.                                 for m in range(d):
    
18.                                         x5=x4-5*m
    
19.                                         d=int(x5/2)+1
    
20.                                         for n in range(d):                                               
    
21.                                                 count+=1
    
22.         print(i)                        #简陋进度条
    
23. time2=now()                                #运算结束的时刻
    
24. print('count=',count,'\n')        #输出结果
    
25. print(time2-time1)                        #输出运算时间

复制代码

khail

稳稳

小由的爸

第一种方法，迭代
import time as t
num = 1
t0 = t.time()

for a in range(0,3): # 100
    for b in range(0,int((200-100*a)/50)+1): # 50
        for c in range(0,int((200-100*a-50*b)/20)+1): # 20
            for d in range(0,int((200-100*a-50*b-20*c)/10)+1): # 10
                for e in range(0,int((200-100*a-50*b-20*c-10*d)/5)+1): # 5
                    for f in range(0,int((200-100*a-50*b-20*c-10*d-5*e)/2)+1):
                        for g in range(0,(200-100*a-50*b-20*c-10*d-5*e-2*f+1)):
                            if ((100 * a) + (50 * b) + (20 * c) + (10 * d) + (5 * e) + (2 * f) + g) == 200:
                                num += 1
                                    
print('有 %d 种组合，花费时间: %.4f' % (num,t.time() - t0))

有 73682 种组合，花费时间: 1.4991


第二种方法，递归：
moneyType = [1,2,5,10,20,50,100,200]
count = {'count':0}
def getMoneyNum(sum,flag):
    if sum < 0:
        return None
    elif sum == 0:
        count['count'] += 1
        
    for i in range(flag,len(moneyType)):
        getMoneyNum(sum-moneyType,i)
        
getMoneyNum(200,0)
print('有 %d 种组合，花费时间: %.4f' % (count['count'],t.time() - t0))

有 73682 种组合，花费时间: 4.2332

递归比迭代花费时间长，都和版主的时间相差巨大

小由的爸

import time as t

t0 = t.time()
count = {'count':0}
moneyType = [200,100,50,20,10,5,2,1]
def test(deep,left):
    if deep == 7 or left == 0:
        count['count'] += 1
    else:
        for i in range(0,int(left/moneyType[deep])+1):
            test(deep + 1,left - i * moneyType[deep])

test(0,200)
print('有 %d 种组合，花费时间: %.4f' % (count['count'],t.time() - t0))


有 73682 种组合，花费时间: 0.0320

wangzhenas

答案： 73682
核心思路是利用从大到小运用递归法，对于大于（200，100，50，20，10，5）内的元素做递归（减少递归调用次数）,每次递归时传递的元素是当前剩下的值即（200-s）以及当前元素的下标（元素从大到小排列以避免重复）， 然后在结果内加上当前剩余值若仅用（1，2）组合时的组合数，比如说当前剩余值是10，如果仅有2，1的话，一共有 10//2 + 1种组合，即有（0，1，2，3，4，5）个2出现的情况

1. import time
   
2. t,result,money = time.time(),0,[200,100,50,20,10,5,2,1]
   
3. 
   
4. def combi(s=200,index=0):
   
5.     global result,money
   
6.     if s >= 0:
   
7.         result += s//2+1
   
8.         for i in range(index,6):
   
9.             combi(s-money[i],i)
   
10. 
    
11. combi()
    
12. print(result,time.time()-t)

复制代码

当前代码还可简化为如下形式：

1. import time
   
2. t,money = time.time(),(200,100,50,20,10,5,2,1)
   
3. 
   
4. def combi(s=200,index=0):
   
5.     global money
   
6.     return s//2+1+sum(combi(s-money[i],i) for i in range(index,6) if s-money[i]>=0)
   
7. 
   
8. print(combi(),time.time()-t)

复制代码

余欲渔

mather 发表于 2016-8-8 14:40
思路是动态规划的思想，把整个过程分为8个阶段，即当只有1p的时候1p到200p分别只有一种凑法，然后计算既有1 ...

这位兄弟,你这个算法二的原理能说明一下吗,想不通为什么这样能算出来