; ======================================================================
;
; Structure and Interpretation of Computer Programs
; (trial answer to excercises)
;
; 计算机程序的构造和解释(习题试解)
;
; created: code17 02/27/05
; modified:
; (保持内容完整不变前提下，可以任意转载)
; ======================================================================
;; SICP No.1.14
;; 本题为理解题
;; 以 (a k) 代表 (cc a k)，即以后k种硬币构成数额为a的方案
;; (11 5)->(-39 5)->0
;; |
;; V
;; (11 4)->(-14 4)->0
;; |
;; V
;; (11 3)->(1 3)->(-9 3)->0
;; | |
;; | V
;; | (1 2)->(-4 2)->0
;; | |
;; | V
;; | (1 1)->(0 1)->1
;; | |
;; | V
;; | (1 0)->0
;; V
;; (11 2)->(6 2)->(1 2)->(-4 2)->0
;; | | |
;; | | V
;; | | (1 1)->(0 1)->1
;; | | |
;; | | V
;; | | (1 0)->0
;; | V
;; | (6 1)->(5 1)->(4 1)->(3 1)->(2 1)->(1 1)->(0 1)->1
;; | | | | | | |
;; | V V V V V V
;; | (6 0) (5 0) (4 0) (3 0) (2 0) (1 0)
;; | | | | | | |
;; | V V V V V V
;; | 0 0 0 0 0 0
;; V
;; (11 1)->(10 1)->(9 1)->(8 1)->(7 1)->(6 1)->(5 1)->(4 1)->(3 1)->(2 1)->(1 1)->(0 1)->1
;; | | | | | | | | | | |
;; V V V V V V V V V V V
;; (11 0) (10 0) (9 0) (8 0) (7 0) (6 0) (5 0) (4 0) (3 0) (2 0) (1 0)
;; | | | | | | | | | | |
;; V V V V V V V V V V V
;; 0 0 0 0 0 0 0 0 0 0 0
;; 符号/表示取整除法，但当x足够大时，x/y约等于x除以y的实数商
;;
;; 空间复杂度s(n)=[theta](n)
;;
;; 在任何一次调用时，我们只需要keep track从根节点到当前节点的路径，
;; 设硬币种类为k, 最小面额为m，显然，最长路径约为(k+n/m)
;; 所以s(n)与n为线性关系，s(n)=[theta](n)
;;
;; 时间复杂度t(n)=[theta](n^5)
;;
;; 设将数量为n的金额换算成k种硬币(面额依次为mk,m(k-1),...m1)的步骤数为T(n,k)
;; (1) 显然T(n,1)=3n/m1 与n成线性关系（参照图中从(11 1)开始的部分，亦可证明）
;; (2) T(n,2) = T(n,1) + T(n-m2,1) + T(n-2*m2),1) + ... + T(n-(n/m2)*m2,1)
;; = [sigma]T(n-x*m2,1) (x从0到n/m2)
;; = [sigma]T(y*m2,1) (y从n/m2到0)
;; = 3*m2/m1*[sigma](y) (y从n/(m_2)到0)
;; = 3/(2*m1*m2)*(n^2+m2^2*n) (公式 1+2+...n = (n+1)n/2)
;; 所以T(n,2)为[theta](n^2)
;; (3) T(n,3) = T(n,2) + T(n-m3,2) + T(n-2*m3,2) + ... + T(n-(n/m3)*m3,1)
;; 所以，和T(n,2)对应，它被分解为n/m3项之和，第x项的最高次为x^2，由此可知
;; T(n,3)的数量级为[theta](n^3) (公式 1^2+ 2^2+... + n^2 = n(n+1)(2n+1)/6)
;; (4) 同理可得T(n,4), T(n,5)
;; 因此时间复杂度t(n)为[theta](n^5)，更一般的情况下当我们有k种硬币，t(n)为[theta](n^k)
