sicp习题试解 (1.13)

; ======================================================================

;

; Structure and Interpretation of Computer Programs

; (trial answer to excercises)

;

; 计算机程序的构造和解释(习题试解)

;

; created: code17 02/25/05

; modified:

; (保持内容完整不变前提下，可以任意转载)

; ======================================================================

;; SICP No.1.13

;; 本题为理解题

;; 1.

;; [phi] = (1+sqrt(5))/2 是方程

;; x^2-x-1=0 (0)

;; 的一个根，设另一根为[varphi]

;; [varphi] = (1-sqrt(5))/2

;; 显然，可得以下性质

;; [phi]+[varphi] = 1 (1)

;; [phi]-[varphi] = sqrt(5) (2)

;; [phi]*[varphi] = -1 (3)

;; 2.

;; 使用自然归纳法证明 Fib(n) = ([phi]^n - [varphi]^n) / sqrt(5)

;; 当 n=0 时，Fib(0) = 0

;; ([phi]^0 -[varphi]^0) / sqrt(5) = (1 - 1) / sqrt(5) = 0

;; 左右两边相等

;; 当 n=1 时，Fib(1) = 1

;; 根据性质(2)，([phi]^1 - [varphi]^1) / sqrt(5) = 1

;; 左右两边相等

;; 假设当 n=k-1 和 n=k-2 时均成立(k>=2), 则

;; 当 n=k 时

;; Fib(k)

;; = Fib(k-1) + Fib(k-2)

;; = [phi]^(k-1) - [varphi]^(k-1) + [phi]^(k-2) + [varphi]^(k-2)

;; = ([phi]^k * ([phi]^-1 + [phi]^-2) +

;; [varphi]^k * ([varphi]^-1 + [varphi]^-2)) / sqrt(5)

;; = ([phi]^k * (-[varphi]+[varphi]^2) +

;; [varphi]^k * (-[phi]+[phi]^2)) / sqrt(5) (根据性质(3))

;; = ([phi]^k * 1 + [varphi]^k * 1) / sqrt(5) (根据性质(0))

;; = ([phi]^k + [phi]^k) / sqrt(5)

;; 也满足这个等式, 因此命题得证

;; 3. 因此

;; Fib(n) - [phi]^n/sqrt(5) = -[varphi]/sqrt(5)

;; |Fib(n) - [phi]^n/sqrt(5)| = |[varphi]|^n/sqrt(5)

;; 所以Fib(n)和[phi]^n/sqrt(5)间的差

;; diff = |Fib(n)-[phi]^n/5| = |[varphi]|^n/sqrt(5)

;; 当 n=0 时 diff=1/sqrt(5) < 0.5 而|[varphi]| < 1

;; 易由归纳法得, 对任何正整数n，均有 diff<0.5

;; 即整数Fib(n)与[phi]^n/sqrt(5)的差总是小于0.5

;; 所以Fib(n)是最靠近[phi]^n/sqrt(5)的整数

;; (这显而易见，但亦可严格证明)