应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第三十一题: 换零钱
111/2返回列表12下一页
查看: 1588  |  回复: 10
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 2 个 程序强帖 ，点击这里进行查看

holmescn

金虫 (正式写手)

[交流] Euler 工程 第三十一题: 换零钱 已有4人参与

话说英国的钱有两种, 一种是英镑(￡), 一种是便士(p). 一共有8种硬币:

1p, 2p, 5p, 10p, 20p, 50p, ￡1 (100p), ￡2 (200p).

2 英镑可以换成这样:

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

那么2英镑一共可以有多少种换零钱的方法呢?

[ Last edited by holmescn on 2011-6-26 at 00:07 ]
回复此楼

» 猜你喜欢
1楼 2011-06-19 09:11:53
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
dubo(金币+1): 欢迎常来程序语言版讨论 2011-06-19 15:27:41
微尘、梦想(金币+4): 话说我也喜欢这样干，哈哈…… 2011-06-19 17:26:47
余泽成(程序强帖+1): 鼓励交流！ 2011-06-26 00:14:44
matlab穷举
CODE:
function result = euler31()
tic;
result = 7; % only use 200,100,50,20,10,5,2 respectively, 7 methods
for i=1:-1:0 % 1
    for j=3:-1:0 % 50p
        for k=9:-1:0 % 20p
            for x=19:-1:0 % 10p
                for y=39:-1:0 % 5p
                    for z=99:-1:0 % 2p
                        if 2*z+5*y+10*x+20*k+50*j+100*i<=200 % 1p, 0 or more
                            result = result+1;
                        end
                    end
                end
            end
        end
    end
end
toc;
end

结果
CODE:
%% How many different ways can 2 be made using any number of coins?
% 1p, 2p, 5p, 10p, 20p, 50p, 1 (100p) and 2 (200p).
% Elapsed time is 0.100646 seconds.
% ans =
%        73682
赞一下(4人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
2楼2011-06-19 13:54:25
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
引用回帖:
Originally posted by libralibra at 2011-06-19 13:54:25:
matlab穷举
[code]function result = euler31()
tic;
result = 7; % only use 200,100,50,20,10,5,2 respectively, 7 methods
for i=1:-1:0 % 1
    for j=3:-1:0 % 50p
        for k=9:-1:0 % 20p
     ...

你牛!

还有, 怎么是小于等于200啊, 应该是等于200吧.

[ Last edited by holmescn on 2011-6-19 at 17:05 ]
赞一下 回复此楼
3楼2011-06-19 17:03:30
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
呃，看了半天也没弄清楚怎么换算的，以后不能去英国玩啊~都是硬币，那得多坠啊~

嗯，还要外带Orz一番~拜服二楼~

[ Last edited by huycwork on 2011-6-19 at 17:45 ]
赞一下(1人) 回复此楼
漩涡的中心有一块空地，空空的。
4楼2011-06-19 17:43:47
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★
小木虫(金币+0.5):给个红包，谢谢回帖
引用回帖:
Originally posted by holmescn at 2011-06-19 17:03:30:
你牛!

还有, 怎么是小于等于200啊, 应该是等于200吧.

[ Last edited by holmescn on 2011-6-19 at 17:05 ]

=,=要认真看注释啊...
赞一下(1人) 回复此楼
5楼2011-06-19 17:59:21
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
微尘、梦想(金币+1): 鼓励交流！ 2011-06-20 19:28:55
引用回帖:
Originally posted by holmescn at 2011-06-19 17:03:30:
你牛!

还有, 怎么是小于等于200啊, 应该是等于200吧.

[ Last edited by holmescn on 2011-6-19 at 17:05 ]

2*z+5*y+10*x+20*k+50*j+100*i这个计算出来是1p的个数,可以少一个变量
如果小于200,等于几,因为是1,就不用除了,就是几个1p.如果恰好==200,
说明这种办法不需要1p
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
6楼2011-06-19 18:02:07
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★ ★ ★
余泽成(金币+3, 程序强帖+1): 鼓励交流！ 2011-06-26 00:15:09
python 版 递归穷举法
CODE:
pence = [1, 2, 5, 10, 20, 50, 100]

results = []

def euler31(TwoPound, index):
    if sum(TwoPound) == 200:
        results.append(TwoPound)
        return

    while index < len(pence):
        if sum(TwoPound) + pence[index] > 200:
            return
        else:
            euler31(TwoPound + [pence[index]], index)
        index += 1

if __name__ == "__main__":
    euler31([], 0)
    print len(results)

算法用时16.5秒，不过我的结果怎么是73681啊。少一个。
赞一下(1人) 回复此楼
7楼2011-06-25 15:16:51
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★
jjdg(金币+1): 感谢参与 2011-06-26 00:40:01
引用回帖:
Originally posted by holmescn at 2011-06-25 15:16:51:
python 版 递归穷举法
[code]
pence = [1, 2, 5, 10, 20, 50, 100]

results = []

def euler31(TwoPound, index):
    if sum(TwoPound) == 200:
        results.append(TwoPound)
        return

...

你pence少一个数,200啊

pence = [1, 2, 5, 10, 20, 50, 100, 200]
赞一下(1人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
8楼2011-06-25 15:45:26
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

holmescn

金虫 (正式写手)
★
jjdg(金币+1): 感谢参与 2011-06-26 00:39:54
引用回帖:
Originally posted by libralibra at 2011-06-25 15:45:26:
你pence少一个数,200啊

pence = [1, 2, 5, 10, 20, 50, 100, 200]

喔，少了这一个啊。那就不是换零钱了啊。哪儿有用2英镑换2英镑的。
赞一下(1人) 回复此楼
9楼2011-06-25 21:36:22
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+1): 感谢参与 2011-06-26 00:39:43
引用回帖:
Originally posted by holmescn at 2011-06-25 21:36:22:
喔，少了这一个啊。那就不是换零钱了啊。哪儿有用2英镑换2英镑的。

原题没说换,哈哈,说的是How many different ways can £2 be made using any number of coins?所以,2镑+\sigma(其余*0)也算个组成方法吧
赞一下(2人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
10楼2011-06-25 23:48:52
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
111/2返回列表12下一页
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
信息提示
关闭
请填处理意见
关闭