CG@CPPBLOG

/*=========================================*/
随笔 - 76, 文章 - 39, 评论 - 137, 引用 - 0
数据加载中……

我的SICP习题答案(1.11~1.13)

1.11
递归计算过程为
(define func-recu
  (lambda(n)
    (cond ((< n 
3) n)
          (else (+ (func-recu (- n 
1))
                   (* 
2 (func-recu (- n 2)))
                   (* 
3 (func-recu (- n 3))))))))
迭代计算过程为
(define func-iter
  (lambda(a b c n)
    (if (
= n 0)
        a
        (func-iter b c (+ (* 
3 a) (* 2 b) c) (- n 1)))))

(define (func n) (func-iter 
0 1 2 n))

1.12
中文版原题翻译有误,应为计算pascal三角中的元素。
;pas(n,k)
;
if (k=1) or (k=n), then pas(n,k) = 1
;
else pas(n,k) = pas(n-1,k-1) + pas(n-1,k)

(define pas (lambda(n k)
              (if (or (
= k 1) (= k n))
                  
1
                  (+ (pas (- n 
1) (- k 1))
                     (pas (- n 
1) k)))))

1.13
中文版原题翻译遗漏 提示 :ψ=(1-√5)/2
已知,φ^2 = φ + 1, 那么 φ^n = φ^(n-1) + φ^(n-2)

同理,
ψ^2 = ψ + 1, 那么 ψ^n = ψ^(n-1) + ψ^(n-2)
φ-ψ = (1+√5)/2 - (1-√5)/2 = √5

when n=0, Fib(0) = 0 =
(φ^0-ψ^0)/√5
when n=1, Fib(1) = 1 = √5/√5 = (φ-ψ)/√5
when n>2, Fib(n) = Fib(n-1) + Fib(n-2) = (φ^(n-1)-ψ^(n-1))/
√5 + (φ^(n-2)-ψ^(n-2))/√5
                 = ((
φ^(n-1)+(φ^(n-2))) - (ψ^(n-1)+ψ^(n-2)))/√5
                 = (φ^n - ψ^n)/√5

又 -1<
ψ < 0, 故 -0.5< -1/
√5< ψ^n/√5 < 1/√5 <0.5 , 而 φ^n/√5 = ψ^n/√5 + Fib(n)

可知 |
φ^n/√5 - Fib(n)| < 0.5, Fib(n)是最接近φ^n/√5的整数。


posted on 2008-03-12 23:10 cuigang 阅读(1457) 评论(0)  编辑 收藏 引用 所属分类: Lisp/Scheme我的SICP答案


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理