(define (cuigang) (coding))

(define (coding) (coding))

我的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 阅读(596) 评论(0)  编辑 收藏 引用 所属分类: Lisp/Scheme 、我的SICP答案


标题  
姓名  
主页
验证码 *
内容(提交失败后,可以通过“恢复上次提交”恢复刚刚提交的内容)  
  登录  使用高级评论  新用户注册  返回页首  恢复上次提交      
[使用Ctrl+Enter键可以直接提交]
相关链接:
网站导航: