Posted on 2007-05-11 08:51
dennis 閱讀(888)
評論(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))