SICP-零錢置換的正確迭代實(shí)現(xiàn)

遞歸和迭代的轉(zhuǎn)化，關(guān)鍵需要明確哪些是遞歸的冗余數(shù)據(jù)，也就說(shuō)哪些是迭代可以重復(fù)利用數(shù)據(jù)。下面具體分析。

給不同的coin分配索引

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

遞歸的思路

將總數(shù)為a的現(xiàn)金換成n種硬幣的不同方式的數(shù)目等于

  1. 將現(xiàn)金a換成除第一種硬幣以外的其他硬幣的不同方式，加上2
  2. 將現(xiàn)金a－d換成所有種類硬幣的不同方式。其中d為第一種硬幣的面值。

可以寫遞歸公式

Ct(N) = Ct(N-first-denomination(t)) + Ct-1(N)

t(下標(biāo))為幾種硬幣，N為現(xiàn)金數(shù)。例如：t為5，N為100美分，所以總數(shù)目=(將100美分換成1,5,10,25這四種硬幣組成方法數(shù))+(將100-50美分換成1,5,10,25,50這五種硬幣組成的方法數(shù))

通過(guò)公式進(jìn)行初步運(yùn)算，漸漸會(huì)發(fā)現(xiàn)冗余數(shù)據(jù)(重復(fù)利用的數(shù)據(jù))

C5(100)=C4(100)+C5(50)
    C4(100)==C3(100)+C4(75)
        C3(100)=C2(100)+C3(90)
            C2(100)=C1(100)+C2(95)
                C2(95)=C1(95)+C2(90)
                    C2(90)=C1(90)+C2(85)
                        C2(85)=C1(85)+C2(80)
                            C2(80)=C1(80)+C2(75)
                                C2(75)=C1(75)+C2(70)
                                    ...
            # C2(90) 重復(fù)
            C3(90)=C2(90)+C3(80)
                # C2(80) 重復(fù)
                C3(80)=C2(80)+C3(70)
                    # C2(70) 重復(fù)
                    C3(70)=C2(70)+C3(60)
                        ...
        C4(75)=C3(75)+C4(50)
            C3(75)=C2(75)+C3(65)
                ...
            C4(50)=C3(50)+C4(25)
                ...
    C5(50)=C4(50)+C5(0)
        C5(50)=C4(50)+C5(0)
            ...

上面可能不太直觀

C2(4) = C1(4) + C2(-1)
C2(5) = C1(5) + C2(0)
C2(6) = C1(6) + C2(1)
C2(7) = C1(7) + C2(2)
C2(8) = C1(8) + C2(3)
C2(9) = C1(9) + C2(4) //出現(xiàn)重復(fù)利用值C2(4) 間隔為5
C2(10) = C1(10) + C2(5) //出現(xiàn)重復(fù)利用值C2(5) 間隔為5
C2(11) = C1(11) + C2(6)
C2(12) = C1(12) + C2(7)
C2(13) = C1(13) + C2(8)
C2(14) = C1(14) + C2(9)
C2(15) = C1(15) + C2(10)
C2(16) = C1(16) + C2(11)


C3(4) = C2(4) + C3(-6)
C3(5) = C2(5) + C3(-5)
C3(6) = C2(6) + C3(-4)
C3(7) = C2(7) + C3(-3)
C3(8) = C2(8) + C3(-2)
C3(9) = C2(9) + C3(-1)
C3(10) = C2(10) + C3(0)
C3(11) = C2(11) + C3(1)
C3(12) = C2(12) + C3(2)
C3(13) = C2(13) + C3(3)
C3(14) = C2(14) + C3(4) //出現(xiàn)重復(fù)利用值C3(4) 間隔為10
C3(15) = C2(15) + C3(5) //出現(xiàn)重復(fù)利用值C3(5) 間隔為10
C3(16) = C2(16) + C3(6)

所以對(duì)于C2來(lái)說(shuō)，始終需要緩存5個(gè)可以重復(fù)利用值(長(zhǎng)度為5的緩存隊(duì)列);對(duì)于C3，始終需要緩存10個(gè)可以重復(fù)利用值(長(zhǎng)度為10的緩存隊(duì)列);對(duì)于C4，使用需要緩存25個(gè)(...);對(duì)于C5來(lái)說(shuō)，使用需要緩存50個(gè)可以重復(fù)利用值(...)

迭代思路

  1. 迭代是線性O(shè)(n)時(shí)間+常量空間消耗(不會(huì)隨n改變)
  2. 迭代需要重復(fù)利用遞歸產(chǎn)生的冗余數(shù)據(jù).
  3. 迭代的狀態(tài)能由這些變量完全刻畫

假設(shè)有5種硬幣，現(xiàn)金100美分

C 源碼

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


#include <stdlib.h>
#include <stdio.h>
#include <string.h>
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;
}

// 這里這里也是關(guān)鍵點(diǎn)，這個(gè)尾遞歸的結(jié)束由t(當(dāng)前需要兌換的金錢)和amount(需要兌換的目標(biāo)金錢)控制，為線性，也就是說(shuō)時(shí)間復(fù)雜度為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\n", 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);
    }
}

// 對(duì)于C1、C2、C3、C4、C5緩存隊(duì)列開始的位置
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);
    }
}

// 分配固定的緩存, 無(wú)論需要兌換多少金錢，只要金幣種類不變，緩存的大小就是固定的。 空間復(fù)雜度為常量。
// "因?yàn)樗臓顟B(tài)能由其中的三個(gè)狀態(tài)變量完全刻畫，解釋器在執(zhí)行 這一計(jì)算過(guò)程時(shí)，只需要保存這三個(gè)變量的軌跡就足夠了" 這句話在這里就有體現(xiàn)了
int *get_tmp_array(int kinds_of_coins) {
    int *tmp;
    int i;
    int sum = 0;
    for(i=1 ; i<kinds_of_coins ; i++) {
        sum += get_coin(i);
    }
    tmp = (int *)malloc(sizeof(int) * sum);
    memset(tmp, 0 ,sizeof(int) * sum);
    return tmp;
}

// 獲取重復(fù)利用值, 每次緩存隊(duì)列頭的位置
// 比如: 此時(shí)緩存隊(duì)列為[C2(0), C2(1), C2(2), C2(3), C2(4)]
// C2(5) = C1(5) + C2(0) 此時(shí)我們需要取緩存隊(duì)列頭的值C2(0)
// 計(jì)算完得到C2(5)，需要執(zhí)行update_recycle_value將得到C2(5)進(jìn)隊(duì)列，除去舊的C2(0)，此時(shí)隊(duì)列頭尾C2(1)，即為計(jì)算C2(6)需要的緩存值
int get_recycle_value(int index_of_coin, int current_amount, int *tmp_array) {
    int t = get_index_tmp(index_of_coin);
    if(current_amount < get_coin(index_of_coin)){
        return 0;
    }
    else if(current_amount == get_coin(index_of_coin)){
        return 1;
    }
    else {
        return tmp_array[t];
    }
}

// 更新重復(fù)利用值(隊(duì)列的概念), 計(jì)算出最新的值，需要替換舊的利用值
// 比如: C2(5) = C1(5) + C2(0)
// 現(xiàn)在C2緩存隊(duì)列中有[C2(0), C2(1), C2(2), C2(3), C2(4)]，我們需要將C2(5)進(jìn)隊(duì)列，[C2(1), C2(2), C2(3), C2(4), C2(5)]
void update_recycle_value(int index_of_coin, int *tmp_array, int value) {
    int i;
    int t = get_index_tmp(index_of_coin);
    for(i = 0; i< (get_coin(index_of_coin)-1); i++) {
        tmp_array[t+i] = tmp_array[t+i+1];
    }
    tmp_array[t+get_coin(index_of_coin)-1] = value;
}

參考

http://stackoverflow.com/questions/1485022/sicp-making-change/

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 1. Java基礎(chǔ)部分 基礎(chǔ)部分的順序：基本語(yǔ)法，類相關(guān)的語(yǔ)法，內(nèi)部類的語(yǔ)法，繼承相關(guān)的語(yǔ)法，異常的語(yǔ)法，線程的語(yǔ)...
    子非魚_t_閱讀 34,638評(píng)論 18贊 399
  • 一. Java基礎(chǔ)部分.................................................
    wy_sure閱讀 4,010評(píng)論 0贊 11
  • 3.2 函數(shù)和所生成的過(guò)程 來(lái)源：3.2 Functions and the Processes They G...
    布客飛龍閱讀 1,143評(píng)論 0贊 37
  • 流星劃過(guò)一剎那的故事 在那一刻虔誠(chéng)的許下我的世界 從心里面留下未來(lái)的愿景 煙火燦爛一時(shí)的美好 在那一刻匆忙的身影駐...
    劃一座城池閱讀 158評(píng)論 0贊 2
  • 交通燈一直很喜歡自己的工作。他在繁忙的十字路口高高矗立著，有三只大大的眼睛，左右一紅一綠，中間一黃。他的工作...
    Clearness閱讀 387評(píng)論 0贊 1

友情鏈接更多精彩內(nèi)容