Created
December 28, 2020 18:49
-
-
Save yanfeng42/8eb1ff0b0636bd3594e99a7072c96aa9 to your computer and use it in GitHub Desktop.
SICP练习1.14. 使用 GrapViz 可视化 零钱问题的 递归计算步骤.
This file contains 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
| (define (count-change amount) | |
| (cc amount 5 0) | |
| ) | |
| (define (cc amount kinds-of-coins depth) | |
| (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) (= kinds-of-coins 0)) 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 kinds-of-coins)) kinds-of-coins (+ depth 1)))) (display (cc-link from-node to-node))) | |
| (+ | |
| ;除第一种硬币之外的所有其他硬币的不同方式的数目. | |
| (cc amount (- kinds-of-coins 1) (+ depth 1)) | |
| ; 将现金 a - d 换成所有种类的硬币的不同方式的数目. | |
| (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins (+ depth 1)) | |
| ) | |
| ) | |
| ) | |
| ) | |
| (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 (cc-node amount kinds-of-coins) | |
| ; (cc 11 5) | |
| (string-append "(cc " (number->string amount) " " (number->string kinds-of-coins) ")") | |
| ) | |
| (define (cc-node-depth amount kinds-of-coins depth) | |
| (define node (cc-node amount kinds-of-coins)) | |
| ; "[0] (cc 11 5)" | |
| (string-append "\"[" (number->string depth) "] " node "\"") | |
| ) | |
| (define (cc-node-depth-label amount kinds-of-coins depth) | |
| (define node (cc-node amount kinds-of-coins)) | |
| ; "[0] (cc 11 5)" [label="(cc 11 5)", ]; | |
| ; "[15] (cc 0 1)" [label="(cc 0 1)",color=gray80]; | |
| (if (= amount 0) | |
| (string-append "\"[" (number->string depth) "] " node "\" [label=\"" node "\",color=gray80];\n") | |
| (string-append "\"[" (number->string depth) "] " node "\" [label=\"" node "\"];\n") | |
| ) | |
| ) | |
| (define (cc-link from-node to-node) | |
| ; "[0] (cc 11 5)" -> "[1] (cc 11 4)"; | |
| (string-append from-node " -> " to-node ";\n") | |
| ) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
https://codology.net/post/sicp-solution-exercise-1-14/ 有提到这种思路, 不过并没有给出 打印 gv dot 的具体方式.
这种 基于 GrapViz 来辅助理解 空间复杂度的解法, 让人很新奇, 也很使用. 后续必将成为一个 很强势的 基础技能.
特实现下 gv 的输出代码, 同时熟悉/温习下 gv 的基础语法.
如果想自己看效果的, 可以安装 VSCode 的 GrapViz 插件.
我自己打印了下
(count-change 13)