`
阿尔萨斯
  • 浏览: 4107341 次
社区版块
存档分类
最新评论

SICP 习题 (1.18) 解题总结

 
阅读更多

SICP 习题 1.18是习题1.17的扩展,要求我们将1.17题中的对数步数求加法的过程修改成迭代方式。同时,习题1.18习题也是对习题1.16的强调,习题1.16是通过迭代方法求幂,这里是通过迭代方法求加法。


所以我们需要回过头去看习题1.16和1.17。


习题1.16是将以下函数进行修改:

(define (fast-expt b n)
  (cond ((= n 0) 1)
	((even? n) (square (fast-expt b (/ n 2))))
	(else (* b (fast-expt b (- n 1))))))

变成了这样:

(define (fast-expt-iter root cur-result n)
  (cond ((= n 0) 1)
	((= n 1) (* root cur-result))
	((even? n) (fast-expt-iter (square root) cur-result (/ n 2)))
	(else (fast-expt-iter root (* root cur-result)  (- n 1)))))


而习题1.17的结果如下:

(define (fast-mul a b)
  (cond ((= b 0) 0)
	((even? b) (double (fast-mul a (halve b ))))
	(else (+ a (fast-mul a (- b 1))))))


我们发现习题1.16修改前的代码和习题1.17的结果几乎是一样的。

所以,我们可以完全按照相同的思路完成迭代方法求加法的代码:


(define (fast-mul-iter a cur-result b)
  (cond ((= b 0) 0)
	((= b 1) (+ a cur-result))
	((even? b) (fast-mul-iter (double a) cur-result (halve b)))
	(else (fast-mul-iter a (+ a cur-result)  (- b 1)))))


所以说习题1.18没有什么难度,前提是你能够独立完成习题1.16和习题1.17 。


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics