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)的整数
;; (这显而易见，但亦可严格证明)
