1章の練習問題の解答 by kacchi
未解答の問題番号
Exercise1-14
Exercise1-19
Exercise1-24
Exercise1-25
Exercise1-26
Exercise1-28
Exercise1-40
Exercise1-45
Exercise1-46
Exercise1-1
省略
Exercise1-2
gosh> (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
(* 3 (- 6 2) (- 2 7)))
-37/150
Exercise1-3
if
(define (f a b c)
(if (>= a b)
(if (>= b c)
(+ (square a) (square b))
(+ (square a) (square c)))
(if (>= a c)
(+ (square b) (square a))
(+ (square b) (square c)))))
cond
(define (f a b c)
(cond ((and (>= a b) (>= b c))
(+ (square a) (square b)))
((and (>= a b) (>= c b))
(+ (square a) (square c)))
((and (>= b a) (>= a c))
(+ (square b) (square a)))
((and (>= b a) (>= c a))
(+ (square b) (square c)))))
Exercise1-4
(define (a-plus-abs-b a b)
((if (> b 0) + -) a b))
(a-plus-abs-b 1 2) を評価してみる。
a-plus-abs-b の本体をとりだす。
((if (> b 0) + -) a b)
仮引数a,bをそれぞれ1,2で置き換える。
((if (> 2 0) + -) 1 2)
合成式である演算子(if (> 2 0) + -)の値をとりだすと基本演算子+が得られ、
(+ 1 2) に帰着する。
3
になる。
Exercise1-5
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
(test 0 (p))
作用的順序:
引数が評価され、0は0になる。(p)を評価すると(p)自身を呼ぶので、無限ループになる。
★手続きと引数はどちらが先に評価されるのか？
(R5RS 4.1.3 プロシージャ呼び出し
演算子と被演算子が評価され(その順序は規定されてない)、
結果として得られた手続きに結果として得られた引数が渡される。)
正規的順序:
testの本体を取り出す。
(if (= x 0) 0 y)
引数x,yを0,(p)で置き換える。
(if (= 0 0) 0 (p))
(= 0 0)は真を返すので0となり、(p)は評価されない。
Exercise1-6
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(new-if (= 2 3) 0 5)
;Value: 5
(new-if (= 1 1) 0 5)
;Value: 0
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(sqrt-iter 1.0 3) を評価してみる。
sqrt-iterの本体を取り出し、仮引数guessとxを1.0と3で取り替えられ、
(new-if (good-enough? 1.0 3)
1.0
(sqrt-iter (improve 1.0 3)
3))
となり、new-if が評価される。しかし、new-if は手続きなので、引数がすべ
て評価されることになる。つまり、good-enough? の値の真偽にかかわらず、
sqrt-iter が常に評価される。その結果、new-if に展開され、引数の評価が無
限に続くことになる。
---
MIT Scheme で(sqrt-iter 1.0 3)を評価した結果、
;Aborting!: maximum recursion depth exceeded
とともに異常終了した。
Gauche で(sqrt-iter 1.0 3)を評価した結果、スタックオーバーフロー。
Exercise1-7
・テストが失敗するケースがわからない。
・good-enough? の実装。
ある繰り返しの時点で、次の予測値を調べ、その変化率が非常に小さくなったら終る。
次の予測値は、(improve guess x) で得られる。
変化率は、(/ (- (improve guess x) guess) guess) で得られる。
(define (good-enough? guess x)
(< (abs (/ (- (improve guess x) guess) guess)) 0.001))
Exercise1-8
立方根をとるNewton法。SICP 1.1.7 の例と同じように考えた。
;; 立方根をとろうとする数 x と予測値 guess から出発する。予測値が目標に十分なら終わる。
;; そうでなければ、改善された予測値を使って手順を繰り返す。
(define (cube-root-iter guess x)
(if (good-enough? guess x)
guess
(cube-root-iter (improve guess x)
x)))
;; 予測値を改善する。
(define (improve guess x)
(/ (+ (/ x (square guess))
(* 2 guess))
3))
;; 予測値の3乗と立方根をとろうとする数の差が、許容値より小さい。
(define (good-enough? guess x)
(< (abs (- (cube guess) x)) 0.001))
;; 予測値の初期値を1として計算を始める。
(define (cube-root x)
(cube-root-iter 1.0 x))
;; 3乗と2乗
(define (cube x) (* x x x))
(define (square x) (* x x))
Exercise1-9
(define (+ a b)
(if (= a 0)
b
(inc (+ (dec a) b))))
(+ 4 5)
(inc (+ (dec 4) 5))
(inc (inc (+ (dec 3) 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
置き換えモデルは、膨張と収縮の形をとるので再帰的プロセス。
(define (+ a b)
(if (= a 0)
b
(+ (dec a) (inc b))))
(+ 4 5)
(+ (dec 4) (inc 5))
(+ (dec 3) (inc 6))
(+ (dec 2) (inc 7))
(+ (dec 1) (inc 8))
9
置き換えモデルは膨張と収縮の形をとらないので反復的プロセス。
Exercise1-10
Ackermann関数
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
(1)次の式の値は何か。
(A 1 10)
;Value: 1024
(A 2 4)
;Value: 65536
(A 3 3)
;Value: 65536
(2)
(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
と定義するとき、正の整数 n に対して、f,g,h が計算する関数の数学的定義を述べよ。
f: 2n を計算する関数。
g: 2^n を計算する関数。
h: ？
・(f 4)
(A 0 4)
(* 2 n) を返すので、2n を計算する関数。
・(g 4)
(A 1 4)
(A 0 (A 1 3))
(A 0 (A 0 (A 1 2)))
(A 0 (A 0 (A 0 (A 1 1))))
から、2^n を計算する関数。
・(h 1)
(A 2 1)
2
(A 2 1) は 2 を返す。
(h 2)
(A 2 2)
(A 1 (A 2 1))
4
(expt 2 2)
(h 3)
(A 2 3)
(A 1 (A 2 2))
(A 1 (A 1 (A 2 1)))
16
(expt 2 (expt 2 2))
(h 4)
(A 2 4)
(A 1 (A 2 3))
(A 1 (A 1 (A 2 2)))
(A 1 (A 1 (A 1 (A 2 1))))
65536
(expt 2 (expt 2 (expt 2 2)))
数学的にどう定義すればよいかは不明だった。
Exercise1-11
n < 3 に対して f(n) = n、 n > 3 に対して f(n) = f(n-1)+2f(n-2)+3f(n-3)
なる規則で定義する関数 f の、再帰的・反復的プロセスの方法で手続きを書け。
;; 再帰的
(define (f n)
(if (< n 3)
n
(+ (* 1 (f (- n 1)))
(* 2 (f (- n 2)))
(* 3 (f (- n 3))))))
;; 反復的
(define (f-iter a b c count)
(if (= count 0)
c
(f-iter (+ a (* 2 b) (* 3 c)) a b (- count 1))))
(define (f n)
(f-iter 2 1 0 n))
;; 出力結果
(f 0) ;0
(f 1) ;1
(f 2) ;2
(f 3) ;4
(f 4) ;11
(f 5) ;25
(f 6) ;59
(f 7) ;142
Exercise1-12
「パスカル三角形の要素を計算」の意味が不明だったので、
二項定理を用いて各行の要素の総和を求めることにした。
多分、解答になってない。
参考: http://www004.upp.so-net.ne.jp/s_honma/pascal/pascal.htm
nCk = n!/k!(n-k)!
(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* product counter) (+ counter 1))))
(iter 1 1))
(define (nCk n k)
(/ (factorial n) (* (factorial k) (factorial (- n k)))))
(define (pascal-iter k n)
(if (> k n)
0
(+ (nCk n k) (pascal-iter (+ k 1) n))))
(define (pascal n)
(pascal-iter 0 n))
(pascal 0) ;1
(pascal 1) ;2
(pascal 2) ;4
(pascal 3) ;8
(pascal 4) ;16
(pascal 5) ;32
(pascal 6) ;64
Exercise1-13
φ = (1 + (sqrt 5))/2 とし、
ψ = (1 - (sqrt 5))/2 とし、
fib(n) が (φ^n - ψ^n)/(sqrt 5) に最も近い整数になっていることだけを確認することにした。
sqrt の精度が低いので十分確認できなかった(Exercise1-7 に問題がある)。
;; 2乗
(define (square x) (* x x))
;; 平方根
(define (sqrt x)
(define (good-enough? guess x)
(< (abs (/ (- (improve guess x) guess) guess)) 0.001))
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess)))
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x)
x)))
(sqrt-iter 1.0 x))
;; べき乗
(define (power n k)
(if (= k 0)
1
(* n (power n (- k 1)))))
(define (test n)
(define psi (/ (- 1 (sqrt 5)) 2))
(define phi (/ (+ 1 (sqrt 5)) 2))
(/ (- (power phi n) (power psi n)) (sqrt 5)))
(test 10) ;Value: 55.29535579685757
(fib 10) ;55
(test 1) ;1
(fib 1) ;1
(test 2) ;1.0
(test 3) ;2.002267573696145
(fib 3) ;2
(test 4) ;3.00453514739229
(fib 4) ;3
(test 5) ;5.011343010371192
(fib 5) ;5
(test 6) ;8.022691162632853
(fib 6) ;8
(test 7) ;13.045397762596725
(fib 7) ;13
(test 8) ;21.086280968682264
(fib 8) ;21
(test 50) ;12974856168.405893
(fib 50) ;12586269025
(test 100) ;3.767763786556457e20
(fib 100) ;354224848179261915075
Exercise1-14
Exercise1-15
(a) p は、(> (abs angle) 0.1)を満たすとき呼ばれるので、
はじめに1回呼ばれ、angleを(/ angle 3.0)として(> (abs angle) 0.1)
を満たす限り呼ばれる。したがって、以下のとおり5回。
(/ 12.15 3.0) ;4.05
(/ 4.05 3.0) ;1.3499999999999999
(/ 1.3499999999999999 3.0) ;.44999999999999996
(/ .44999999999999996 3.0) ;.15
(/ .15 3.0) ;4.9999999999999996e-2
(b) 解らない。
適当に答えると、ステップ数はθ(3a)に比例して増加し、スペースもθ(3a)で増加する。
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
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)))))
Exercise1-19
Exercise1-20
;; 正規順序
(gcd 206 40)
正規順序による評価は次のように進行する。
(gcd 40 (remainder 206 40))
(gcd (remainder 206 40)
(remainder 40 (remainder 206 40)))
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40))))
(gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))
(remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))
(gcd 2 0)
2
完全に展開し、簡約されるので、remainder は 11回実行される。
;; 作用的順序
(gcd 206 40)
作用的順序による評価は次のように進行する。
(gcd 40 6) ;6: (remainder 206 40)
(gcd 6 4) ;4: (remainder 40 6)
(gcd 4 2) ;2: (remainder 6 4)
(gcd 2 0) ;0: (remainder 4 2)
2
引数が評価されてから作用させるので、remainder は 4回実行される。
Exercise1-21
199, 1999, 19999 の最小除数
(smallest-divisor 199)
;Value: 199
(smallest-divisor 1999)
;Value: 1999
(smallest-divisor 19999)
;Value: 7
Exercise1-22
指定範囲の連続する奇整数について素数性を調べる手続き search-for-prime を書け
;; 素数でない整数は出力しないようにした。
(define (search-for-prime start limit)
(if (prime? start)
(times-prime-test start))
(if (<= (+ start 2) limit)
(search-for-prime (+ start 2) limit)))
;; 速すぎて計測できないので大きな数で試した。
(search-for-prime 1000001 1000100)
1000003 *** 1.0000000000000009e-2
1000033 *** 1.0000000000000009e-2
1000037 *** 1.0000000000000009e-2
(search-for-prime 10000001 10000200)
10000019 *** .01999999999999602
10000079 *** .03999999999999915
10000103 *** 2.0000000000003126e-2
(search-for-prime 100000001 100000100)
100000007 *** .11999999999999744
100000037 *** 6.0000000000002274e-2
100000039 *** 6.0000000000002274e-2
ひと桁増えると計算時間がほぼ√10倍になると思うので、
・支持する。
・合っている。
Exercise1-23
(define (next n)
(if (= n 2)
3
(+ n 2)))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (next test-divisor)))))
(times-prime-test 1000003)
1000003 *** .00999999999999801
(times-prime-test 10000019)
10000019 *** 3.0000000000001137e-2
(times-prime-test 100000007)
100000007 *** .10999999999999943
速度に変化はないと思う。しかし理由が解らない。
Exercise1-24
Exercise1-25
Exercise1-26
Exercise1-27
カーマイケル数がフェルマーテストをだますことを示せ。
(define true #t)
(define false #f)
(define (carmichael-deceive-fermat-test? carmichael)
(define (iter a n)
(if (< a n)
(if (= (expmod a n n) a)
(iter (+ a 1) n)
false)
true))
(iter 1 carmichael))
(carmichael-deceive-fermat-test? 561) ;=> #t
(carmichael-deceive-fermat-test? 1105) ;=> #t
(carmichael-deceive-fermat-test? 1729) ;=> #t
(carmichael-deceive-fermat-test? 2465) ;=> #t
(carmichael-deceive-fermat-test? 2821) ;=> #t
(carmichael-deceive-fermat-test? 6601) ;=> #t
以上から、整数 n について a < n のすべての a で、a^n が n を法として a と合同になる
素数でない n が存在することが分かるので、カーマイケル数はフェルマーテストをだます。
Exercise1-28
Exercise1-29
;; 合成シンプソン公式を参考にした。
http://ja.wikipedia.org/wiki/%E3%82%B7%E3%83%B3%E3%83%97%E3%82%BD%E3%83%B3%E3%81%AE%E5%85%AC%E5%BC%8F
(define (cube x) (* x x x))
(define (integral f a b n)
(define h (/ (- b a) n))
(define (y k) (f (+ a (* k h))))
(define (next n) (+ n 2))
(/ (* h
(+ (y 0)
(* (sum y 1 next (- n 1)) 4)
(* (sum y 2 next (- n 2)) 2)
(y n)))
3))
(integral cube 0 1 100)
=>1/4
(integral cube 0 1 1000)
=>1/4
Exercise1-30
(define (sum term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ (term a) result))))
(iter a 0))
Exercise1-31
(a)
(1)与えられた範囲の点での関数値の積を返す手続き product を定義せよ。
(2)product を使って factorial を定義せよ。
(3)式 π/4 = (2*4*4*6*6*8..)/(3*3*5*5*7*7...) によってπの近似値を
productを使って定義せよ。
(1)
(define (product term a next b)
(if (> a b)
1
(* (term a) (product term (next a) next b))))
(2)
(define (factorial n)
(product identity 1 inc n))
(3)
;; John Wallis
;; http://www.pluto.ai.kyutech.ac.jp/plt/matumoto/pi_small/node5.html
(define (pi-product a b)
(define (pi-term x)
(/ (* (* x 2) (+ (* x 2) 2))
(square (+ (* x 2) 1))))
(define (pi-next x) (+ x 1))
(product pi-term a pi-next b))
gosh> (* 4 (pi-product 1.0 1000))
=>3.1423773650938855
(b) 反復的プロセスを生成する product を書け。
(define (product term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* (term a) result))))
(iter a 1))
Exercise1-32
(a) sum や product 更に一般的な accumulate の特殊な場合であることを示せ。
;; 再帰的プロセス版
(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))))
(define (sum term a next b)
(accumulate + 0 term a next b))
(define (product term a next b)
(accumulate * 1 term a next b))
(b) 反復的プロセスを生成する版
(define (accumulate combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner (term a) result))))
(iter a null-value))
Exercise1-33
;; 再帰版
(define (filtered-accumulate predicate combiner null-value term a next b)
(cond ((> a b) null-value)
((predicate a)
(combiner (term a)
(filtered-accumulate
predicate combiner null-value term (next a) next b)))
(else (filtered-accumulate
predicate combiner null-value term (next a) next b))))
;; 反復版
(define (filtered-accumulate predicate combiner null-value term a next b)
(define (iter a result)
(cond ((> a b) result)
((predicate a) (iter (next a) (combiner (term a) result)))
(else (iter (next a) result))))
(iter a null-value))
(a) 素数の2乗の和
(define (sum-squared-prime-numbers a b)
(filtered-accumulate prime? + 0 square a inc b))
(sum-squared-prime-numbers 2 10)
;Value: 87
(b) i < n で gcd(i,n) = 1 となる全整数の積
(define (product-gcd n)
(define (p i)
(= (gcd i n) 1))
(filtered-accumulate p * 1 identity 1 inc n))
(product-gcd 10)
;Value: 189
(product-gcd 100)
;Value: 426252881942771063138176712755660145456313428952105524817872601
Exercise1-34
(define (f g)
(g 2))
解釈系に (f f) を評価させるとどうなるか。
f の本体を取り出し仮引数 g を f で置き換える。
(f 2)
f の本体を取り出し仮引数 g を 2 で置き換える。
(2 2)
に帰着する。左端の演算子を評価すると値は 2 となる。値は手続きでなければならないが、
数値なのでエラーになる。
MIT scheme での結果。
;The object 2 is not applicable.
Gauche での結果。
*** ERROR: invalid application: (2 2)
Exercise1.35
1.2.2節の黄金比は、x^2 = x + 1 を満たす x である。
これを等価な、x = 1 + 1/x と書けば、平方根の計算と同様、x |-> 1 + 1/x の不動点を
探すことと同じである。
gosh> ([[fixed-point]] (lambda (x) (+ 1 (/ 1 x))) 1.0)
=>1.6180327868852458
Exercise1.36
(1) fixed-point を修正して、生成する近似値を順に印字できるようにせよ。
(define (average x y) (/ (+ x y) 2))
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2)) tolerance))
(define (try guess step)
(let ((next (f guess)))
(print-step next step)
(if (close-enough? guess next)
next
(try next (+ step 1)))))
(try first-guess 1))
(define (print-step n step)
(display step)
(display ": ")
(display n)
(newline))
(2) x^x = 1000 の解を求めよ。
(expt 4 4) < 1000 < (expt 5 5) なので、4.0 を fixed-point の予測値とした。
gosh> (fixed-point (lambda (x) (/ (log 1000) (log x))) 4.0)
1: 4.9828921423310435
2: 4.301189432497896
(略)
28: 4.555530430629037
29: 4.555539183677709
=>4.555539183677709
gosh> (expt 4.555539183677709 4.555539183677709)
=>1000.0087530953886
(3) 平均緩和法を使った場合とステップ数を比較せよ。
gosh> (fixed-point (lambda (x) (average (/ (log 1000) (log x)) x)) 4.0)
1: 4.491446071165521
2: 4.544974650975552
(略)
6: 4.5555268862194875
7: 4.5555342036887705
=>4.5555342036887705
gosh> (expt 4.5555342036887705 4.5555342036887705)
=>999.9962217021748
平均緩和法を使った場合、ステップ数は 1/4 になった。
Exercise1.37
(a) k項有限連分数を計算する手続きを定義し、kの順次の値で1/φの近似をとり手続きを調べよ。4桁の精度を得るにはkをどのくらいの大きくしなければならないか。
(1) cont-frac
;; 再帰的プロセス版
(define (cont-frac n d k)
(define (rec i)
(if (= i k)
(/ (n i) (d i))
(/ (n i) (+ (d i) (rec (+ i 1))))))
(rec 1))
(2) kの大きさ
1/φ の計算
gosh> (/ 1 (fixed-point (lambda (x) (+ 1 (/ 1 x))) 1.0))
=>0.6180344478216819
手続きを調べるため cont-frac-test を定義し、kの値が1から15まで1/φの近似を調べた。
kの増加に伴って精度が上がることを確認した。4桁の精度を得るには、kの値は11程度でよい。
(define (cont-frac-test a b)
(if (<= a b)
(let ((r (cont-frac (lambda (i) 1.0)
(lambda (i) 1.0)
a)))
(display a)
(display ": ")
(display r)
(newline)
(cont-frac-test (+ a 1) b))))
gosh> (cont-frac-test 1 15)
1: 1.0
2: 0.5
3: 0.6666666666666666
4: 0.6000000000000001
5: 0.625
6: 0.6153846153846154
7: 0.6190476190476191
8: 0.6176470588235294
9: 0.6181818181818182
10: 0.6179775280898876
11: 0.6180555555555556
12: 0.6180257510729613
13: 0.6180371352785146
14: 0.6180327868852459
15: 0.6180344478216819
(b) cont-frac の反復的プロセス版
(define (cont-frac n d k)
(define (iter a i)
(if (= i 1)
a
(iter (/ (n (- i 1)) (+ (d (- i 1)) a)) (- i 1))))
(iter (/ (n k) (d k)) k))
Exercise1.38
オイラーの展開による自然対数の底を近似するプログラムを書け。
;; e-2-cfの計算でkが20程度で15桁の精度が得られたので、
;; kを20としてeを近似するプログラムを書いた。
(define (e)
(define (e-2-cf k)
(cont-frac (lambda (i) 1.0)
(lambda (i) (if (= (remainder i 3) 2)
(- i (- (/ (+ i 1) 3) 1))
1.0))
k))
(+ (e-2-cf 20) 2))
gosh> (e)
=>2.718281828459045
Exercise1.39
正接関数の近似値を計算する手続き(tan-cf x k)を定義せよ。
(define (tan-cf x k)
(cont-frac (lambda (i) (if (= i 1) x (- (* x x))))
(lambda (i) (- (* i 2) 1))
k))
Exercise1.40
Exercise1.41
1. double を定義せよ
(define (double f)
(lambda (x) (f (f x))))
2. (((double (double double)) inc) 5) の返す値は何か。
=>21
Exercise1.42
f と g を1引数の関数とし、g の後の f の合成関数は関数 x |-> f(g(x)) と定義する。
合成関数を実装する手続き compose を定義せよ。
(define (compose f g)
(lambda (x) (f (g x))))
((compose square inc) 6)
=>49
Exercise1.43
数値関数fと正整数nをとり、fのn回作用関数を定義せよ。
;; 再帰的プロセス版
(define (repeated f n)
(if (= n 1)
f
(compose f (repeated f (- n 1)))))
((repeated square 2) 5)
;; 反復的プロセス版
(define (repeated f n)
(define (iter a n)
(if (= n 1)
a
(iter (compose f a) (- n 1))))
(iter f n))
Exercise1.44
1. smooth を書け。
(define dx 0.00001)
(define (smooth f)
(lambda (x)
(/ (+ (f (- x dx)) (f x) (f (+ x dx)))
3)))
2. n重平滑化関数を作る方法を示せ。
n重平滑化関数を得るには、与えられた関数 f の平滑化関数 (smooth f) を、
repeated を用いて n 回作用させればよい。
(define (n-fold-smooth f n)
(repeated (smooth f) n))
Exercise1.45
Exercise1.46
最終更新：2008年01月08日 22:23
