Last active
September 10, 2021 12:41
-
-
Save yanfeng42/70379d28385b470eb7ab47da1a9fd6de to your computer and use it in GitHub Desktop.
sicp 2.19: 可视化的方式, 展示零钱本身的顺序, 对计算过程的不同影响.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
; 源码 1.14.scm 中有一部分. | |
; 既有实现的输出: 4. | |
(count-change 10) | |
; 新的实现... | |
(define us-coins (list 50 25 10 5 1)) | |
(define us-coins-0 (list 1 5 10 25 50)) | |
(define us-coins-1 (list 50 5 10 1 25)) | |
(define uk-coins (list 100 50 20 10 5 2 1 0.5)) | |
; 与旧版实现等价的输入. 4. | |
(cc 10 us-coins 0) | |
; 尝试不同的顺序. | |
(cc 10 us-coins-0 0) | |
(cc 10 us-coins-1 0) | |
; 新的实现. | |
(define (cc amount coin-values depth) | |
(define kinds-of-coins (length coin-values)) | |
(define from-node (cc-node-depth amount kinds-of-coins depth)) | |
(display (cc-node-depth-label amount kinds-of-coins depth)) | |
(cond | |
((= amount 0) 1) | |
((or (< amount 0) (no-more? coin-values)) 0) | |
(else (let ((to-node (cc-node-depth amount (- kinds-of-coins 1) (+ depth 1)))) (display (cc-link from-node to-node))) | |
(let ((to-node (cc-node-depth (- amount (first-denomination coin-values)) kinds-of-coins (+ depth 1)))) (display (cc-link from-node to-node))) | |
(+ | |
;除第一种硬币之外的所有其他硬币的不同方式的数目. | |
(cc amount (except-first-denomination coin-values) (+ depth 1)) | |
; 将现金 a - d 换成所有种类的硬币的不同方式的数目. | |
(cc (- amount (first-denomination coin-values)) coin-values (+ depth 1)) | |
) | |
) | |
) | |
) | |
; 需要定义的方法. | |
(define (no-more? l) (= (length l) 0)) | |
(define (except-first-denomination l) (cdr l)) | |
(define (first-denomination l) (car l)) | |
Author
yanfeng42
commented
Sep 10, 2021
digraph G {
node [color = gray95,style=filled];
graph [ranksep=0.3,size=7];
node [color = gray95,style=filled,fontsize=9,shape=box, margin=.08, width=0, height=0 ];
edge [penwidth=.1, arrowsize=0.5];
"[0] (cc 10 5)" [label="(cc 10 5)"];
"[0] (cc 10 5)" -> "[1] (cc 10 4)";
"[0] (cc 10 5)" -> "[1] (cc -40 5)";
"[1] (cc 10 4)" [label="(cc 10 4)"];
"[1] (cc 10 4)" -> "[2] (cc 10 3)";
"[1] (cc 10 4)" -> "[2] (cc 5 4)";
"[2] (cc 10 3)" [label="(cc 10 3)"];
"[2] (cc 10 3)" -> "[3] (cc 10 2)";
"[2] (cc 10 3)" -> "[3] (cc 0 3)";
"[3] (cc 10 2)" [label="(cc 10 2)"];
"[3] (cc 10 2)" -> "[4] (cc 10 1)";
"[3] (cc 10 2)" -> "[4] (cc 9 2)";
"[4] (cc 10 1)" [label="(cc 10 1)"];
"[4] (cc 10 1)" -> "[5] (cc 10 0)";
"[4] (cc 10 1)" -> "[5] (cc -15 1)";
"[5] (cc 10 0)" [label="(cc 10 0)"];
"[5] (cc -15 1)" [label="(cc -15 1)"];
"[4] (cc 9 2)" [label="(cc 9 2)"];
"[4] (cc 9 2)" -> "[5] (cc 9 1)";
"[4] (cc 9 2)" -> "[5] (cc 8 2)";
"[5] (cc 9 1)" [label="(cc 9 1)"];
"[5] (cc 9 1)" -> "[6] (cc 9 0)";
"[5] (cc 9 1)" -> "[6] (cc -16 1)";
"[6] (cc 9 0)" [label="(cc 9 0)"];
"[6] (cc -16 1)" [label="(cc -16 1)"];
"[5] (cc 8 2)" [label="(cc 8 2)"];
"[5] (cc 8 2)" -> "[6] (cc 8 1)";
"[5] (cc 8 2)" -> "[6] (cc 7 2)";
"[6] (cc 8 1)" [label="(cc 8 1)"];
"[6] (cc 8 1)" -> "[7] (cc 8 0)";
"[6] (cc 8 1)" -> "[7] (cc -17 1)";
"[7] (cc 8 0)" [label="(cc 8 0)"];
"[7] (cc -17 1)" [label="(cc -17 1)"];
"[6] (cc 7 2)" [label="(cc 7 2)"];
"[6] (cc 7 2)" -> "[7] (cc 7 1)";
"[6] (cc 7 2)" -> "[7] (cc 6 2)";
"[7] (cc 7 1)" [label="(cc 7 1)"];
"[7] (cc 7 1)" -> "[8] (cc 7 0)";
"[7] (cc 7 1)" -> "[8] (cc -18 1)";
"[8] (cc 7 0)" [label="(cc 7 0)"];
"[8] (cc -18 1)" [label="(cc -18 1)"];
"[7] (cc 6 2)" [label="(cc 6 2)"];
"[7] (cc 6 2)" -> "[8] (cc 6 1)";
"[7] (cc 6 2)" -> "[8] (cc 5 2)";
"[8] (cc 6 1)" [label="(cc 6 1)"];
"[8] (cc 6 1)" -> "[9] (cc 6 0)";
"[8] (cc 6 1)" -> "[9] (cc -19 1)";
"[9] (cc 6 0)" [label="(cc 6 0)"];
"[9] (cc -19 1)" [label="(cc -19 1)"];
"[8] (cc 5 2)" [label="(cc 5 2)"];
"[8] (cc 5 2)" -> "[9] (cc 5 1)";
"[8] (cc 5 2)" -> "[9] (cc 4 2)";
"[9] (cc 5 1)" [label="(cc 5 1)"];
"[9] (cc 5 1)" -> "[10] (cc 5 0)";
"[9] (cc 5 1)" -> "[10] (cc -20 1)";
"[10] (cc 5 0)" [label="(cc 5 0)"];
"[10] (cc -20 1)" [label="(cc -20 1)"];
"[9] (cc 4 2)" [label="(cc 4 2)"];
"[9] (cc 4 2)" -> "[10] (cc 4 1)";
"[9] (cc 4 2)" -> "[10] (cc 3 2)";
"[10] (cc 4 1)" [label="(cc 4 1)"];
"[10] (cc 4 1)" -> "[11] (cc 4 0)";
"[10] (cc 4 1)" -> "[11] (cc -21 1)";
"[11] (cc 4 0)" [label="(cc 4 0)"];
"[11] (cc -21 1)" [label="(cc -21 1)"];
"[10] (cc 3 2)" [label="(cc 3 2)"];
"[10] (cc 3 2)" -> "[11] (cc 3 1)";
"[10] (cc 3 2)" -> "[11] (cc 2 2)";
"[11] (cc 3 1)" [label="(cc 3 1)"];
"[11] (cc 3 1)" -> "[12] (cc 3 0)";
"[11] (cc 3 1)" -> "[12] (cc -22 1)";
"[12] (cc 3 0)" [label="(cc 3 0)"];
"[12] (cc -22 1)" [label="(cc -22 1)"];
"[11] (cc 2 2)" [label="(cc 2 2)"];
"[11] (cc 2 2)" -> "[12] (cc 2 1)";
"[11] (cc 2 2)" -> "[12] (cc 1 2)";
"[12] (cc 2 1)" [label="(cc 2 1)"];
"[12] (cc 2 1)" -> "[13] (cc 2 0)";
"[12] (cc 2 1)" -> "[13] (cc -23 1)";
"[13] (cc 2 0)" [label="(cc 2 0)"];
"[13] (cc -23 1)" [label="(cc -23 1)"];
"[12] (cc 1 2)" [label="(cc 1 2)"];
"[12] (cc 1 2)" -> "[13] (cc 1 1)";
"[12] (cc 1 2)" -> "[13] (cc 0 2)";
"[13] (cc 1 1)" [label="(cc 1 1)"];
"[13] (cc 1 1)" -> "[14] (cc 1 0)";
"[13] (cc 1 1)" -> "[14] (cc -24 1)";
"[14] (cc 1 0)" [label="(cc 1 0)"];
"[14] (cc -24 1)" [label="(cc -24 1)"];
"[13] (cc 0 2)" [label="(cc 0 2)",color=gray80];
"[3] (cc 0 3)" [label="(cc 0 3)",color=gray80];
"[2] (cc 5 4)" [label="(cc 5 4)"];
"[2] (cc 5 4)" -> "[3] (cc 5 3)";
"[2] (cc 5 4)" -> "[3] (cc 0 4)";
"[3] (cc 5 3)" [label="(cc 5 3)"];
"[3] (cc 5 3)" -> "[4] (cc 5 2)";
"[3] (cc 5 3)" -> "[4] (cc -5 3)";
"[4] (cc 5 2)" [label="(cc 5 2)"];
"[4] (cc 5 2)" -> "[5] (cc 5 1)";
"[4] (cc 5 2)" -> "[5] (cc 4 2)";
"[5] (cc 5 1)" [label="(cc 5 1)"];
"[5] (cc 5 1)" -> "[6] (cc 5 0)";
"[5] (cc 5 1)" -> "[6] (cc -20 1)";
"[6] (cc 5 0)" [label="(cc 5 0)"];
"[6] (cc -20 1)" [label="(cc -20 1)"];
"[5] (cc 4 2)" [label="(cc 4 2)"];
"[5] (cc 4 2)" -> "[6] (cc 4 1)";
"[5] (cc 4 2)" -> "[6] (cc 3 2)";
"[6] (cc 4 1)" [label="(cc 4 1)"];
"[6] (cc 4 1)" -> "[7] (cc 4 0)";
"[6] (cc 4 1)" -> "[7] (cc -21 1)";
"[7] (cc 4 0)" [label="(cc 4 0)"];
"[7] (cc -21 1)" [label="(cc -21 1)"];
"[6] (cc 3 2)" [label="(cc 3 2)"];
"[6] (cc 3 2)" -> "[7] (cc 3 1)";
"[6] (cc 3 2)" -> "[7] (cc 2 2)";
"[7] (cc 3 1)" [label="(cc 3 1)"];
"[7] (cc 3 1)" -> "[8] (cc 3 0)";
"[7] (cc 3 1)" -> "[8] (cc -22 1)";
"[8] (cc 3 0)" [label="(cc 3 0)"];
"[8] (cc -22 1)" [label="(cc -22 1)"];
"[7] (cc 2 2)" [label="(cc 2 2)"];
"[7] (cc 2 2)" -> "[8] (cc 2 1)";
"[7] (cc 2 2)" -> "[8] (cc 1 2)";
"[8] (cc 2 1)" [label="(cc 2 1)"];
"[8] (cc 2 1)" -> "[9] (cc 2 0)";
"[8] (cc 2 1)" -> "[9] (cc -23 1)";
"[9] (cc 2 0)" [label="(cc 2 0)"];
"[9] (cc -23 1)" [label="(cc -23 1)"];
"[8] (cc 1 2)" [label="(cc 1 2)"];
"[8] (cc 1 2)" -> "[9] (cc 1 1)";
"[8] (cc 1 2)" -> "[9] (cc 0 2)";
"[9] (cc 1 1)" [label="(cc 1 1)"];
"[9] (cc 1 1)" -> "[10] (cc 1 0)";
"[9] (cc 1 1)" -> "[10] (cc -24 1)";
"[10] (cc 1 0)" [label="(cc 1 0)"];
"[10] (cc -24 1)" [label="(cc -24 1)"];
"[9] (cc 0 2)" [label="(cc 0 2)",color=gray80];
"[4] (cc -5 3)" [label="(cc -5 3)"];
"[3] (cc 0 4)" [label="(cc 0 4)",color=gray80];
"[1] (cc -40 5)" [label="(cc -40 5)"];
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment