; ======================================================================
;
;          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)