SICP学习笔记05 vvipi 发表于2018年11月10日,阅读：2167 ### 练习1.16 课本1.24给出了只需要log（n）步求$$b^n$$的过程的递归版本。定义一个过程，使其能够产生一个按照迭代方式的求幂计算过程。（提示：请利用$$(b^(n/2))^2 = (b^2)^(n/2)$$，除了指数n和基数b外，还应维持一个状态变量a，并定义好状态变换，使得从一个状态转到另一状态时乘积$$a*b^n$$不变。在计算过程开始时令a取值1，并用计算过程结束时a的值作为回答。 ### 解答 ```scheme (define (iter-expt b n) (define (f a b n) (if (= n 0) a (if (even? n) (f a (square b) (/ n 2)) (f (* a b) b (- n 1))))) (f 1 b n)) (define (even? n) (= (remainder n 2) 0)) (define (square x) (* x x)) (display (iter-expt 2 10)) (exit) ``` ### 理解 由于提示很详细，不难形成思路。当指数n为偶数，则将其减半，同时将b平方，a保持不变，则 ```math a*b^n = a*(b^2)^(n/2) ``` 当指数n为奇数，则将其减一变为偶数，保持不变，a变为a*b，则 ```math a*b^n = a*b*b^(n-1) ``` 保持不变.如此反复直到n=0,此时$$a*b^n$$ 变成了$$a*b^0$$, 而a的值已经从1变成$$b^n$$。 ### 练习1.17 ```scheme (define (iter-mult b n) (define (f a b n) (if (= n 0) a (if (even? n) (f a (double b) (halve n)) (f (+ a b) b (- n 1))))) (f 0 b n)) (define (double n) (* n 2)) (define (halve n) (/ n 2)) ``` 1.17的思路和1.16一样，只是把乘变成加。
