咳咳..先说一段废话..
最近开始看SICP这本书，正看到了换零钱的部分。看到里面那么多简明生动的例子，还有作者的细心讲解，真是唤起了对学习的无限激情。之前也看过王垠的一些文章，提到了诸如Lisp、scheme等语言，不过当时对此是零概念（其实现在对scheme的了解，也止于SICP换零钱这部分章节）。在了解了mit-scheme的一些基本用法后，虽然也觉得用‘括号’这种语法的确很优雅，但当我真的写完一个长长的定义之后，游荡在许许多多括号中间，找个小bug，真心觉得头疼。
换零钱
回到正题，先说一下题目：
给了50、25、10、5、1美分的硬币，将1美元（100美分）换成零钱，总共有多少种换法？
在这之前，书中也提到了一般有两种方法，线性递归和线性迭代，书中给出的解法是一个最为直观的，效率也最低的解法——线性递归。
递归法
书中的思路这样描述：
将总数为a的现金换成n种硬币的不同方式的数目等于
- 将现金数a换成除第一种硬币之外的所有其他硬币的不同方式数目，加上
- 将现金数a-d换成所有种类的硬币的不同方式数目，其中的d是第一种硬币的币值
按照这种规则，则可以总结出如下算法：
- 如果a就是0，应该算作是有1种换零钱的方式。
- 如果a小于0，应该算作是有0种换零钱的方式。
- 如果n是0，应该算作是有0种换零钱的方式。
n应该代表的是，第几种硬币（有1、2、3、4、5这五种币种，0就是没有可分配的币种）。
这个递归过程的代码为：
(define (first-denomination kinds-of-coin)
(cond ((= kinds-of-coin 1) 1)
((= kinds-of-coin 2) 5)
((= kinds-of-coin 3) 10)
((= kinds-of-coin 4) 25)
((= kinds-of-coin 5) 50)))
(define (cc amount kinds-of-coin)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coin 0)) 0)
(else (+ (cc amount
(- kinds-of-coin 1))
(cc (- amount
(first-denomination kinds-of-coin))
kinds-of-coin)))))
(define (count-change amount)
(cc amount 5))
所以测试了一下，结果为：
1 ]=> (count-change 100)
;Value: 292
这个递归运算是指数级的，现在看起来没什么问题，但是当总钱数比较大时，问题就明显了。
迭代法
又是一段废话...
作者说，这一解法留给读者作为一个挑战。看到'挑战'这个字眼，凭着对求知的好胜心，我的心就痒痒了，然后接下来就是自虐的过程。虽然出身于数学系，但是大学期间，基本都把青春献给dota了。
面对这个一层套一层的问题，脑袋已经不够用了，想了许多种思路，几乎都是半途发现行不通又重新思考。在想了几个小时后，终于忍不住去网上搜索答案，英文不好，只能搜搜中文的。发现有个答案，大概看了一下，说是用数组先把一部分结果算出来，然后复用。因为我的scheme水平实在有限，没接触到那些用法，所以也没细看，而且我觉得这个解法，也不符合我想要的那种答案。
只好回来继续虐自己吧，光空想，脑袋是转不过来了。突然想起，书中一般都是通过画一些推导图之类的，来寻求规律，于是我也拿起笔画起来，终于找到了一种思路。
思路
递归法是通过把每一个大问题划分成两个小问题，从而生一个树形解法，思路虽然比较好理解，但是运算时就要把树全部展开，而且子树当中存在大量重复计算，效率可想而知。而迭代法不能延续这种思路，只能通过自身的参数，来分析当前迭代的情况，并计算出来，进行下一次迭代。所以我的想法是，可不可以每次迭代通过每种币种的数量，计算出剩余的钱，然后分析出当前情况是否是一个有效的分法，然后进行下一次迭代，直至每种币种的所有数量情况遍历完毕。
怎么判断，什么是一个有效的分法呢？就是每种硬币，它的币值乘以它的数量，最后相加在一起，正好等于总钱数时，即剩余钱数是0时，就是一种有效的分法。
设有如下对应关系：
| 币种 | 币值 | 数量 |
|---|---|---|
| 1 | 50 | c1 |
| 2 | 25 | c2 |
| 3 | 10 | c3 |
| 4 | 5 | c4 |
| 5 | 1 | c5 |
总钱数为amount;
那么，当amount = coin1*c1+coin2*c2+coin3*c3+coin4*c4+coin5*c5;时，
就是一种有效的分法。
有几个问题需要考虑：
- 按照怎么样顺序去遍历各币种的数量，直至当剩余钱数符合一种特殊情况（小于0或者等于0）。
- 当剩余钱数等于或者小于0的时候，怎样安排下一次顺序。
- 怎么判断结束情况。
分钱这种事，大概一想也知道，如果你有100块，分别可分成2张50块的，4张25块的，10张10块的，20张5块的，100张1块的。币值越大，可分的数量就越少，如果给定有一张是50块的，那令外50又可分成，2张25块的，5张10块的等等...
按这个规律，我们又发现，全分成50的，有2张；50、25混着分，有3张；全分成25的，有4张。这样就是说，币种平均值越小，可分的张数就越多。
那我们就先从平均值最大的币种开始遍历（没试过从平均值最小的遍历），迭代就是只要剩余钱数大于0，就让数量增加，每当遇到特殊情况，也就是剩余钱数小于0或者等于0时，就开始遍历平均值第二大的，这样可分的张数就越来越多。直到只剩下平均值最小的币种了，那么就结束了。
方法
先从币值最大的币种（第一种币种）开始遍历，每次数量加1，计算出剩余钱数，直到剩余钱数等于0或者小于0时，就将此次的最大币种的数量减1，并将币值第二大的币种（第二种币种）数量加1；接下来每次第一种的数量保持不变，将第二种的数量加1，再次直到剩余钱数等于或者小于0，然后将第二种数量减1，第三种数量加1，此时重复之前的步骤，直至到最后一个币种。可以发现，我们需要有个标识记录，当前是哪种硬币的数量应该加1。总结后，遍历情况如下图：
图1.jpg
思考：
到了图中最后一步时，游标已经走到了最后一个币种，但此时遍历还远没有结束。接下来就是需要找到比现在的币种平均值要小的搭配了。一开始，我直接把第一个币种的数量减1，并且后面的币种数量清0，进而开始迭代，结果发现，漏掉了许多情况。漏掉的情况就是当第一个币种数量不变（即上图中数量为1）时，除第一种币种之外，剩余其他币种的随意搭配。所以，只能从后往前，开始减少币种的数量，这样就不会漏掉情况了。
接下来继续，目前游标已经是第五种硬币了，所以要将前面离的最近的且数量不为0的币种数量减1，将下一币种数量加1（将游标移动到此币种），再将这之后的币种硬币数清零，然后继续用之前的方法迭代。
接着图1继续迭代，如下图：
图2.jpg
最后一个问题，怎么判断结束呢？
由于是一步一步减少币值较大的币种的数量，所以最后会看见这样一幅画面：
图3.jpg
很明显，当前四种硬币的数量为0时，第5种硬币数量为100，这就是最后一种有效的分法，可以结束了。
代码
方法已经有了，接下来就是还原成代码吧。由于对scheme不熟，如果直接用scheme，估计我就崩溃了。为了快速验证我的想法，我首先用C语言实现了一下（我用的是Xcode），代码如下：
// 获取对应币种的币值
int get_coin(int index){
switch (index) {
case 1:{
return 50;
break;
}
case 2:{
return 25;
break;
}
case 3:{
return 10;
break;
}
case 4:{
return 5;
break;
}
case 5:{
return 1;
break;
}
default:
break;
}
return 0;
}
// 为了计算执行了多少次迭代
static long long cn2 = 0;
// 剩余钱数 有效分法 游标
static int c_c(int leftAmount, int count, int cur, int c1, int c2, int c3, int c4, int c5){
cn2++;
// 当剩余钱数等于或者小于0时
if (leftAmount == 0 || leftAmount < 0){
// 1.当游标走到4时，其实是从前往后遍历的时候
// 2.当游标在5时，但是第4种硬币的数量大于0，属于从后往前遍历
// 这两种情况处理是一样的，之后的判断与处理跟此处类似
// 这里还有一个稍微特殊一点的地方：
// 当属于第2种情况时，由于第5种硬币已经是最后一种硬币，所以直接加1，且之后并没有需要数量清零的币种
if ((cur==5 && c4>0) ||
cur==4){
return c_c(leftAmount+get_coin(4)-get_coin(5),
(leftAmount<0)?count:count + 1,// 如果剩余钱数等于0，有效次数加1，反之不变
5,
c1,
c2,
c3,
c4-1,
c5+1);
}
else if ((cur==5 && c4==0 && c3>0) ||
cur==3){
return c_c(leftAmount+get_coin(3)-get_coin(4)+get_coin(5)*c5,
(leftAmount<0)?count:count + 1,
4,
c1,
c2,
c3-1,
c4+1,
0);
}
else if ((cur==5 && c4==0 && c3==0 && c2>0) ||
cur==2){
return c_c(leftAmount+get_coin(2)-get_coin(3)+get_coin(4)*c4+get_coin(5)*c5,
(leftAmount<0)?count:count + 1,
3,
c1,
c2-1,
c3+1,
0,
0);
}
else if ((cur==5 && c4==0 && c3==0 && c2==0 && c1>0) ||
cur==1){
return c_c(leftAmount+get_coin(1)-get_coin(2)+get_coin(3)*c3+get_coin(4)*c4+get_coin(5)*c5,
(leftAmount<0)?count:count + 1,
2,
c1-1,
c2+1,
0,
0,
0);
}
// 结束情况： (cur==5 && c4==0 && c3==0 && c2==0 && c1==0)
else{
// 如果剩余钱数等于0，有效次数加1，并返回
return (leftAmount<0)?count:count+1;
}
}
// 剩余钱数大于0
else{
// 继续将游标处的币种数量加1
return c_c(leftAmount-get_coin(cur),
count,
cur,
(cur==1)?c1+1:c1,
(cur==2)?c2+1:c2,
(cur==3)?c3+1:c3,
(cur==4)?c4+1:c4,
(cur==5)?c5+1:c5);
}
}
int getCountChange(int amount){
cn2 = 0;
// 将第一种搭配当参数传入
int count = c_c(amount-get_coin(1),0,1,1,0,0,0,0);
printf("执行了%lld次",cn2);
return count;
}
然后进行测试
printf("count: %d",getCountChange(100));
控制台打印：
->] 执行了1554次
->] count: 292
其实我也把递归法实现了，有对比才好说话，递归法 (getCountChange2) 的测试如下：
printf("count: %d",getCountChange2(100));
控制台打印：
->] 执行了15499次
->] count: 292
看来差距还不是非常的大（10倍），那增加到500试试...
printf("迭代法count: %d",getCountChange3(500));
printf("递归法count: %d",getCountChange2(500));
控制台打印：
->] 迭代法执行了346730次
->] 迭代法count: 59576
->] 递归法执行了12822611次
->] 递归法count: 59576
恩，看来差距还是有的。
细心的朋友可能发现了，这个迭代法用的是getCountChange3，这个并不是bug。其实当我用getCountChange方法时，总钱数到200多的时候，Xcode就阻止继续运行了，此时是迭代了3万次左右，这个原因我不太懂，可能是会检查函数的最大循环调用次数。所以我写了个getCountChange3方法，方法里面用一个循环代替了函数递归，其他方式都不变，以此模拟函数迭代法。
看来没什么问题了，可以用scheme测试了。代码如下：
(define (get-coin index)
(cond ((= index 1) 50)
((= index 2) 25)
((= index 3) 10)
((= index 4) 5)
((= index 5) 1)))
(define (c-c leftAmount count cursor c1 c2 c3 c4 c5)
(cond ((or (= leftAmount 0) (< leftAmount 0)) ; 当剩余的钱小于或等于0的时候
(cond ((or (= cursor 4)
(and (= cursor 5) (> c4 0))) ;如果cursor=4，或者 cursor=5且c4>0
(c-c (- (+ leftAmount
(get-coin 4))
(get-coin 5)) ;leftAmount将第4种硬币钱数加回来一个，且c4减1，紧接着加上第5种硬币钱数，且c5加1
(if (< leftAmount 0)
count
(+ count 1)) ;如果leftAmount=0，说明正好分完一次，所以count加1；反之，count不变
5 ;将游标指向第五种硬币
c1
c2
c3
(- c4 1) ;c4减1
(+ c5 1))) ;c5加1，不清零是因为c5是最后一种硬币，无需从零开始计算
((or (= cursor 3)
(and (= cursor 5) (= c4 0) (> c3 0)))
(c-c (- (+ leftAmount
(get-coin 3)
(* c5 (get-coin 5)));此时c5需要清零，所以把第五种硬币的钱数都加回来
(get-coin 4))
(if (< leftAmount 0)
count
(+ count 1))
4
c1
c2
(- c3 1)
(+ c4 1)
0))
((or (= cursor 2)
(and (= cursor 5) (= c4 0) (= c3 0) (> c2 0)))
(c-c (- (+ leftAmount
(get-coin 2)
(* c4 (get-coin 4))
(* c5 (get-coin 5)))
(get-coin 3))
(if (< leftAmount 0)
count
(+ count 1))
3
c1
(- c2 1)
(+ c3 1)
0 ;清零原理同上
0))
((or (= cursor 1)
(and (= cursor 5) (= c4 0) (= c3 0) (= c2 0) (> c1 0)))
(c-c (- (+ leftAmount
(get-coin 1)
(* c3 (get-coin 3))
(* c4 (get-coin 4))
(* c5 (get-coin 5)))
(get-coin 2))
(if (< leftAmount 0)
count
(+ count 1))
2
(- c1 1)
(+ c2 1)
0
0
0))
(else (if (< leftAmount 0); 此时c4=0,c3=0,c2=0,c1=0,所以全部遍历完毕，结束。
count
(+ count 1)))))
(else (c-c (- leftAmount
(get-coin cursor));此时如果leftAmount>0,继续将游标指向的硬币数量加1
count
cursor
(if (= cursor 1)
(+ c1 1)
c1)
(if (= cursor 2)
(+ c2 1)
c2)
(if (= cursor 3)
(+ c3 1)
c3)
(if (= cursor 4)
(+ c4 1)
c4)
(if (= cursor 5)
(+ c5 1)
c5)))))
(define (count-change2 amount)
(c-c (- amount
(get-coin 1))
0
1
1
0
0
0
0))
进行测试
1]=> (count-change2 100)
;Value: 292
为了与递归法对比，我分别执行了钱数为1000的情况，迭代法也是过了20秒左右才出结果（801451种），但是递归法至今还没有算出来（也许是我等的时间太短了？）...
优化
仔细研究研究这个算法，还是有优化的余地的，比如当游标处的币种数量减1时，下一币种数量不是加1，而是直接加上当前剩余钱数（因为剩余钱数有可能小于0）与此游标处币种的币值与需要清零的所有币值的和，然后再除以游标下一币种的币值最后得到的商，这样可以减少迭代次数。而且按照这个思路，第一次传入参数的时候，也直接把第一种硬币的数量设置为总钱数与第一种币值的商，也减少了一些迭代次数（总钱数越大，减少的也越多，不过这个第一次的计算在计算机面前可以忽略的，只是为了追求完美）。
这个方法我试了，对于1000这个总钱数，从递归法的333082021次调用，到上述迭代法的4732860次调用，最后到这个优化迭代法的801871调用（总换法是801451，个人觉得对于这种遍历的算法，真是优化到了极致😄），每一次都是一个数量级的提升。具体优化后的代码就不贴了，看了太多代码也会烦吧。
总结
虽然最后代码看起来很长，但思路还算清晰，由于自认为挑战成功吧，还是有点小高兴的，也算是给了自己一个比较满意的答案。
学习的过程比较漫长，情绪也是跌宕起伏，但我相信结果是美的，继续往下学吧😄...
文章在Github上同步更新
网友评论