Exercise1.1
gosh> 10
10
gosh> (+ 5 4 3)
12
gosh> (- 9 1)
8
gosh> (/ 6 2)
3
gosh> (+ (* 2 4) (- 4 6))
6
gosh> (define a 3)
a
gosh> (define b (+ a 1))
b
gosh> (+ a b (* a b))
19
gosh> (= a b)
#f
gosh> (if (and (> b a) (< b (* a b)))
..... b
..... a)
4
gosh> (cond ((= a 4) 6)
..... ((= b 4) (+ 6 7 a))
..... (else 25))
16
gosh> (+ 2 (if (> b a) b a))
6
gosh> (* (cond ((> a b) a)
..... ((< a b) b)
..... (else -1))
..... (+ a 1))
16
Exercise1.2
gosh> (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
..... (* 3 (- 6 2) (- 2 7)))
-0.24666666666666667
by iwk
Exercise1.3
(define (func a b c)
(if (>= a b)
(+ (* a a)
(if (>= b c)
(* b b)
(* c c)))
(+ (* b b)
(if (>= a c)
(* a a)
(* c c)))))
実行例
SC> (func 1 2 3)
13
SC> (func 2 2 3)
13
SC> (func 2 2 2)
8
別解(再帰呼び出しによる解答)
(define (sum-square-largest x y z)
(cond ((and (< x y) (< x z))
(+ (* y y) (* z z)))
(else (sum-square-largest y z x))))
Exercise1.4
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
;; b>0ならば，(+ a b)が評価され，そうでないなら(- a b)が評価される．
;; つまり，この手続きはaと，bの絶対値を足した値を返す．
;; このように基本演算子を，あたかもデータであるかのように返すことが可能なのである．
実行例
SC> (a-plus-abs-b 1 -2)
3
SC> (a-plus-abs-b 1 2)
3
by Alyssa
Exercise1.5
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
;; testは，自らが定義した手続きであるので，作用的順序(applicative order)の場合，test手続きに引数x,yを作用(apply)させる前に，引数x,yを評価する．
;; ゆえに，(test 0 (p))の評価において，(p)はそれ自身(p)と定義されているので，引数(p)の評価が終わらず，無限ループとなる．
;; 一方，正規順序(normal order)の場合，引数の評価はその引数の値が必要となるまで遅延(delay)される．
;; 今の場合，手続きtestの本体はif文であり，まず述語式{(= x 0)}の評価に入り，今xは0であるので，(= 0 0)となりこれは真であるので，
;; 代替部{y}を評価することなく，そのまま帰結部{0}を返す．よって無限ループには陥らない．
;; （参考）
;; この様に書くと，正規順序の方が優れているように見えますが，計算効率などを考え普通の解釈系は作用的順序です．
;; 正規順序の解釈系の実装については，4.2で詳しくやります．
by Alyssa
Exercise1.6
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
;; new-ifはあくまで手続きであるので，引数を全て評価してからnew-if本体に作用させる．
;; ゆえに，引数else-clause(ifでいう代替部)にあたる(sqrt-iter ..)の部分の評価でさらにその中のsqrt-iterを評価し，と無限ループに陥る．
;; （参考）
;; なぜ普通のifではこの様な無限ループに陥らないかというと，ifは手続きではなくあくまで特殊形式であり，
;; まず述語部を評価して，その真偽に応じて，帰結部か代替部を初めて評価するので，(good-enough? ..)の部分が真になった時点で，代替部の(sqrt-iter ..)は評価されないのです．
;; ですので例えば，(if (= 0 0) 1 (/ 1 0))なども（一応）エラーが出ずに通ります．
by Alyssa
Exercise1.7
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-iter guess next-guess x)
(if (good-enough? guess next-guess)
next-guess
(sqrt-iter next-guess (improve next-guess x) x)))
(define (good-enough? guess next-guess)
(< (abs (/ (- next-guess guess) next-guess)) 0.001))
(define (sqrt x)
(sqrt-iter 1.0 (improve 1.0 x) x))
;; 変更する前のsqrtでは，小さい値の場合誤差が酷く，大きい値の場合永久に結果が出ない場合があります．
;; この原因は，good-enough?が求めるべき値との絶対的な誤差で判断しているからです．
;; ですので，重要な変更点はgood-enough?です．
;; 推測値が十分に変化しなくなった相対的な誤差で判断させます．
;; こちらは有効数字的な考え方ですので，酷く結果がずれることも，永久に値が出ないこともありません．
実行例
;; 改良前（本文中に出てくるsqrt）
SC> (sqrt .0002)
0.0333528160928043
;; 誤差が酷い
SC> (sqrt 20000000000000000000000000000000000)
;; 停止しない
;; 改良後（上のソースのsqrt）
SC> (sqrt .0002)
0.0141421356237384
SC> (sqrt 20000000000000000000000000000000000)
1.41421379705111e+17
;; ともにちゃんとした値がでる
by Alyssa
Exercise1.8
(define (curt-iter guess x)
(if (good-enough? guess x)
guess
(curt-iter (improve guess x) x)))
(define (improve guess x)
(/ (+ (/ x guess guess) (* 2 guess)) 3))
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) .001))
(define (cube x) (* x x x))
(define (curt x) (curt-iter 1.0 x)
実行例
SC> (curt 1.0)
1.0
SC> (curt 2.0)
1.25993349344998
SC> (curt 8.0)
2.0000049116755
;; ただし，これもEx1.7と同じ理由で，小さい値や大きい値には対応できません．
by Alyssa
Exercise1.9
(define (inc a) (+ a 1))
(define (dec a) (- a 1))
(define (+_1 a b)
(if (= a 0)
b
(inc (+_1 (dec a) b))))
(define (+_2 a b)
(if (= a 0)
b
(+_2 (dec a) (inc b))))
;; (注:2つの+を区別するために問題文とは名前を変えています．)
;; 以下プロセス
(+_1 4 5)
(inc (+_1 (dec 4) 5))
(inc (+_1 3 5))
(inc (inc (+_1 (dec 3) 5)))
(inc (inc (+_1 2 5)))
(inc (inc (inc (+_1 (dec 2) 5))))
(inc (inc (inc (+_1 1 5))))
(inc (inc (inc (inc (+_1 (dec 1) 5)))))
(inc (inc (inc (inc (+_1 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
これは再帰的
(+_2 4 5)
(+_2 (dec 4) (inc 5))
(+_2 3 6)
(+_2 (dec 3) (inc 6))
(+_2 2 7)
(+_2 (dec 2) (inc 7))
(+_2 1 8)
(+_2 (dec 1) (inc 8))
(+_2 0 9)
9
これは反復的
by Alyssa
Exercise1.10
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1) (A x (- y 1))))))
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
実行例
SC> (A 1 10)
1024
SC> (A 2 4)
65536
SC> (A 3 3)
65536
また，f(n)=2*n,f(0)=0,f(1)=2より，
f(n) = 2n
同様に，g(n)=2*g(n-1),g(1)=2より，
g(n) = 2^n （これはn=0の時も成り立つ）
最後に，h(n) = 2^h(n-1),h(1)=2より，
h(n) = (n≠0) 2^(2^(2^...^(2^2))...)) （2がn個表れる）
(n=0) 0
by Alyssa
Exercise1.11
;; 再帰
(define (f-r n)
(if (<= n 3)
n
(+ (f-r (- n 1)) (* 2 (f-r (- n 2))) (* 3 (f-r (- n 3))))))
;; 反復
(define (f-i n)
(define (iter a b c count)
(cond ((<= n 2) n)
((= count n) a)
(else (iter (+ a (* 2 b) (* 3 c)) a b (+ count 1)))))
(iter 3 2 1 3))
実行例
SC> (f-r 2)
2
SC> (f-r 15)
124905
SC> (f-i 2)
2
SC> (f-i 15)
124905
by Alyssa
Exercise1.12
(define (pascal n k)
(cond ((= k 0) 1)
((= k n) 1)
(else (+ (pascal (- n 1) (- k 1)) (pascal (- n 1) k)))))
;; ただし上のn,kは，上からn(n>=0)番目の段の左からk(k>=0)個目の要素としています．
実行例
SC> (pascal 5 2)
10
SC> (pascal 10 8)
45
by Alyssa
Exercise1.13
schemeとは直接関係ありませんし書くのも面倒なのでアイディアだけ．
まず，言われた通り，帰納法なりなんなりでFib(n)=(φ^n - ψ^n)/√5を示し，
ここでn>=0において，0<ψ<1より，(ψ^n)/√5 < 1/√5 < 1/√4 = 0.5であるので，
これらよりFib(n)は(φ^n)/√5にもっとも近い整数といえます．
by Alyssa
Exercise1.14
(amount , kinds-of-coins)
(11 , 5) - ( -39 , 5) <- 0
|
(11 , 4) - ( -14 , 4) <- 0
|
(11 , 3) - ( 1 , 3) - ( -9 , 3) <- 0
| |
| ( 1 , 2) - ( -4 , 2) <- 0
| |
| ( 1 , 1) - ( 0 , 1 ) <- 1
| |
| ( 1 , 0) <- 0
|
(11 , 2) - ( 6 , 2) - ( 1 , 2 ) - ( -4 , 2) <- 0
| | |
| | ( 1 , 1 ) - ( 0 , 1 ) <- 1
| | |
| | ( 1 , 0 ) <- 0
| |
| ( 6 , 1) - ( 5 , 1 ) - ( 4 , 1 ) - ( 3 , 1) - ( 2 , 1) - ( 1 , 1) - ( 0 , 1) <- 1
| | | | | | |
| | | | | | ( 1 , 0) <- 0
| | | | | |
| | | | | ( 2 , 0) <- 0
| | | | |
| | | | ( 3 , 0) <- 0
| | | |
| | | ( 4 , 0 ) <- 0
| | |
| | ( 5 , 0 ) <- 0
| |
| ( 6 , 0) <- 0
|
(11 , 1) - (10 , 1) - ( 9 , 1 ) - ( 8 , 1 ) - ( 7 , 1) - ( 6 , 1) - ........ - ( 1 , 1) - ( 0 , 1) <- 1
| | | | | | |
| | | | | | ( 1 , 0) <- 0
| | | | | ( 6 , 0) <- 0
| | | | |
| | | | ( 7 , 0) <- 0
| | | |
| | | ( 8 , 0) <- 0
| | |
| | ( 9 , 0 ) <- 0
| |
| (10 , 0) <- 0
|
(11 , 0) <- 0
増加の程度
スペース Θ(n) , ステップ数 Θ(a^n)
by iriya
Exercise1.15
(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)))))
;; (a)
;; angleの絶対値が0.1より大きい時にpは呼ばれるので，
;; angel:12.15 > 4.05 > 1.35 > 0.45 > 0.15 > 0.05となることから
;; pは5回呼び出される．
;; (b)
;; 手続きpは，xにたいしてステップもスペースももちろんθ(1)である．
;; よって手続きsineは，pを呼び出す数に比例してステップが増え，スペースも同様である．
;; 今，ある(0.1より大きい)angleについて，その3倍の3*angleの(sine (* 3 angle))を考えると，
;; これは(p (sine angle))を呼び出すので，(sine angle)に対して一つステップもスペースも増える．
;; つまり，sineのオーダーをf(n)と表すなら，f(3n) = f(n) + 1が成り立つのである．
;; これを満たすfは，log_{3}(n)である．
;; よって，sineはステップもスペースもθ(log_{3}(n))である．
;; (補足)
;; ようは，angleが1/3ずつになっていくのでθ(log_{3}(n))なのです．
by Alyssa
Exercise1.16
;; http://ja.wikipedia.org/wiki/%E5%86%AA%E4%B9%97
;; 効率的演算法 の最初の方法から着想
(define (square x) (* x x))
(define (even? n)
(= (remainder n 2) 0))
(define (fast-expt-iter a b n)
(cond ((= n 0) a)
((even? n) (fast-expt-iter a (square b) (/ n 2)))
(else (fast-expt-iter (* a b) b (- n 1)))))
(define (fast-expt b n)
(fast-expt-iter 1 b n))
Exercise1.17
(define (halve x) (/ x 2))
(define (double x) (* x 2))
(define (even? n)
(= (remainder n 2) 0))
(define (x a b)
(cond ((= b 0) 0)
((even? b) (double (x a (halve b))))
(else (+ a (x a (- b 1))))))
gosh> (x 123 4567890987654321)
561850591481481483
gosh> (* 123 4567890987654321)
561850591481481483
by kacchi
Exercise1.18
Exercise1.16 と同じ形なので、そのままあてはめた。
(define (double x) (+ x x))
(define (x a b)
(x-iter 0 a b))
(define (x-iter product a b)
(cond ((= b 0) product)
((even? b) (x-iter product (double a) (/ b 2)))
(else (x-iter (+ a product) a (- b 1)))))
by kacchi
Exercise1.19
(define (mfib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(mfib-iter a
b
(+ (* p p) (* q q))
(+ (* q q) (* 2 p q))
(/ count 2)))
(else (mfib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
(define (mfib n)
(mfib-iter 1 0 0 1 n))
by iwk
最終更新：2008年02月29日 17:20
