一知半解讲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

版权声明：本文为博主原创文章，转载请附上博文链接！

我表示只能膜拜啦！

智商高、数学好真牛！

怎么样，你有没有像我一样怀疑人生？

不过，怀疑归怀疑，学习还是得继续！