Posted on 2007-05-11 08:51
dennis 阅读(861)
评论(0) 编辑 收藏 所属分类:
计算机科学与基础
此题充分展示了如何将递归转化为迭代的技巧：定义一个不变量，要求它在迭代状态之间保持不变！题目如下：
写一个过程求平方，并且只用对数个步骤。
解答：
考虑一个附加状态a，如何保持ab**n(b**n表示b的n次方）在状态改变间保持不变.
1)当n是偶数：
a(b
2)
n/2 = ab
n
b
n = (b
n/2)
2 = (b
2)
n/2
在这个过程中回溯状态的迁移：
a ← a
b ← b2
n ← n/2
2)当n是奇数：
(ab)b
(n-1) = ab
n
回溯状态的变迁：
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))