这个小节主要讲解了迭代与树形递归,递归比起迭代更易于理解和直观,而迭代相比于递归则效率更高,一般计算机的递归实现都是使用堆栈结构实现的,当递归层次太深的时候容易导致栈溢出,而迭代则没有这样的问题。
习题1.11是这样的: 如果n<3,那么f(n)=n;如果n>=3,那么f(n)=f(n-1)+2f(n-2)+3f(n-3),请写一个采用递归计算过程f的过程,再改写一个采用迭代计算过程计算f的过程。解答:
1.采用递归的话就很简单了,可以将条件直接描述为一个lisp过程,没什么好解释的:
<!---->(define (f n)
(if (< n 3)
n
(+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))
2。迭代就相对麻烦点,将递归转化为迭代,关键在于找出迭代每一步之间的差异,这个差异就是每次迭代变化的量,找出这个固定编号的量就是问题的关键。很容易就可以看出f(n)和f(n-1)之间的差距就是:2f(n-2)+3f(n-3)。这就提示我们需要保持3个顺序的状态变量:f(n-2)、 f(n-1) 、f(n),迭代向前一步的时候:f(n-2)被f(n-1)取代,f(n-1)被f(n)取代,将f(n)+2f(n-2)+3f(n-3)做为新的f(n)。迭代是自底向上,初始化的3个变量就是0、1、2,这样就可以相应地写出一个迭代版本的解答:
<!---->(define (f-iter a b c n)
(if (= n 2)
c
(f-iter b c (+ c (* 2 b) (* 3 a)) (- n 1))))
(define (f-i n) (f-iter 0 1 2 n))
可以测试一下,在n数目比较大的时候,递归版本速度明显变慢甚至栈溢出,而迭代版本就比较快了。
习题1.12:用递归过程描述帕斯卡三角(或者说杨辉三角)根据杨辉三角的特点,x行y列的数字等于x-1行y列的数字和x-1行y-1列的数字之和,就可以解决这个问题:
<!---->(define (pascal x y)
(cond ((> y x) (display "error"))
((= x 1) 1)
((= x 2) 1)
((= y 1) 1)
((= x y) 1)
(else
(+ (pascal (- x 1) y) (pascal (- x 1) (- y 1))))))
分享到:
相关推荐
SICP习题解答,主要第一章的内容习题答案
SICP 习题答案 计算机程序的构造和解释 1-3章 习题答案
NULL 博文链接:https://pengpeng.iteye.com/blog/1344689
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 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-in-python(中文版+英文版)PDF 背景. SICP 全称Structure and Interpretation of Computer Programs,翻译过来叫《计算机程序的构造和解释》使用python
sicp 2ed高清pdf,以及相对应的mit课程资料及习题答案打包,中文版的视频在这里http://i.youku.com/i/UNTcxODk3ODQw/videos?spm=a2hzp.8244740.0.0
资源名称:sicp 和 操作系统:精髓与设计原理第七版资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
经典书籍《计算机程序的构造与解释》,UCB热门课程CS61a的官方教材
#SICP SICP解决方案
超声高速铣削和高速铣削高体分SiCp/Al MMCs的粗糙度研究,向道辉,岳广喜,结合正交分析和单因素分析对高体分SiCp/MMCs在超声高速和高速铣削两种实验条件下的粗糙度进行分析,研究铣削速度、进给量和切削深度