SICP換零錢迭代方法實現，是如何寫的？

01-27

scheme小菜，最近看書，看到換零錢這個問題，
(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))) x 想了好久都沒想出來這道題迭代怎麼寫，有能講解一下的大神嗎？查了一下資料，有的說是動態規劃，有的說是背包

我一開始也不懂，不過畫了圖以後就明白了。

用了最大的面額的，減去最大面額的值，遞歸。
沒有用最大面額兌換的，不考慮最大的面額，遞歸。

然後這樣就會展開一個二叉樹，其中樹葉的數量就是總數，可以畫圖來看一下：

這張圖是用這樣的方法，用1, 2, 5 去劃分 6的情況。每個節點的左枝是第一種方法所遞歸的，右枝是第二種。(update: 之前這裡左右搞反了。)

然後藍色的線就代表每個葉子所對應的排列方式。

說真的，原理並不難，這一段不知道為什麼寫得感覺有點繁瑣。

用迭代也沒那麼麻煩（非原創）

n = 30 v = [1, 5, 10, 25, 50] L = [i==0 for i in range(n+1)]

for i in range(len(v)): for j in xrange(v[i], len(L)): L[j] += L[j - v[i]] print L[n]

看看輸出結果有什麼規律：

(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)))

(define (display-change amount)
  (display (cc amount 5))
  (display "	")
  (display (cc amount 4))
  (display "	")
  (display (cc amount 3))
  (display "	")
  (display (cc amount 2))
  (display "	")
  (display (cc amount 1))
  (display "	")
  (display (cc amount 0))
  (newline)
  (if (&> amount 0)

    (display-change (- amount 1))))

(display-change 100)

結果：

292 242 121 21 1 0 252 213 110 20 1 0 252 213 110 20 1 0 252 213 110 20 1 0 252 213 110 20 1 0 252 213 110 20 1 0 218 187 100 19 1 0 218 187 100 19 1 0 218 187 100 19 1 0 218 187 100 19 1 0 218 187 100 19 1 0 187 163 90 18 1 0 187 163 90 18 1 0 187 163 90 18 1 0 187 163 90 18 1 0 187 163 90 18 1 0 159 141 81 17 1 0 159 141 81 17 1 0 159 141 81 17 1 0 159 141 81 17 1 0 159 141 81 17 1 0 134 121 72 16 1 0 134 121 72 16 1 0 134 121 72 16 1 0 134 121 72 16 1 0 134 121 72 16 1 0 112 103 64 15 1 0 112 103 64 15 1 0 112 103 64 15 1 0 112 103 64 15 1 0 112 103 64 15 1 0 93 87 56 14 1 0 93 87 56 14 1 0 93 87 56 14 1 0 93 87 56 14 1 0 93 87 56 14 1 0 77 73 49 13 1 0 77 73 49 13 1 0 77 73 49 13 1 0 77 73 49 13 1 0 77 73 49 13 1 0 62 60 42 12 1 0 62 60 42 12 1 0 62 60 42 12 1 0 62 60 42 12 1 0 62 60 42 12 1 0 50 49 36 11 1 0 50 49 36 11 1 0 50 49 36 11 1 0 50 49 36 11 1 0 50 49 36 11 1 0 39 39 30 10 1 0 39 39 30 10 1 0 39 39 30 10 1 0 39 39 30 10 1 0 39 39 30 10 1 0 31 31 25 9 1 0 31 31 25 9 1 0 31 31 25 9 1 0 31 31 25 9 1 0 31 31 25 9 1 0 24 24 20 8 1 0 24 24 20 8 1 0 24 24 20 8 1 0 24 24 20 8 1 0 24 24 20 8 1 0 18 18 16 7 1 0 18 18 16 7 1 0 18 18 16 7 1 0 18 18 16 7 1 0 18 18 16 7 1 0 13 13 12 6 1 0 13 13 12 6 1 0 13 13 12 6 1 0 13 13 12 6 1 0 13 13 12 6 1 0 9 9 9 5 1 0 9 9 9 5 1 0 9 9 9 5 1 0 9 9 9 5 1 0 9 9 9 5 1 0 6 6 6 4 1 0 6 6 6 4 1 0 6 6 6 4 1 0 6 6 6 4 1 0 6 6 6 4 1 0 4 4 4 3 1 0 4 4 4 3 1 0 4 4 4 3 1 0 4 4 4 3 1 0 4 4 4 3 1 0 2 2 2 2 1 0 2 2 2 2 1 0 2 2 2 2 1 0 2 2 2 2 1 0 2 2 2 2 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1

如上表，記右下為A[0][0]，左上為A[5][100]。

只有1分硬幣的時候，就只有一種換法，所以A[1][0]到A[1][100]都是1。

有1分、5分硬幣的時候，由於0～4都小於5，所以A[2][0]=A[1][0]，A[2][1]=A[1][1]，A[2][2]=A[1][2]，A[2][3]=A[1][3]，A[2][4]=A[1][4]。

對於A[2][5]，可分兩種情況討論：不用5分硬幣，那就是A[1][5]。用一個5分硬幣，那就是A[2][0]。

於是A[2][5]=A[1][5]+A[2][0]。同理，A[2][6]=A[1][6]+A[2][1]……

通式就是

A[0][n]=0

A[1][n]=A[0][n]+A[1][n-1] (n&>=1)

A[2][n]=A[1][n]+A[2][n-5] (n&>=5)

A[3][n]=A[2][n]+A[3][n-10] (n&>=10)

A[4][n]=A[3][n]+A[4][n-25] (n&>=25)

A[5][n]=A[4][n]+A[5][n-50] (n&>=50)

【為何要有A[0]呢，是為了方便將A[1也納入到通式裡面去。而且最小的硬幣未必一定是1分】

#include &

int count_change(int n) { int A[n+1]; int kind[5] = {1, 5, 10, 25, 50}; A[0] = 1; for (int j = 1; j &<= n; j++) A[j] = 0; for (int i = 0; i &< 5; i++) { for (int j = kind[i]; j &<= n; j++) { A[j] += A[j - kind[i]]; } } return A[n]; } int main(void) { printf("%d", count_change(100)); return 0; }

SICP換零錢迭代方法實現，是如何寫的？ - 匿名用戶的回答

這個回答使用的就是A[1][n]數組，另外也可以使用A[5][50]，但是可以這樣做是因為50是其他幾個數字的公倍數（通常的面額硬幣是這樣的）。要是有奇葩面額的硬幣，比如30分，應該使用幾個數字的最小公倍數。

我自己搞騰了一個，線性迭代，可能看起來有點傻，畢竟才剛開始學，廢話不多說，上代碼：

(define (change-count w)

(cc 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (+ (/ w 5 ) 1 )1 2 4 ))

#初始值設定，中間的（+（/w 5）1）是因為我找規律的時候發現硬幣總數每加5，換硬幣的方法才改變一次

(define (even? u)

(= (remainder u) 0 ))

#這個是用來判斷偶數的

(define (cc a b c d e f g h i j k l m n o p q x y)

(cond ((= p q) a)

((even? q) (cc (- (+ y e j) o) a b c d e f g h i j k l m n p (+ q 1) x (+ y q 3)))

(else (cc (- (+ x e j) o) a b c d e f g h i j k l m n p (+ q 1) (+ x q 3) y))))

#這個是我找規律發現的。。。具體很難用口語表示。。。自己拿去用，上機調試。。。自己研究吧。。。

哇塞！知乎終於有我能夠回答的題了，第一次回答問題，好激動！

最近也在看SICP，不是迭代嘛，動態規劃，背包什麼的不太懂。用最笨的方法，窮舉唄。

提供5種面值貨幣：50,25,10,5,1

設每種數量分別對應n1,n2,n3,n4,n5

然後迭代，為了簡單貨幣面值順序就按從大到小排列了，計算臨時換得錢的數量temp，和需要換的錢amount比較

當temp (amount - temp)

當temp = amount ，sum+1，判斷從n5到n2是否等於0，不等0就讓其為0，前一位加1,繼續迭代，當n5到n2都為0,就返回最後結果

當temp &> amount ，sum不變，之後同上

以下是用common lisp實現的。（cl剛入門，我怎麼貼不了圖）

(defparameter *half* 50)

(defparameter *quarter* 25)

(defparameter *dime* 10)

(defparameter *nickel* 5)

(defparameter *pennies* 1)

(defun count-change (amount)

(cc-iter 0 0 0 0 0 amount 0))

(defun cc-iter (n1 n2 n3 n4 n5 amount sum)

(let ((temp (+ (* n1 *half*)

(* n2 *quarter*)

(* n3 *dime*)

(* n4 *nickel*)

(* n5 *pennies*))))

(cond ((((= temp amount) (cc-iter-1 n1 n2 n3 n4 n5 amount (1+ sum)))

((&> temp amount) (cc-iter-1 n1 n2 n3 n4 n5 amount sum)))))

(defun cc-iter-1 (n1 n2 n3 n4 n5 amount sum)

(if (= n5 0)

(if (= n4 0)

(if (= n3 0)

(if (= n2 0)

(princ sum)

(cc-iter (1+ n1) 0 0 0 0 amount sum))

(cc-iter n1 (1+ n2) 0 0 0 amount sum))

(cc-iter n1 n2 (1+ n3) 0 0 amount sum))

(cc-iter n1 n2 n3 (1+ n4) 0 amount sum)))

電腦上不能回答，只好手機回答了，代碼這樣。。。

想看清楚代碼，可以看我的博客

http://blog.sina.com.cn/s/blog_7daf3d040101od8p.html

SICP：換零錢方式統計問題

#include &

#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))

int g_all_coins[] = {1, 5, 10, 25, 50};

#define COIN_NUM ARRAY_SIZE(g_all_coins)

int count(int sz, int coins[], int total)

{

int t_coins[COIN_NUM] = {0};

if(total == 0) return 1;

if(total &< 0) return 0;

if(sz &<= 0) return 0;

for(int i = 0; i &< sz - 1; i++)

{

t_coins[i] = coins[i+1];

}

return count(sz-1, t_coins, total) + count(sz, coins, total-coins[0]);

}

#define TOTAL 100

int main(int argc, char* argv[])

{

printf("count(%d) = %d
", TOTAL, count(COIN_NUM, g_all_coins, TOTAL));

return 0;

}

update: 之前的方法迭代不徹底,速度還不夠好(只提高了一倍),現在的方法更好,很快.

;;;迭代-遞歸方法 ;;思路:發現cc在(a+50,any c)的數值只依賴cc在(a,any c)和(a-5,3)的數值. ;;所以只要儲存這6個數值(用列表),就可以迭代到下一組cc了. ;;;輔助函數:從一組生成下一組(用遞歸生成) (define cc-aux;return the new-list at a=a0+n*50 (lambda (n a0 i0);a0, a=a0+n*50, i0:initial list at a0 (define (aux a c) (cond [(= c 1) 1] [(= a a0) (list-ref i0 c)] [(and (= a (- a0 5)) (= c 3)) (list-ref i0 0)] [else (+ (aux a (- c 1)) (aux (- a (value-of-coin c)) c))])) (cons (aux (- (+ a0 (* n 50)) 5) 3) (map (lambda (c) (aux (+ a0 (* n 50)) c)) (list 1 2 3 4 5))))) ;;test (cc-aux 2 0 (list 0 1 1 1 1 1)) (cc-aux 1 50 (cc-aux 1 0 (list 0 1 1 1 1 1)));;same with above ;;;用遞歸cc-rec生成第一組(i0),再用cc-aux迭代 (define cc-iter (lambda (a) (let* ([a0 (remainder a 50)] [i0 (cons (cc-rec (- a0 5) 3);;cc-rec (map (lambda (c) (cc-rec a0 c)) (list 1 2 3 4 5)))]) (let iter ([now a0] [result i0]) (if (= now a) result (iter (+ now 50) (cc-aux 1 now result))))))) (define cc (lambda (a c) (list-ref (cc-iter a) c)))

---------------------------------第一種不高效方法---------------------------

;;;換零錢的迭代方法(尾遞歸方法) ;;和fibonacci序列不同,那裡是一維序列(fib n), ;;這裡是二維陣列(cc amount kinds-of-coins),但可以只考慮迭代amount. ;;為了書寫方便, a即是amount,c即是kinds-of-coins (define cc-iter (lambda (a c) (if (= c 1) 1 (let ([val-c (value-of-coin c)]) (let iter ([result 0];記錄累積值 [rest a]);判斷迭代結束 (if (&< rest 0) result (iter (+ result (cc-iter rest (- c 1))) (- rest val-c)))))))) (define value-of-coin;;這個過程就是書中的過程first-denomination (lambda (c) (cond [(= c 1) 1] [(= c 2) 5] [(= c 3) 10] [(= c 4) 25] [(= c 5) 50])))

發現lisp真是難寫啊.那麼多括弧.

用sml寫一個, 和寫數學差不多.

fun countChange (sum, coins) = case sum of 0 =&> 1 | s =&> if s&<0 then 0 else case coins of [] =&> 0 |x::xs =&> countChange(sum,xs) + countChange(sum-x,x::xs);

countChange(100,[50,25,10,5,1]);

最近在用clojure實現sicp中的代碼，剛好做到這裡，我採用線性迭代的方式計算的，根據該解法的遞歸定義，將調用棧保存在了堆裡面。我沒優化啊，但是性能應該比遞歸的好吧，我猜的。

換零錢問題的非遞歸解法 SICP 1.2.2中的一個問題

動態規劃是比較有效率的，無論是時間還是空間上。下面給出一個簡單的代碼：

#include & #include &


using namespace std;

int main(){ int amount = 100; int kindsOfCoins[] = {1, 5, 10, 25, 50}; int lengthOfKOC = 5;//上一行數組的長度 vector& dp(amount+1, 0); dp[0] = 1; for(int i = 0; i &< lengthOfKOC; i++){ for(int j = kindsOfCoins[i]; j &<= amount; j++){ dp[j] += dp[j - kindsOfCoins[i]]; } } cout &<&< dp[amount] &<&< endl; }

也是最近看SICP，看到很多寫的並不對，比如把回溯演算法也算上，還有就是類似第一位回答者那樣，空間消耗並非常量。對於遞歸轉迭代我覺得有幾點是很重要的，SICP上也寫的很清楚。

迭代是線性O(n)時間+常量空間消耗(不會隨n改變)
迭代需要重複利用遞歸產生的冗餘數據.
迭代的狀態能由固定個數變數完全刻畫

這裡把代碼貼出來。這段代碼時間消耗是O(n)，空間消耗是常量，迭代狀態由tmp緩存和t完全刻畫。

具體的分析寫在blog

Jmpews
– sicp換零錢

/* * ===================================================================================== * * Filename: p26.c * * Description: change money * * Version: 1.0 * Created: 2016/08/02 14時58分22秒 * Revision: none * Compiler: gcc * * Author: jmpews (jmpews.github.io), jmpews@gmail.com * * ===================================================================================== */


#include &

#include &

#include &

int count_change(int amount);

int cc(int amount, int kinds_of_coins);

void count_iter(int *tmp, int t, int amount);

int get_coin(int index_of_coin);

int get_index_tmp(int index_of_coin);

int *get_tmp_array(int kinds_of_coins);

int get_recycle_value(int index_of_coin, int current_amount, int *tmp_array);

void update_recycle_value(int index_of_coin, int *tmp_array, int value);
int main ( int argc, char *argv[] )

{

    int t;

    t = count_change(100);

    printf("%d", t);

    return EXIT_SUCCESS;

}               /* ----------  end of function main  ---------- */
int count_change(int amount) {

    cc(amount, 5);

    return 0;

}
int cc(int amount, int kinds_of_coins) {

    int *tmp = get_tmp_array(kinds_of_coins);

    int t = 0;

    tmp[0] = 0;

    count_iter(tmp, t, amount);

    return 0;

}
// 這裡這裡也是關鍵點，這個尾遞歸的結束由t(當前需要兌換的金錢)和amount(需要兌換的目標金錢)控制，為線性，也就是說時間複雜度為O(n)

void count_iter(int *tmp, int t, int amount) {

    int r;

    r = get_recycle_value(1, t, tmp);

    update_recycle_value(1, tmp, r);
    //C2(t) = C2(t-get_coin(2)) + C1(t)

    r = get_recycle_value(2, t, tmp) + r;

    update_recycle_value(2, tmp, r);
    //C3(t) = C3(t-get_coin(3)) + C2(t)

    r = get_recycle_value(3, t, tmp) + r;

    update_recycle_value(3, tmp, r);
    //C4(t) = C4(t-get_coin(4)) + C3(t)

    r= get_recycle_value(4, t, tmp) + r;

    update_recycle_value(4, tmp, r);
    //C5(t) = C5(t-get_coin(5)) + C4(t)

    r = get_recycle_value(5, t, tmp) + r;

    if(t == amount) {

        printf("final-value: %d

", r);

        exit(1);

    }

    update_recycle_value(5, tmp, r);
    count_iter(tmp, t+1, amount);

}
int get_coin(int index_of_coin) {

    switch(index_of_coin) {

        case 1: return 1;

        case 2: return 5;

        case 3: return 10;

        case 4: return 25;

        case 5: return 50;

        default: exit(1);

    }

}
// 對於C1、C2、C3、C4、C5緩存隊列開始的位置

int get_index_tmp(int index_of_coin) {

    switch(index_of_coin) {

        case 1: return 0;

        case 2: return 1;

        case 3: return 6;

        case 4: return 16;

        case 5: return 41;

        default: exit(1);

    }

}
// 分配固定的緩存, 無論需要兌換多少金錢，只要金幣種類不變，緩存的大小就是固定的。 空間複雜度為常量。

// "因為它的狀態能由其中的三個狀態變數完全刻畫，解釋器在執行 這一計算過程時，只需要保存這三個變數的軌跡就足夠了" 這句話在這裡就有體現了

int *get_tmp_array(int kinds_of_coins) {

    int *tmp;

    int i;

    int sum = 0;

    for(i=1 ; i&

這個問題我在這邊文章里有回答：讀書筆記-SICP換零錢的遞歸法與迭代法

SICP所說的迭代應該是指線性迭代，如果設計成迭代 應該使用空間複雜度為常數（僅用有限個變數保存中間值）的迭代演算法，我覺得問題的關鍵在於怎麼用空間複雜度為常數（僅用一個或兩個變數來存儲中間過程值），由於程序結果可以用一個變數來表示（僅有一個值）所以理論上這樣的迭代演算法是存在的，但更重要的問題是怎麼在不增加時間複雜度的情況下，能夠做到這種空間複雜度為常數的演算法（因為感覺窮舉法符合我說的線性迭代，但貌似時間代價比原來高），我覺得更值得思考的是這個問題如果能夠解決，等價于思考出了一個演算法：僅用空間複雜度為常數的線性迭代演算法計算任何一個二叉樹的葉子結點數，所以其中的意義並不是沒有

用谷歌好像可以找到，去stackflow找答案吧~很難寫。

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace ConsoleApplication1

{

    class Program

    {

        static int[] first_denomination = new int[6] { 0, 1, 5, 10, 25, 50 };

        static void Main(string[] args)

        {

            int ccamount;

            ccamount =Convert.ToInt32(Console.ReadLine());

            Console.WriteLine(cc(ccamount, 5));

            Console.ReadKey();

        }

        static int cc(int amount,int kindofcoins)

        {

            if (amount == 0)

            {

                return 1;

            }

            else if (kindofcoins == 0||amount&<0)
            {
                return 0;
            }
            else
            {
                return cc(amount - first_denomination[kindofcoins],kindofcoins)+cc(amount,kindofcoins-1);
            }
        }
    }
}

隨便寫了個C#的代碼，其實書在第26頁的時候講的比較詳細了已經（我用的是中文版的）。
將總數為a的現金換成n種硬幣的不同方式的數目等於
·將現金a換成除第一種硬幣之外的所有其他硬幣的不同方式數目加上
·將現金數a-d換成所有和數的硬幣的不同方式數目，其中d是第一種硬幣的幣值
什麼，不理解？
用更加通俗的話來講就是
·完全不管第一種硬幣的數目再加上
·算上第一種硬幣的數目（因為算上了第一種，所以還剩下a-d這麼多的錢來分）
理解了這個，就可以開始遞歸了。
上面代碼的核心部分便是cc(amount - first_denomination[kindofcoins],kindofcoins)+cc(amount,kindofcoins-1);
將其分為兩個部分來看
·cc(amount,kindofcoins-1)
·cc(amount - first_denomination[kindofcoins],kindofcoins)
其中kindofcons就是硬幣的種數，也就是書中所說的n，amount就是現金a了！
而cc函數，簡單來講就是cc(需要換成硬幣的現金，有哪幾種硬幣)
那麼cc(amount,kindofcoins)意思就是：我需要把amount這麼多的現金，用kindofcoins這幾種硬幣來換！
再看一次剛才代碼的兩個核心部分：
·cc(amount,kindofcoins-1)
·cc(amount - first_denomination[kindofcoins],kindofcoins)
是不是感覺有點理解了呢
·把amount這麼多的現金，用kindofcoins-1這幾種硬幣來換！//是不是和一開始說的，完全不管第一種硬幣一樣呢
·把amount-first_denomination[kindofcoins]這麼多的現金，用kindofcoins這幾種硬幣來換！//這就是算上第一種硬幣的情況了
至於first_denomination[kindofcoins]是什麼東西，就不用我多說了吧。
別忘了數組第一個數字是從0開始的！！！
如果到這都能理解，那就已經完全OK了！

  推薦閱讀：


※根據遞推關係，如何編程計算這個數列的前10項？
※入門 Lisp 有哪些在線資料？
※Emacs 的配置文件為什麼會用 Lisp 語言來寫？
※Chez scheme是怎樣一個編譯器啊，聽說編譯後的scheme代碼速度能媲美C？有人用過么？
※SICP第二章里的「圖形語言」在DrRacket 或者MIT Scheme上有沒有辦法實現啊？
TAG:Lisp | Scheme | SICP |