SICP学习笔记 1.2.2 树形递归
? 练习1.11
? ?递归过程
?
(define (func n) (if (< n 3) n (+ (* 1 (func (- n 1))) (* 2 (func (- n 2))) (* 3 (func (- n 3))))))????
? ? 迭代过程
?
(define (func n) (fun-iter 0 1 2 n))(define (fun-iter a b c count) (if (= count 0) a (fun-iter b c (+ (* 1 c) (* 2 b) (* 3 a)) (- count 1))))
?
? 练习1.12
?
(define (pasca n i) (cond ((= i 1) 1)((= i (+ n 1)) 1) (else (+ (pasca (- n 1) (- i 1)) (pasca (- n 1) i)))))
?
?
? 练习1.13
?
? ? 已知:f(n+1) = f(n) + f(n-1) ? (1)
?
? ? 设存在f(n+1) + x*f(n) = y*[f(n) + x*f(n-1)] ?(2),则有
? ? f(n+1) = (y-x)*f(n) + x*y*f(n-1)
? ? 根据(1)，则有y-x=1, x*y=1，则有x*(x+1)=1
? ? 此方程有解
? ? x=(√5-1)/2、y=(√5+1)/2
? ? 则存在等比数列f'(n),其首项为f(2) + [(√5-1)/2]*f(1) = (√5+1)/2,公比为(√5+1)/2
? ? 则f'(n) = [(√5+1)/2]^n,即
? ? f(n+1) + [(√5-1)/2]*f(n) = [(√5+1)/2]^n ??
? ? f(n+1) = [(1-√5)/2]*f(n) + [(√5+1)/2]^n ? ? (3)
?
? ? 设存在f(n+1) + x*[(√5+1)/2]^(n+1) = [(1-√5)/2]*[f(n) + x*[(√5+1)/2]^n] ? (4),则有
? ? f(n+1) = [(1-√5)/2]*f(n) + [(√5+1)/2]^n*(-√5*x)
? ? 根据(2),则有
? ? -√5*x=1,则x=-√5/5
? ? 代入(4),得
? ? f(n+1) - (√5/5)*[(√5+1)/2]^(n+1) = [(1-√5)/2]*[f(n) - (√5/5)*[(√5+1)/2]^n]
? ? 则存在等比数列f''(n),其首项为f(1)- (√5/5)*[(√5+1)/2] = (5-√5)/10,公比为(1-√5)/2
? ? 则f''(n) = [(5-√5)/10]*[(1-√5)/2]^(n-1)，则
? ? f(n)- (√5/5)*[(√5+1)/2]^n = -(√5/5)*[(1-√5)/2]^n
? ? f(n) = (√5/5)*[(√5+1)/2]^n - (√5/5)*[(1-√5)/2]^n
?
? ? 若有φ=(√5+1)/2、ψ=(1-√5)/2，则有
? ? f(n)=(φ^n-ψ^n)/√5
? ? 所以 φ^n/√5 = f(n) + ψ^n/√5
? ? 而ψ=(1-√5)/2，-1 < ψ < 0,则-1 < ψ^n < 1,则-√5/5 < ψ^n/√5 < √5/5
? ? 又√5/5 < 1,所以f(n)是最接近φ^n/√5的整数
?
?
