莊周夢蝶

          生活、程序、未來
             :: 首頁 ::  ::  :: 聚合  :: 管理

          sicp 習題1.31,1.32,1.33解答

          Posted on 2007-05-14 15:10 dennis 閱讀(701) 評論(0)  編輯  收藏
              此題與1.32、1.33是一個系列題,沒什么難度,只不過把sum的加改成乘就可以了,遞歸與迭代版本相應修改即可:
          ;(define (product term a next b)
          ;  (
          if (> a b)
          ;      
          1
          ;      (
          * (term a) (product term (next a) next b))))
          (define (product
          -iter term a next b result)
            (
          if (> a b)
                result
                (product
          -iter term (next a)  next b (* result (term a)))))
             分號注釋的是遞歸版本。利用product過程生成一個計算pi的過程,也是很簡單,通過觀察公式的規律即可得出:
          (define (product term a next b)
            (product
          -iter term a next b 1))
          (define (inc x) (
          + x 2))
          (define (pi
          -term n)(/ (* (- n 1) (+ n 1)) (* n n)))
          (define (product
          -pi a b)
             (product pi
          -term a inc b))
          測試一下:

          > (* 4 (product-pi 3 1000))
          3.1431638424191978569077933

          再來看習題1.32,如果說sum和product過程是一定程度的抽象,將對累積項和下一項的處理抽象為過程作為參數提取出來,那么這個題目要求將累積的操作也作為參數提取出來,是更高層次的抽象,同樣也難不倒我們:
          (define (accumulate combiner null-value term a next b)
            (
          if (> a b)
                null
          -value
                (combiner (term a) (accumulate combiner null
          -value term (next a) next b))))

          OK,其中combiner是進行累積的操作,而null-value值基本值。現在改寫sum和product過程,對于sum過程來說,累積的操作就是加法,而基本值當然是0了:
          (define (sum term a next b)
            (accumulate 
          + 0 term a next b))

          而對于product,累積操作是乘法,而基本值是1,因此:
          (define (product term a next b)
            (accumulate 
          * 1 term a next b))

          測試一下過去寫的那些測試程序,比如生成pi的過程,可以驗證一切正常!

          上面的accumulate過程是遞歸版本,對應的迭代版本也很容易改寫了:
          (define (accumulate-iter combiner term a next b result)
            (
          if (> a b)
                result
                (accumulate
          -iter combiner term (next a) next b (combiner result (term a)))))
          (define (accumulate  combiner null
          -value term a next b)
            (accumulate
          -iter combiner term a next b null-value))

          再看習題1.33,在accumulate的基礎上多增加一個filter的參數(也是一個過程,用于判斷項是否符合要求),在accumulate的基礎上稍微修改下,在每次累積之前進行判斷即可:

          (define (filtered-accumulate combiner null-value term a next b filter)
            (cond ((
          > a b) null-value)
                  ((filter a) (combiner (term a) (filtered
          -accumulate combiner null-value term (next a) next b filter))) 
                  (
          else (filtered-accumulate combiner null-value term (next a) next b filter))))

          比如,求a到b中的所有素數之和的過程可以寫為(利用以前寫的prime?過程來判斷素數):
          (define (sum-primes a b)
            (filtered
          -accumulate + 0 identity a inc b prime?))

          測試一下:
          > (sum-primes 2 4)
          5
          > (sum-primes 2 7)
          17
          > (sum-primes 2 11)
          28
          > (sum-primes 2 100)
          1060


          只有注冊用戶登錄后才能發表評論。


          網站導航:
           
          主站蜘蛛池模板: 丹巴县| 玉田县| 繁峙县| 沙坪坝区| 长治市| 图木舒克市| 河北省| 石阡县| 满洲里市| 安泽县| 南安市| 富民县| 望都县| 南丰县| 揭阳市| 清涧县| 镇沅| 平罗县| 桃园县| 陆良县| 虞城县| 永顺县| 寿宁县| 克山县| 开原市| 台北市| 鱼台县| 红安县| 常州市| 彭水| 谷城县| 淮阳县| 黑龙江省| 田东县| 平陆县| 桑植县| 咸宁市| 阿克苏市| 会昌县| 浦县| 萨迦县|