sicp 1.16解答

    此题充分展示了如何将递归转化为迭代的技巧：定义一个不变量，要求它在迭代状态之间保持不变！题目如下：
写一个过程求平方，并且只用对数个步骤。

解答：
考虑一个附加状态a，如何保持ab**n(b**n表示b的n次方）在状态改变间保持不变.
1)当n是偶数：
a(b²)^n/2 = abⁿ
bⁿ = (b^n/2)² = (b²)^n/2
在这个过程中回溯状态的迁移：

<!---->

    a ← a

    b ← b2

    n ← n/2

2)当n是奇数：
(ab)b^(n-1) = abⁿ
回溯状态的变迁：

<!---->

    a ← a * b

    b ← b

    n ← n-1

就此可以写出lisp过程了:

<!---->(define (even? n) (= (remainder n 2) 0))
(define (square n) (* n n))
(define (fast-expr b n)
  (define (iter a b n)
    (cond ((= n 0) a)
          ((even? n) (iter a (square b) (/ n 2)))
          (else (iter (* a b) b (- n 1)))))
  (iter 1 b n))

这道题目一开始我的解答完全错了！-_-，我理解错了题意，一直将指数对半折，这样的步骤是n/2步而不是对数步骤，阶仍然是(theta)(n)：

<!---->(define (fast-expt-iter b product counter)
  (cond ((= counter 0) product)
    ((even? counter) (fast-expt-iter b (* (square b) product) (* 2 (- (/ counter 2) 1)))) 
    
    (else
      (* b (fast-expt-iter b product (- counter 1)))
  )))
(define (fast-exptt b n)
  (fast-expt-iter b 1 n))

dennis 2007-05-11 08:51 发表评论