Created
December 30, 2020 16:33
-
-
Save yanfeng42/c8ca3f1c0cc010aad18f91938ab831f7 to your computer and use it in GitHub Desktop.
sicp 练习1.14 (2) 计算步数增长的阶(时间复杂度)
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)) | |
(define color | |
(cond ((= amount 0) "gray80") | |
((= kinds-of-coins 1) "lightblue") | |
((= kinds-of-coins 2) "green") | |
((= kinds-of-coins 3) "firebrick1") | |
((= kinds-of-coins 4) "chocolate2") | |
((= kinds-of-coins 5) "magenta3") | |
(else "gray95") | |
) | |
) | |
(string-append "\"[" (number->string depth) "] " node "\" [label=\"" node "\",color=" color "];\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/
后半部分, 关于 时间复杂度的推演, 让我很受触动.
基于 简单的 从特殊到一般, 从低阶(T(n, 1)) 到 高阶(T(n,5)) 的 递进计算, 辅以 基础的数学知识, 就可以准确计算出 精确的 "计算步骤数".
我原来一直以为 "复杂度" 的计算, 必然都是 非常 高超的 "算法" 计算技巧, 竟然, 也都是 逐步推导出来的.
以后遇到 特殊的 实际的 算法复杂度 对比问题, 我也要试着 实际尝试推导分析下, 而不是简单地 凭直觉 "猜".
附上
(cc 12 2)
对应的图形, 供后续查阅: