莊周夢蝶

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

          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的過程,也是很簡單,通過觀察公式的規(guī)律即可得出:
          (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值基本值。現(xiàn)在改寫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


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


          網站導航:
           
          主站蜘蛛池模板: 无为县| 宜宾县| 大田县| 阳朔县| 鹰潭市| 舟曲县| 安徽省| 武鸣县| 宁南县| 恭城| 四子王旗| 定远县| 黄梅县| 虞城县| 永胜县| 遂宁市| 广东省| 平和县| 永和县| 昌江| 陆川县| 枣庄市| 门头沟区| 绿春县| 宜春市| 府谷县| 舒城县| 张掖市| 沛县| 金阳县| 廊坊市| 蓝山县| 博客| 乐平市| 镇安县| 酉阳| 曲沃县| 抚远县| 慈溪市| 邹城市| 田阳县|