|
|
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的整數(shù)。
|