Posted on 2007-05-11 10:04
dennis 閱讀(776)
評論(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))