; ====================================================================== ; ; 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)
本文地址：http://com.8s8s.com/it/it23191.htm