; ====================================================================== ; ; 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)的整数 ;; (这显而易见，但亦可严格证明)
本文地址：http://com.8s8s.com/it/it23197.htm