一知半解讲Python第二季:7.钞票兑换

一道让我怀疑人生的题

CCF NOI1034 钞票兑换。

时间限制: 1000 ms 空间限制: 262144 KB

题目描述

将任意给定的整百元钞票,兑换成10元、20元、50元小钞票形式。输出兑换方案总数。

输入

输入需要兑换的钞票总数n。

输出

输出方案总数。

样例输入

100

样例输出

10

数据范围限制

100

看到这题我第一反应就是穷举了,于是稍加思考,一个三层循环的代码就出现了,提交吧。结果如下:

点开数据一看:5410000这个测试超时。

先看看代码吧

#coding:cp936

print('''将任意给定的整百元钞票,

兑换成10元、20元、50元小钞票形式。输出兑换方案总数。''')

n=int(input("请输入100的整数倍的钱数:"))

sum=0

for i in range(0,n//10+1,1):

for j in range(0,n//20+1,1):

for k in range(0,n//50+1,1):

if i*10+j*20+50*k==n:

sum=sum+1

print("共有",sum,"种方案。")

input()

(ps:oj.noi.cn不支持Python,这是我转写的,注意 n//10这里必须用//,表示整除,/计算结果为float类型,而循环终止值要求必须整型)

好吧,知道了超时,就想到了循环次数可能多了,那就减吧。

别告诉我你写的话n//10、n//20、n//50都写成n了。那就和我一样了。上面的代码思路是我第一次减次数时想到的。但不行开始写这篇文章时我测试的这个数据,现在都跑了10多分钟了还没出结果。想象一下它会执行多少次循环吧。5410000/10*5410000/20*5410000/50=15834042100000000

1万5834万零421亿次

吓人不,按这需求我这台2.93Ghz计算机大约要计算多久?

ps:参考网上算法2.93Ghz大致就是相当于每秒计算29.3亿次,不知是否准确,仅供参考。

算到这把我都吓到了,赶紧结束那个还在跑的程序。

后来,想到了,10元和20元知道了,50元的自然就知道了,并且,10元的数量确定了20的最大数量也就确定了,所以做了如下修改,少了一重循环,并且二重循环的循环次数也减少了。

for i in range(0,n//10+1,1):

for j in range(0,(n-10*i)//20+1,1):

if (n-i*10-j*20)%50==0:

sum=sum+1

但是,还不行,再想。根据上面的思路,其实是知道了三种面额的两个就能知道第三个的数量。那么如果从10元开始循环,循环的次数一定高于从50元的,并且是它的5倍。所以改为如下代码:

for i in range(0,n//50+1,1):

for j in range(0,(n-50*i)//20+1,1):

if (n-i*50-j*20)%10==0:

sum=sum+1

结果你也预见到了,肯定还是不行。到这里我就没辙了,思考了好久也不得其法隐隐感觉,其实这里的if是不必要的,因为余下的钱可能能被10整除,可是再怎么也想不明白了。

无奈,求助度娘吧。找了一圈,方法是找到了,可以我的智商,还是理解不够透彻,如果想给别人讲是讲不明白的,只能说是知道了这样可以,也大致明白为什么。先上代码吧:

for i in range(0,n//50+1,1):

sum=sum+(n-50*i)//20+1

用上面的数据测试,瞬间完事儿:

请输入100的整数倍的钱数:5410000

看看这种方法的作者的解释:

假定50元的钞票有i张,那么这种情况下的方案数就能算出来了。

例如 n=100

50元 有3种情况

(1)0张,则把剩余的钱(100元)换算成20元,可以有5张(即20,20,20,20,20,此为1种方案),每个20元都可以用2张10元来代替,这样5张20元,就可以有5次兑换成10元的机会,即由此产生5种兑换方案。这样,50元为0张时,兑换的方案数就是5+1;

(2)1张,则把剩余的钱(50元)换算成20元,可以有2张(即50,20,20,10,此为1种方案),每个20元都可以用2张10元来代替,这样2张20元,就可以有2次兑换成10元的机会,即由此产生5种兑换方案。这样,50元为0张时,兑换的方案数就是2+1;

(3)2张,则把剩余的钱(0元)换算成20元,可以有0张(即50,50,此为1种方案)

---------------------

来源:CSDN

版权声明:本文为博主原创文章,转载请附上博文链接!

你能看懂吗?反正我是似懂非懂,即便懂了也是那种知道但想不到的的懂。

大致说一下我的似懂非懂:

基本思路:

1、关注两个钱数:50和20,10自然就确定了。因为50是大数循环次数少,所以选50做循环基数。

2、穷举50的个数,这时50的个数的已知的,那么20和10的个数便由剩余的钱数n-50*i决定。而20的个数(n-50*i)//20*(0—n//20),当20的个数确定了,10的个数就确定了。这样就形成了一种方案。

3、在50和20都确定了一个具体的数时,即上面形成的方案情况下,即50和10的个数都确定的情况下,又可以将20的个数(n-50*i)//20又可以成2*(n-50*i)//20个10元,而这又有20的个数种方案,即(n-50*i)//20种。

4、所以一个50的个数对应的方案是(n-50*i)//20+1种,依次穷举累加即可。

解释就到这里,聪明的你一定比我想的明白,我是只能感叹自己的智商不够啦!

如果这个你能轻松的理解,那么再看看下面这个更变态的解法吧:

n=n//100

sum=5*n*n+4*n+1

没错,一个循环都没有,直接上求和公式。看看大佬的思路:

刚才本质上已经相当于数列求和,把a=0单独提出

sum=∑a=02i(INT(5i−2.5a)+1)=5i+1+∑a=12i(INT(5i−2.5a)+1)

sum=∑a=02i(INT(5i−2.5a)+1)=5i+1+∑a=12i(INT(5i−2.5a)+1)

展开,分奇偶讨论,去掉取整

=5i+1+∑a=0i(INT(5i−2.5(2a−1))+INT(5i−2.5(2a))+2)

=5i+1+∑a=0i(INT(5i−2.5(2a−1))+INT(5i−2.5(2a))+2)

=5i+1+∑a=0i(10i−10a+4)

=5i+1+∑a=0i(10i−10a+4)

sum=5i2+4i+1

sum=5i2+4i+1

简化成这样,配的上超进化这个名字

---------------------

作者:作业乃身外之物

来源:CSDN

版权声明:本文为博主原创文章,转载请附上博文链接!

我表示只能膜拜啦!

智商高、数学好真牛!

怎么样,你有没有像我一样怀疑人生?

不过,怀疑归怀疑,学习还是得继续!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181219G0DOVC00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券