首页 > 代码库 > SICP 找零钱问题背后的思考

SICP 找零钱问题背后的思考

问题见SICP P26
 

此问题的递归方法很简单,类似于背包的思想。

     即金额为amount的现金换成n种硬币的种类数 满足循环不变式:
          count_change(amount,n)=count_change(amount,n-1)+count_change(amount-amount_of_first_coin,n)
     递归中止条件是:当a=0,结果为1
                    a<0,结果为0
                    当n=0 结果也为0
  • 将上述规则转换为scheme代码,在Drracket中运行
 1      #lang racket 2      (define (count-change amount kinds-of-coins)  3           ( cond ((= amount 0) 1) 4          ((or (< amount 0) (= kinds-of-coins 0))0) 5          (else  6            (+(count-change amount (- kinds-of-coins 1)) (count-change (- amount (some-coin kinds-of-coins)) kinds-of-coins )) ) ) ) 7    8      (define (some-coin kinds-of-coins) 9        ( cond ((= kinds-of-coins 1) 1)10          ((= kinds-of-coins 2) 5)11          ((= kinds-of-coins 3) 10)12          ((= kinds-of-coins 4) 25)13          ((= kinds-of-coins 5) 50)))14 15   (count-change 45 5)

 


  • 上述代码在解决amount=300以上的时候已经十分缓慢了,原因在于这是个递归,并非尾递归(迭代),有大量重复和冗余的计算在其中,但此问题比斐波那契数复杂,因为
      斐波那契数的问题,我们容易将其转化为迭代,因为此问题性质很好,每次分支只有2,每个问题直接满足最优自问题性质。但换零钱问题则不然,无法简单的化为尾递归,那么除了将递归转化为迭代外,另一个折衷的优化技巧是动态规划。
 
               思路如下:
                    零钱coin=[c1,c2,c3……]
                   【 amount金额的钱币换成 kind_of_coins种零钱的种类数】=【只有一种零钱c1换的种类数】+【用两种零钱c1 c2的种类数】+……
                    可以看到,【用两种零钱c1 c2的种类数】就是在【只有一种零钱c1换的种类数】的基础上对第二个零钱c2做同样处理
         
 1  //cpp 2           #include <iostream> 3           #include <vector> 4           using namespace std; 5  6           int main () 7           {      8                  int amount = 55; 9                  const int kind_of_coins = 5 ;10                  int coin [ kind_of_coins] = { 1 , 5 , 10, 25 , 50 };11                  vector< int > result ( amount + 1 , 0 );12                  result [0 ] = 1;13       14                  for (int i = 0 ; i < kind_of_coins; ++ i ){15                        int j = coin[ i ];16                        for (; j <= amount; ++ j )17                              result [j ] += result[ j - coin [ i]];18                   }19 20               cout << result [amount ] << endl;21               system ("pause" );22       23           }24  
          改用python:
        
 1  //cpp 2           #include <iostream> 3           #include <vector> 4           using namespace std; 5  6           int main () 7           {      8                  int amount = 55; 9                  const int kind_of_coins = 5 ;10                  int coin [ kind_of_coins] = { 1 , 5 , 10, 25 , 50 };11                  vector< int > result ( amount + 1 , 0 );12                  result [0 ] = 1;13       14                  for (int i = 0 ; i < kind_of_coins; ++ i ){15                        int j = coin[ i ];16                        for (; j <= amount; ++ j )17                              result [j ] += result[ j - coin [ i]];18                   }19 20               cout << result [amount ] << endl;21               system ("pause" );22       23           }

 

 递归和迭代是一个从编程语言入门开始即有的问题,然后会不断重复感觉理解了,又发现新的内容,又感觉理解了的过程。
不论是c++还是python,语法上给出的都是循环结构,而显示的循环结构实质上是尾递归模式,就是迭代的一种刻画,而尾递归要比循环更容易体现迭代的内涵,
但是,这些c 家族的语言都不支持尾递归,所以你写成尾递归,有两种可能:第一种,编译器把它优化为循环;第二种,编译器把它作为普通递归来处理,冗余的计算很多。
因此,我们一般都将递归优化为循环。
 
容易让我们产生错觉,循环是高效的,而递归是低效的。
 
让我们看看scheme,lisp的一种方言,语法中支持尾递归来实现迭代,对于斐波那契数生成的两个版本:

#lang racket

递归版本
(define (fibonacci n)
  (cond( (= n 0) 0)
     ( (= n 1) 1)
    (else (+ (fibonacci (- n 1)) (fibonacci (- n 2))))))

 

迭代版本

#lang racket
(define (fibonacci n)
  (fib 0 1 n))
(define (fib first-number second-number n)
  (if   (= n 0)

    first-number
    (fib second-number (+ first-number second-number) (- n 1) )))

 容易发现,迭代比递归快的多,因为它没有多余的重复计算,而且更重要的是它每次维护常数空间,而无须先扩展再收缩,并且还要记住运算的轨迹。
 
而一般的优化方法除了改为迭代,还有人工模拟栈或者动态规划,栈模拟没什么好说的,将递归栈人为构建。
而动态规划呢,其实很简单,就是我们对递归过程不能转化为尾递归即迭代的情况下,人为的记录下子过程的返回值,计算大过程的时候就可以直接范围,缺点在于需要维护一个比较大的空间,是典型的空间换时间,不过这是值得的,存储一定程度上的廉价的,而时间效率更加宝贵(当然有一定限度,若是存储无限算法意义变得微小)。