練習問題1.14

1.2.2 節の count-change 手続きによって 11 セントに対する両替のやり方を求める際に生成されるプロセスを図示する木を描け。両替する金額の増加に対して、このプロセスが使う空間とステップ数はどのような増加オーダーになるか。

(define (count-change amount) (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
	((or (< amount 0) (= kinds-of-coins 0)) 0)
	(else #?=(+ (cc amount
		     (- kinds-of-coins 1)) ;まだ試してない中で１番大きい大きいコインを両替したパターン数
		 (cc (- amount
			(first-denomination
			 kinds-of-coins)) ; のこりのパターン
		     kinds-of-coins )))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
	((= kinds-of-coins 2) 5)
	((= kinds-of-coins 3) 10)
	((= kinds-of-coins 4) 25)
	((= kinds-of-coins 5) 50)))

(count-change 11)

図を書く

省略

増加オーダー

n / 50 * n / 25 * n / 10 * n / 5 * n (全部割り算切り上げ)

なので

O(n^5)

練習問題 1.15: (ラジアンで指定される) 角度の正弦は、x が十分

に小さいとき sin x ≈ x の近似式によって計算できる。また、次の
三角法の恒等式によって、sin の引数の大きさを小さくできる。

式(1)

sin x = 3 sin \frac{x}{3} - 4 sin^3 \frac{x}{3}

(この練習問題では、角が “十分に小さい” とはその大きさが 0.1 ラ
ジアン以下であることとする)

(sine 12.15) を評価する際に、手続き p は何回適用されるか。

(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      #?=(p (sine (/ angle 3.0)))))

(sine 12.5)
;; 5回
;; #?="./1.15.scm":7:(p (sine (/ angle 3.0)))
;; #?="./1.15.scm":7:(p (sine (/ angle 3.0)))
;; #?="./1.15.scm":7:(p (sine (/ angle 3.0)))
;; #?="./1.15.scm":7:(p (sine (/ angle 3.0)))
;; #?="./1.15.scm":7:(p (sine (/ angle 3.0)))
;; #?-    0.153776521096694
;; #?-    0.4467840153484446
;; #?-    0.9836111719853284
;; #?-    -0.8557060643295382
;; #?-    -0.060813768577286265

(sine a) が評価される際に sine 手続きによって生成されるプロセスのの増加オーダー

p(x) = 3x - 4x^3

なので、sine の引数はは毎回1/3になっていく。
増加オーダーは

O(\log_{3} a)

練習問題 1.16

反復プロセスでfast-ext(b^n)を求める

(最適化された)末尾再帰は、再帰手続きだけど、反復プロセス。
なので、元のfast-extを末尾再帰で実装すればよい。

末尾再帰とは：
最終的な結果は最後の読み出しがしてくれて、それ以前の手続きは最終呼び出しを待たなくていいもの。再帰の後に、それ以前の手続きのローカル変数を保持しなくていいもの。

;; a: いままでのをかけたやつ。答えになるやつ
;; b: 現時点でのn^?の値 ?の値は保持してない
(define (fast-ext a b n)
  (cond ((= n 0) a)
	((even? n) (fast-ext a (* b b) (/ n 2)) )  ;;奇数
	(else (fast-ext (* a b) b (- n 1)) )
	))

;; 2 ^ 3
(fast-ext 1 2 3) ;8
(fast-ext 1 2 10) ;1024

これだけ見ても？？ってなる気がするので、
何をしているかというと、こんな感じのイメージ

nを2進数にする
nが0ならaが答え
nの１番右のビットが立ってたら、 a *=b,
nを右に1つシフト(n >> 1)
b *= b
1.に戻る

練習問題1.17

1.16と同様以下の２つの演算を使って、対数ステップ数を取る掛け算を実装する
double: 整数を倍にする
halve: 偶数の整数を半分にする

(define (double x) (* x 2))
(define (halve x) (/ x 2))

(double 4) ;8
(halve 14) ;7

(define (*-org a b)
  (*-iter 0 a b))

(define (*-iter a b n)
  ;(print "*-iter: " a " " b " " n)
  (cond ((= n 0) a)
	((even? n) (*-iter a (double b) (halve n)))
	(else (*-iter (+ a b) b (- n 1)))
	))

(*-org 3 4) ;12
(*-org 12 35) ; 420

練習問題1.18

練習問題 1.16と練習問題 1.17の結果を使って、足し算、double、halve によって、かけ算を対数的ステップ数で実行する反復的プロセスを生成する手続きを考えよ。

多分1.17を普通に再帰的に書いても良かったのかな・・・。1.18で既に末尾再帰で書いたので1.17に同じ。