小练习：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，相信你能用更短的时间做出。

冬雪雪冬

from time import time
start = time()
count = 0
for p200 in range(0, 201, 200):
    for p100 in range(0, 201 - p200, 100):
        for p50 in range(0, 201 - p200 - p100, 50):
            for p20 in range(0, 201 - p200 - p100 - p50, 20):
                for p10 in range(0, 201 - p200 - p100 - -p50 - p20, 10):
                    for p5 in range(0, 201 - p200 - p100 - -p50 - p20 - p10, 5):
                        for p2 in range(0, 201 - p200 - p100 - -p50 - p20 - p10 - p5, 2):
                            if p200 + p100 + p50 + p20 + p10 + p5 + p2  <= 200:
                                count += 1
print(count)
print(time() - start)

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

sunqiangzai

##python 2.7
target = 200
coins = [ 1, 2, 5, 10, 20, 50, 100, 200 ]
total_ways = [0] * (target + 1)
total_ways[0] = 1

for i in range(0, len(coins)):
  for j in range(coins[i], target + 1):
    total_ways[j] += total_ways[j - coins[i]]

print total_ways[target]

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

huomqh

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

答案：73682,用时：0.0520 s

GhostJane

好有意思

mather

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

import time
on = time.time()
s = [0,1,2,5,10,20,50,100,200]
def f(x,y):
    if x<0 or y<=0:
        return 0
    if x==0:
        return 1
    return f(x,y-1) + f(x-s[y],y)

print(f(200,8))
print(time.time()-on)

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

import time
on = time.time()

target = 200
coins = [1, 2, 5, 10, 20, 50, 100, 200]
ways = [1] + [0]*target

for coin in coins:
    for i in range(coin, target+1):
        ways[i] += ways[i-coin]
print(ways[target])

print(time.time()-on)

结果：73682
时间：0.03

飘飞的白杨

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

答案：73682

小剑剑

import time
begin=time.time()
current=[100,50,20,10,5,2]
def recusion(num,ti):
       if num==0:
              return 1
       if ti ==6:
              return 1
       su=0
       value=current[ti]
       ti+=1
       while num>=0:
              su+=recusion(num,ti)
              num-=value
       return su
print(recusion(200,0),time.time()-begin)

答案73681
我机子上时间0.04682016

bacon6581

from time import time
start=time()

result=0

for j7 in range(0,2):
    k6=int(1 + (200-j7*200)/100)
    for j6 in range(0,k6):
        k5=int(1+ (200-j7*200-j6*100)/50)
        for j5 in range(0,k5):
            k4=int(1+ (200-j7*200-j6*100-j5*50)/20)
            for j4 in range(0,k4):
                k3=int(1+ (200-j7*200-j6*100-j5*50-j4*20)/10)
                for j3 in range(0,k3):
                    k2=int(1+ (200-j7*200-j6*100-j5*50-j4*20-j3*10)/5)
                    for j2 in range(0,k2):
                        k1=int(1+ (200-j7*200-j6*100-j5*50-j4*20-j3*10-j2*5)/2)
                        for j1 in range(0,k1):
                            result+=1
print(result)
print(time()-start)

>>> 
73682
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

from time import clock as now
time1=now()                                #开始计时
count=1                                        #已计入一个200的取法
#'''
for i in range(3):                #优先考虑大面值 
        x1=200-i*100                
        a=int(x1/50)+1                #确定下一面值的张数的上限
        for j in range(a):
                x2=x1-50*j                #以此类推
                b=int(x2/20)+1        
                for k in range(b):
                        x3=x2-20*k 
                        c=int(x3/10)+1
                        for l in range(c):
                                x4=x3-10*l
                                d=int(x4/5)+1
                                for m in range(d):
                                        x5=x4-5*m
                                        d=int(x5/2)+1
                                        for n in range(d):                                                
                                                count+=1
        print(i)                        #简陋进度条
time2=now()                                #运算结束的时刻
print('count=',count,'\n')        #输出结果
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出现的情况

import time
t,result,money = time.time(),0,[200,100,50,20,10,5,2,1]

def combi(s=200,index=0):
    global result,money
    if s >= 0:
        result += s//2+1
        for i in range(index,6):
            combi(s-money[i],i)

combi()
print(result,time.time()-t)

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

import time
t,money = time.time(),(200,100,50,20,10,5,2,1)

def combi(s=200,index=0):
    global money
    return s//2+1+sum(combi(s-money[i],i) for i in range(index,6) if s-money[i]>=0)

print(combi(),time.time()-t)

余欲渔

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

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