`

sicp 1.11 1.12习题解答

阅读更多
    这个小节主要讲解了迭代与树形递归,递归比起迭代更易于理解和直观,而迭代相比于递归则效率更高,一般计算机的递归实现都是使用堆栈结构实现的,当递归层次太深的时候容易导致栈溢出,而迭代则没有这样的问题。
习题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 11)
              ((
= x 21)
              ((
= y 11)
              ((
= x y) 1)
              (
else 
              (
+ (pascal (- x 1) y) (pascal (- x 1) (- y 1))))))




dennis 2007-05-09 14:57 发表评论
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics