SICP习题1.16要求将书中递归形式的求幂过程fast-expt改写成迭代的。
如果对我们之前对于递归计算过程和迭代计算过程理解的比较透彻的话做这道题问题不大。
首先看看书中的fast-expt过程:
(define (fast-expt b n)
(cond ((= n 0) 1)
((even? n) (square (fast-expt b (/ n 2))))
(else (* b (fast-expt b (- n 1))))))
可以清晰地看到过程中的square操作和 *操作是被推迟的操作,必须要等递归调用的fast-expt函数返回后才能进行计算,这就是我们之前曾经讨论过的递归计算过程。
为了将他们改成迭代计算过程,需要将延时操作的部分提前完成,需要提前的操作包括下面两个:
;(square (fast-expt b (/ n 2)))中的square操作
;和(* b (fast-expt b (- n 1)))中的*的操作
就是要在进入递归调用前完成square和*计算。
(square (fast-expt b (/ n 2)))部分比较简单。
就是将
(square (fast-expt b (/ n 2)))
改成:
(fast-expt (square b) (/ n 2))
也就是将:
(b的“n/2”次方)的平方
变成了:
(“b的平方”的“n/2”次方)
就像书中提到的,这两个是等价的。
通过这样的变换,我们就在计算“n/2次方”之前提前将“b的平方”计算完成了,这样就将延时计算的square操作提前完成了。
对于 (* b (fast-expt b (- n 1)))的部分就比较麻烦一点
比如我们要求4的7次方,这里是将它变形为(“4的6次方”x 4),其中x4这个操作就是需要延迟计算的操作,如何将x4这个操作提前完成呢?
因为都是乘法,什么时候计算都可以,我们可以定义一个临时变量,给一个基数1,每次发现一个需要延迟计算的x4操作就将这个临时变量x4,到最后再算总帐,将平方计算结果和这个临时变量相乘。
所以我们就需要给fast-expt加多一个参数,将:
(* b (fast-expt b (- n 1)))
改成:
(fast-expt b (- n 1) (* b temp-val))
既然加多了一个参数,我们还需要回去考虑(fast-expt (square b) (/ n 2))的部分,在这部分计算里,临时变量是不需要改变的,所以应该写为:(fast-expt (square b) (/ n 2) temp-val)
最终我写的过程如下:
(define (fast-expt-iter b n temp-val)
(cond ((= n 0) 1)
((= n 1) (* b temp-val))
((even? n) (fast-expt-iter (square b) (/ n 2) temp-val))
(else (fast-expt-iter b (- n 1) (* temp-val b)))))
使用时的调用形式如下:
(fast-expt-iter b n 1)
回顾以上对递归计算过程的迭代变换,其关键在于引入了那个临时变量,这也是书上提到的定义一个不变量的方法,这种方法在很多情况下都可以用来将递归计算过程装换为迭代计算过程。
分享到:
相关推荐
SICP 习题答案 计算机程序的构造和解释 1-3章 习题答案
SICP习题解答,主要第一章的内容习题答案
NULL 博文链接:https://pengpeng.iteye.com/blog/1344689
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 CHINESE ENGLISH THE SECOND EDITION SICP CHINESE ENGLISH THE SECOND EDITION
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 download : https://github.com/wizardforcel/sicp-py-zh
资源来自pypi官网。 资源全名:sicp-0.0.1b102.dev4.tar.gz
sicp 2ed高清pdf,以及相对应的mit课程资料及习题答案打包,中文版的视频在这里http://i.youku.com/i/UNTcxODk3ODQw/videos?spm=a2hzp.8244740.0.0
SICP 解题集《计算机程序的构造和解释》练习题解集。安装 MIT/GNU Scheme(macOS)下载:下载后运行 .dmg 文件,把 MIT/GNU Scheme.app 拖入 Applications 文件夹在 Applications/应用程序 文件夹中找到 MIT/GNU ...
sicp-in-python(中文版+英文版)PDF 背景. SICP 全称Structure and Interpretation of Computer Programs,翻译过来叫《计算机程序的构造和解释》使用python
资源名称:sicp 和 操作系统:精髓与设计原理第七版资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
经典书籍《计算机程序的构造与解释》,UCB热门课程CS61a的官方教材
#SICP SICP解决方案