Posted on 2007-05-11 10:04
dennis 閱讀(780)
評論(0) 編輯 收藏 所屬分類:
計算機科學(xué)與基礎(chǔ)
這兩道題目沒什么難度了，冪運算是連續(xù)乘，乘法運算就是連續(xù)加，改造一下書中的例子和習(xí)題1.16就可以了，還是分析一下。
習(xí)題1.17:
已知兩個過程,double過程可以求出一個整數(shù)的兩倍，而halve過程將一個偶數(shù)除以2;要求寫出一個過程，只用
對數(shù)個步驟計算兩個整數(shù)的乘積。
解答:
計算a*b，考慮兩種情況：
1)當(dāng)b是偶數(shù)時：
a*b=2(a*(b/2))
2)當(dāng)b是奇數(shù)時：
a*b=a*(b-1)+a
通過遞歸直接得到lisp過程，很好理解了，預(yù)先定義了兩個已知過程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))))))
習(xí)題1.18:將1.17的遞歸過程改寫為迭代過程，保持對數(shù)個步驟
分析：遞歸轉(zhuǎn)化為迭代，關(guān)鍵是要抓住狀態(tài)遷移間的不變量，我們給它一個狀態(tài)變量c，問題歸結(jié)為如何保持c+a*b不變。
1)當(dāng)b是偶數(shù)：
c+a*b=c+(2a)*(b/2))
在此過程中的狀態(tài)變換：
c <--- c
a <--- 2a
b <--- b/2
2)當(dāng)b是奇數(shù):
c+a*b=(c+a)+a*(b-1)
回溯此狀態(tài)轉(zhuǎn)換：
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))