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