Serendip

Web Studio

問題5.4

a. 再帰的べき乗

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

再帰的べき乗を計算する計算機のデータパス図

再帰的べき乗を計算する計算機の制御器

(controller
    (assing b (op read))
    (assing n (op read))
    (assign continue (label expt-done))
  expt-loop
    (test (op =) (reg n) (const 0))
    (branch (label base-case))
    (save continue)
    (save n)
    (assign n (op -) (reg n) (const 1))
    (assign continue (label after-expt))
    (goto (label expt-loop))
  after-expt
    (restore n)
    (restore continue)
    (assign val (op *) (reg b) (reg val))
    (goto (reg continue))
  base-case
    (assign val (const 1))
    (goto (reg continue))
  expt-done)

b. 反復的べき乗

(define (expt b n)
  (define (expt-iter counter product)
    (if (= counter 0)
        product
        (expt-iter (- counter 1) (* b product))))
  (expt-iter n 1))

反復的べき乗を計算する計算機のデータパス図

反復的べき乗を計算する計算機の制御器

(controller
    (assign b (op read))
    (assign n (op read))
    (assign counter (reg n))
    (assign product (const 1))
  expt-loop
    (test (op =) (reg counter) (const 0))
    (branch (label expt-done))
    (assign counter (op -) (reg counter) (const 1))
    (assign product (op *) (reg b) (reg product))
    (goto (label expt-loop))
  expt-done)

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る