练习1.16
根据提示, a*b^n保持不变、使用a来保存结果,观察如下变换过程
求b^100,(b n a)
-->(b 100 a)
-->(b^2 50 a)
-->(b^4 25 a)
此时根据fast-expt的过程,应将25执行减1操作,如果保持a*b^n不变,则可有如下变换
-->(b^4 24 b^4)
即(b^4)^24*b^4=b^100,当n为奇数时,a=a*b,则a=1
-->(b^8 12 b^4)
-->(b^16 6 b^4)
-->(b^32 3 b^4)
此时n为奇数,a=a*b,则
-->(b^32 2 b^36)
-->(b^64 1 b^36)
-->(b^64 0 b^100)
则定义过程如下
(define (fast-iter-expt b n)
(fast-expt-iter b n 1))
(define (fast-expt-iter b counter product)
(cond ((= counter 0) product)
((even? counter) (fast-expt-iter (square b) (/ counter 2) product))
(else (fast-expt-iter b (- counter 1) (* b product)))))
(define (square x)
(* x x))
(define (even? n)
(= (remainder n 2) 0))
练习1.17
(define (* a b)
(if (= b 0)
0
(+ a (* a (- b 1)))))
(define (double x)
(+ x x))
(define (halve x)
(/ x 2))
(define (fast* a b)
(cond ((= b 0) 0)
((even? b) (double (fast* a (halve b))))
(else (+ a (fast* a (- b 1))))))
练习1.18
(define (fast* a b)
(fast*-iter a b 0))
(define (fast*-iter a b v)
(cond ((= b 0) v)
((even? b) (fast*-iter (double a) (halve b) v))
(else (fast*-iter a (- b 1) (+ a v)))))
(define (double x)
(+ x x))
(define (halve x)
(/ x 2))
(define (even? n)
(= (remainder n 2) 0))
练习1.19
已知:T变换对于(a, b)、(p, q),
a = bq + aq + ap
b = bp + aq
则有如下变换过程
(a, b)
-->(bq + aq + ap, bp + aq)
-->(bq' + aq' + ap', bp' + aq')
则有
(1)bq' + aq' + ap' = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
(2)bp' + aq' = (bp + aq)p + (bq + aq + ap)q
将(1)右边展开,得到
bq' + aq' + ap'
= (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
= bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2
= 2bpq + 2apq + 2aq^2 + bq^2 + ap^2
= b(2pq + q^2) + a(2pq + q^2) + a(p^2 + q^2)
则有
p' = p^2 + q^2
q' = 2pq + q^2
代入(2),检测正确
bp' + aq'
= (bp + aq)p + (bq + aq + ap)q
= bp^2 + apq + bq^2 + aq^2 + apq
= b(p^2 + q^2) + a(2pq + q^2)
分享到:
相关推荐
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 in python 中文版 sicp in python 中文版 sicp in python 中文版 download : https://github.com/wizardforcel/sicp-py-zh
请参考那些正在学习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习题解答,主要第一章的内容习题答案
资源来自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解决方案