sicp习题 1.17 1.18解答

    这两道题目没什么难度了，幂运算是连续乘，乘法运算就是连续加，改造一下书中的例子和习题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))

dennis 2007-05-11 10:04 发表评论