练习1.14
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount (- kinds-of-coins 1))
(cc (- amount (first-denomination kinds-of-coins))
kinds-of-coins)))))
(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)))
图为二叉树,其中由根节点到最底层的叶子的路径为
(cc 11 5)->(cc 11 4)->(cc 11 3)->(cc 11 2)->(cc 11 1)->(cc 10 1)->(cc 9 1)->(cc 8 1)->(cc 7 1)->(cc 6 1)->(cc 5 1)->(cc 4 1)->(cc 3 1)->(cc 2 1)->(cc 1 1)->(cc 0 1)
则数的深度为n+5,则空间增长阶为O(n)
设f(n, k)为计算amount分为kinds种货币时需要的步骤,则由图中可知
f(1, 1)=2
f(2, 1)=4
f(3, 1)=6
......
则有f(n, 1) = 2*n,则f(n, 1)步骤增长阶为O(n)
而f(n, 2) = f(n, 1) + f(n-5, 2)f(n-5, 2), f(n-5, 2) = f(n-5, 1) + f(n-5*2, 2) ......
设m=n/5(整数),则有
f(n, 2) = f(n-5*0, 1) + f(n-5*1, 1) + f(n-5*2, 1) + ...... + f(n-5*m, 1)
= 2*[(n-5*0) + (n-5*1) + (n-5*2) + ...... + (n-5*m)]
= 2*[n*m - 5*(0 + 1 + 2 + ...... +m)]
= 2*[n*m - 5*[m*(m+1)/2]]
= 2*n*m - 5*(m^2+1)
则有f(n, 2)步骤增长阶为O(n^2)
同理推得f(n, 5)步骤增长阶为O(n^5)
练习1.15
define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
(sine 12.15) --> (p (sine 4.05))
--> (p (p (sine 1.35)))
--> (p (p (p (sine 0.45))))
--> (p (p (p (p (sine 0.15)))))
--> (p (p (p (p (p (sine 0.05))))))
a) 12.15=0.05*3^5,p被使用5次
b) 设a=x*3^n,其中x小于0.1,则有
a/3^n=x<0.1
--> 10a/3^n<1
--> 10a<3^n
--> lg(10a)<lg(3^n)
--> lg(10a)/lg3<n
则其增长的阶为O(lga)
- 大小: 39.9 KB
分享到:
相关推荐
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 !!!download>>>https://github.com/wizardforcel/sicp-py-zh
SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版
SICP-Python版本
Python SICP epub版本,很适合学习抽象的思想,用Python版本比lisp更实用
SICP 使用的scheme解释器 以前叫DrScheme
Learn_sicp 学习sicp的一些代码
sicp 2.2.4节图形语言的racket程序包,配置路径,C:\Users\Administrator\AppData\Roaming\Racket
sicp_notes SICP笔记和练习 资源 笔记 使用第一版,最高为ex 1.24。 从ex 1.31开始切换到第二版。
SICP 解题集
SICP CHINESE ENGLISH THE SECOND EDITION SICP CHINESE ENGLISH THE SECOND EDITION
SICP 习题答案 计算机程序的构造和解释 1-3章 习题答案
请参考那些正在学习SICP的人。 笔记 如果你想在 gauch 中使用随机函数 (use math.mt-random) (define m (make <mersenne> :seed (sys-time))) (mt-random-integer m 1000) (define (random n) (mt-random-integer ...
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 download : https://github.com/wizardforcel/sicp-py-zh
SICP习题解答,主要第一章的内容习题答案
资源来自pypi官网。 资源全名:sicp-0.0.1b102.dev4.tar.gz
sicp-in-python(中文版+英文版)PDF 背景. SICP 全称Structure and Interpretation of Computer Programs,翻译过来叫《计算机程序的构造和解释》使用python
资源名称:sicp 和 操作系统:精髓与设计原理第七版资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
经典书籍《计算机程序的构造与解释》,UCB热门课程CS61a的官方教材
#SICP SICP解决方案