SICP学习笔记08 vvipi 发表于2018年12月26日,阅读：3219 ### 练习1.36 请修改fixed-point过程，使它能打印出计算过程中产生的近似值序列，利用newline和display基本过程。而后通过找出 `x->log(1000)/log(x)`的不动点的方式，确定x^x=1000的一个根。请比较一下采用平均阻尼和不用平均阻尼时的计算步数。（注意不要用猜测1去启动fixed-point，因为这将导致除以log(1)=0) ### 解答 ```scheme (define (average a b) (/ (+ a b) 2)) (define tolerance 0.00001) ; 希望达到的精确度 (define (fixed-point f first-guess) (define (close-enough? a b) ; 判断猜测值是否足够接近 (< (abs (- a b)) tolerance)) (define (try guess) ; 迭代进行猜测 (display guess) (newline) (let ((next (f guess))) (if (close-enough? guess next) next (try next)))) (try first-guess)) (display (fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0)) ; 不采用平均阻尼 (newline) (newline) (newline) (display (fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2.0)) ; 采用平均阻尼 (exit) ``` 运行输出结果如下： ```scheme 2.0 9.965784284662087 3.004472209841214 6.279195757507157 3.759850702401539 5.215843784925895 4.182207192401397 4.8277650983445906 4.387593384662677 4.671250085763899 4.481403616895052 4.6053657460929 4.5230849678718865 4.577114682047341 4.541382480151454 4.564903245230833 4.549372679303342 4.559606491913287 4.552853875788271 4.557305529748263 4.554369064436181 4.556305311532999 4.555028263573554 4.555870396702851 4.555315001192079 4.5556812635433275 4.555439715736846 4.555599009998291 4.555493957531389 4.555563237292884 4.555517548417651 4.555547679306398 4.555527808516254 4.555540912917957 4.555532270803653 2.0 5.9828921423310435 4.922168721308343 4.628224318195455 4.568346513136242 4.5577305909237005 4.555909809045131 4.555599411610624 4.5555465521473675 4.555537551999825 ``` 可以看出采取平均阻尼计算步数少了很多，猜测过程从两边振荡变成一侧逼近。原理还不太理解。 ### 练习1.37 无穷连分式 $$ \frac{N_1} {D_1+\frac{N_2} {D_2+\frac{N_3} {\cdots} } }$$ 在给定数目的项之后截断为k项有限连分式 $$\frac{N_1} {D_1+\frac{N_2} {\cdots+\frac{N_k} {D_k} } }$$ a) 假定n和d都是只有一个参数（项的下标i）的过程，他们分别返回连分式的项$$N_i$$和$$D_i$$。定义一个过程cont-frac,使得对(cont-frac n d k)的求值计算出k项有限连分式的值。通过如下调用检查你的过程对于顺序的k值是否逼近1/ψ（其中ψ为黄金分割率）： ```scheme (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k) ``` b) 分别写出cont-frac的递归版本和迭代版本 ### 解答 ```scheme ; (define (cont-frac n d k) ; 递归版本 ; (define (iter-frac n d x) ; (if (= k x) ; (/ (n x) (d x)) ; (/ (n x) ; (+ (d x) ; (iter-frac n d (+ x 1)))))) ; (iter-frac n d 1)) (define (cont-frac n d k) ; 迭代版本 (define (iter-frac n d counter x) (if (= 0 x) counter (iter-frac n d (/ (n x) (+ (d x) counter)) (- x 1)))) (iter-frac n d (/ (n k) (d k)) (- k 1))) (define (test-cont-frac x) (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) x)) (display (test-cont-frac 1)) (newline) (display (test-cont-frac 5)) (newline) (display (test-cont-frac 10)) (exit) ``` ### 练习1.38 e-2的一个连分式展开，其中e是自然对数的底。在这一分式中，$$N_i$$都是1，$$D_i$$依次为1,2,1,1,4,1,1,6,1,1,8,...。写出一个程序，其中使用你在练习1.37中所做的cont-frac过程，并用它求e的近似值。 ### 解答 1,2,1,1,4,1,1,6,1,1,8,...这一序列规律是序号除以3余2的数字为偶数，其他数字都为1，只需要修改1.37中一部分代码即可。 ```scheme (define (di i) (if (= 2 (remainder i 3)) (* (/ (+ i 1) 3) 2) 1)) (define (test-cont-frac x) (+ 2 (cont-frac (lambda (i) 1.0) di x))) ``` 做练习1.38的过程中发现我原先在1.37中写错了迭代版代码。由于1.37中$$D_i$$总是1，没有暴露这个问题。这个错误是把第k-1项对应到第k项造成的。 ```scheme ; 这是错误的原代码 (define (cont-frac n d k) ; 迭代版本 (define (iter-frac n d counter x) (if (= 1 x) counter (iter-frac n d (/ (n x) (+ (d x) counter)) (- x 1)))) (iter-frac n d (/ (n k) (d k)) k)) ```
