SICP中的零钱兑换问题

声明：本文中的算法和部分程序非本人原创，仅作适当修改以供学习借鉴，代码版权归属原作者

在<<计算机程序的构造和解释>>中有一道零钱兑换问题:一美元兑换成1美分,5美分,10美分,25美分和50美分这几种零钱有多少种方法? 原书中采用树形递归给出了一种解法:

将总数为a的现金换成n种硬币的不同方式的数目等于

·将现金数a换成除第一种硬币之外的所有其他硬币的不同方式数目，加上

·将现金数a-d换成所有种类的硬币的不同方式数目，其中的d是第一种硬币的币值

要问为什么这一说法是对的，请注意这里将换零钱分成两组时所采用的方式，第一组里都没有使用第一种硬币，而第二组里都使用了第一种硬币。显然，换成零钱的全部方式的数目，就等于完全不用第一种硬币的方式的数目，加上用了第一种硬币的换零钱方式的数目。而后一个数目也就等于去掉一个第一种硬币值后，剩下的现金数的换零钱方式数目。

这样就可以将某个给定现金数的换零钱方式的问题，递归地归约为对更少现金数或者更少种类硬币的同一个问题。仔细考虑上面的归约规则，设法使你确信，如果采用下面方式处理退化情况，我们就能利用上面规则写出一个算法来：

·如果a就是0，应该算作是有1种换零钱的方式。

·如果a小于0，应该算作是有0种换零钱的方式。

·如果n是0，应该算作是有0种换零钱的方式。

以下是具体的Scheme代码：

#lang racket
(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                      (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins ))
                     kinds-of-coins)))))
  
 (define (first-denomination kinds-of-coins)
   (cond ((= kinds-of-coins 1) 1)
         ((= kinds-of-coins 2) 5)
         ((= kinds-of-coins 3) 10)
         ((= kinds-of-coins 4) 25)
         ((= kinds-of-coins 5) 50)))

对应的C++代码为

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int N = 1000;
 5 int dimes[] = {1, 5, 10, 25, 50};
 6 int arr[N+1] = {1};
 7 
 8 // 递归方式实现,更好理解
 9 int coinExchangeRecursion(int n, int m)  
10 {
11     if (n == 0)    //跳出递归的条件
12         return 1;
13     if (n < 0 || m == 0)
14         return 0;
15     // 分为两种情况：换取当前面值的情况 + 没有换取当前面值的情况    
16     return (coinExchangeRecursion(n, m-1) + coinExchangeRecursion(n-dimes[m-1], m));
17 }
18 
19 
20 int main()
21 {
22     int num=coinExchangeRecursion(N, 5);
23     cout << num << endl;
24     
25     return 0;
26 }

使用DrRacket计算(count-change 100)在1秒以内可以算出结果为292，计算(count-change 1000)需要大概1分钟才能计算出结果为801451，这是因为树形递归在递归时

中间变量随输入金额呈指数级增长。

以上问题更好的方法是迭代的方法，下面把题目改成使用我国第三套人民币的情况：1元人民币兑换成1分,2分,5分,1角,2角和5角这几种零钱有多少种方法?

解题思路是，设现金总数为amount的兑换方法有sum种（sum初始值为0），首先如果只使用1分币，显然sum=1,然后尝试使用2分币（此时币种为1分币和2分币），2分币数量每增加1个就产生一种新的兑换方法，相应的sum值也加1，当2分币总数大于amount时，要想产生新的兑换方法就必须引入5分币了，同时将2分币的数额清零（此时币种为1分币，2分币和5分币），2分币数量每增加1个就产生一种新的兑换方法，相应的sum值也加1，当2分币和5分币总数大于amount时，5分币数量加1同时2分币数值清零，继续此过程直到5分币总数大于amount时，要想产生新的兑换方法就必须引入1角币了，后面的过程同上，最后引入5角币（每引入一个更大的币种或某个大币种数量加1后各相对小的币种数量都清零），当5角币总数额大于amount时迭代结束，此时sum的值为兑换方法总数。

#lang racket
(define (count-change-true-iterative amount)
  ;; penny is not in the signature, because it equals (- amount
  ;;                                                     (* half-dollar 50)
  ;;                                                     (* quarter 25)
  ;;                                                     (* dime 10)
  ;;                                                     (* nickeli 5))
  ;;                                                     (* two 2))
  (define (count-iter sum half-dollar quarter dime nickeli two)
    (cond ((> (* half-dollar 50) amount)
           sum)
          ((> (+ (* half-dollar 50)
                 (* quarter 20)) amount)
           (count-iter sum (+ half-dollar 1) 0 0 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 20)
                 (* dime 10)) amount)
           (count-iter sum half-dollar (+ quarter 1) 0 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 20)
                 (* dime 10)
                 (* nickeli 5)) amount)
           (count-iter sum half-dollar quarter (+ dime 1) 0 0))
          ((> (+ (* half-dollar 50)
                 (* quarter 20)
                 (* dime 10)
                 (* nickeli 5)
                 (* two 2)) amount)
           (count-iter sum half-dollar quarter dime (+ nickeli 1) 0))
          (else 
                   (count-iter (+ 1 sum) half-dollar quarter dime nickeli (+ two 1)))))
  (count-iter 0 0 0 0 0 0))

对应的c++程序为

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int amount = 100;
 5 
 6 int count_iter(int sum, int half_dollar, int quarter, int dime, int nickeli, int two)
 7 {
 8     //此语句显示了迭代过程中相关变量的数值，便于大家了解迭代过程
       printf("sum = %d, half_dollar = %d, quarter = %d, dime i= %d, \
 9        nickeli = %d, two = %d\n", sum, half_dollar, quarter, dime, nickeli, two);
10             
11     if ( half_dollar * 50 > amount) 
12         return sum;
13    
14     else if ( half_dollar * 50 + quarter * 20 > amount) 
15         count_iter (sum, half_dollar+1, 0, 0, 0, 0);
16    
17     else if ( half_dollar * 50 + quarter * 20 + dime * 10 > amount) 
18         count_iter (sum, half_dollar, quarter+1, 0, 0, 0);
19        
20     else if ( half_dollar * 50 + quarter * 20 + dime * 10 + nickeli * 5 > amount) 
21         count_iter (sum, half_dollar, quarter, dime+1, 0, 0);
22        
23     else if ( half_dollar * 50 + quarter * 20 + dime * 10 + nickeli * 5 + two * 2 > amount) 
24         count_iter (sum, half_dollar, quarter, dime, nickeli+1, 0);      
25           
26     else 
27         count_iter (sum+1, half_dollar, quarter, dime, nickeli, two+1);
28 }
29 
30 int main()
31 {
32 
33   cout << count_iter( 0, 0, 0, 0, 0, 0) << endl;
34   
35   return 0;
36 }

使用DrRacket计算(count-change-true-iterative 100)在1秒以内可以算出结果为4562，计算(count-change-true-iterative 1000)需要大概20秒计算出结果为103119386，显然效率比第一种算法高出不少。

SICP中的零钱兑换问题

推荐阅读