Posted on 2007-05-11 10:04
dennis 阅读(789)
评论(0) 编辑 收藏 所属分类:
计算机科学与基础
这两道题目没什么难度了，幂运算是连续乘，乘法运算就是连续加，改造一下书中的例子和习题1.16就可以了，还是分析一下。
习题1.17:
已知两个过程,double过程可以求出一个整数的两倍，而halve过程将一个偶数除以2;要求写出一个过程，只用
对数个步骤计算两个整数的乘积。
解答:
计算a*b，考虑两种情况：
1)当b是偶数时：
a*b=2(a*(b/2))
2)当b是奇数时：
a*b=a*(b-1)+a
通过递归直接得到lisp过程，很好理解了，预先定义了两个已知过程double和halve：
(define (double x) (* x 2))
(define (halve x) (/ x 2))
(define (multiplied a b)
(cond ((or (= b 0) (= a 0)) 0)
((even? b) (double (multiplied a (halve b))))
(else (+ a (multiplied a (- b 1))))))
习题1.18:将1.17的递归过程改写为迭代过程，保持对数个步骤
分析：递归转化为迭代，关键是要抓住状态迁移间的不变量，我们给它一个状态变量c，问题归结为如何保持c+a*b不变。
1)当b是偶数：
c+a*b=c+(2a)*(b/2))
在此过程中的状态变换：
c <--- c
a <--- 2a
b <--- b/2
2)当b是奇数:
c+a*b=(c+a)+a*(b-1)
回溯此状态转换：
c <--- (a+c)
a <--- a
b <--- (b-1)
由此可以得到该过程的迭代版本，两个已知过程与上同：
(define (fast-multiplied-iter a b c)
(cond ((= a 0) 0)
((= b 0) c)
((even? b) (fast-multiplied-iter (double a) (halve b) c))
(else
(fast-multiplied-iter a (- b 1) (+ a c)))))
(define (fast-multiplied a b) (fast-multiplied-iter a b 0))