此题充分展示了如何将递归转化为迭代的技巧:定义一个不变量,要求它在迭代状态之间保持不变!题目如下:
写一个过程求平方,并且只用对数个步骤。
解答:
考虑一个附加状态a,如何保持ab**n(b**n表示b的n次方)在状态改变间保持不变.
1)当n是偶数:
a(b
2)
n/2 = ab
n
b
n = (b
n/2)
2 = (b
2)
n/2
在这个过程中回溯状态的迁移:
<!---->
a ← a
b ← b2
n ← n/2
2)当n是奇数:
(ab)b
(n-1) = ab
n
回溯状态的变迁:
<!---->
a ← a * b
b ← b
n ← n-1
就此可以写出lisp过程了:
<!---->(define (even? n) (= (remainder n 2) 0))
(define (square n) (* n n))
(define (fast-expr b n)
(define (iter a b n)
(cond ((= n 0) a)
((even? n) (iter a (square b) (/ n 2)))
(else (iter (* a b) b (- n 1)))))
(iter 1 b n))
这道题目一开始我的解答完全错了!-_-,我理解错了题意,一直将指数对半折,这样的步骤是n/2步而不是对数步骤,阶仍然是(theta)(n):
<!---->(define (fast-expt-iter b product counter)
(cond ((= counter 0) product)
((even? counter) (fast-expt-iter b (* (square b) product) (* 2 (- (/ counter 2) 1))))
(else
(* b (fast-expt-iter b product (- counter 1)))
)))
(define (fast-exptt b n)
(fast-expt-iter b 1 n))
分享到:
相关推荐
SICP习题解答,主要第一章的内容习题答案
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 !!!download>>>https://github.com/wizardforcel/sicp-py-zh
SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版
SICP-Python版本
SICP 使用的scheme解释器 以前叫DrScheme
sicp 2.2.4节图形语言的racket程序包,配置路径,C:\Users\Administrator\AppData\Roaming\Racket
Python SICP epub版本,很适合学习抽象的思想,用Python版本比lisp更实用
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
NULL 博文链接:https://pengpeng.iteye.com/blog/1344689
资源来自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解决方案
sicp 2ed高清pdf,以及相对应的mit课程资料及习题答案打包,中文版的视频在这里http://i.youku.com/i/UNTcxODk3ODQw/videos?spm=a2hzp.8244740.0.0
超声高速铣削和高速铣削高体分SiCp/Al MMCs的粗糙度研究,向道辉,岳广喜,结合正交分析和单因素分析对高体分SiCp/MMCs在超声高速和高速铣削两种实验条件下的粗糙度进行分析,研究铣削速度、进给量和切削深度