其他语言

本类阅读TOP10

·基于Solaris 开发环境的整体构思
·使用AutoMake轻松生成Makefile
·BCB数据库图像保存技术
·GNU中的Makefile
·射频芯片nRF401天线设计的分析
·iframe 的自适应高度
·BCB之Socket通信
·软件企业如何实施CMM
·入门系列--OpenGL最简单的入门
·WIN95中日志钩子(JournalRecord Hook)的使用

分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
sicp习题试解 (1.14)

作者:未知 来源:月光软件站 加入时间:2005-5-13 月光软件站

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




相关文章

相关软件