1章の練習問題(hiront)
1.1
10
;Value: 10
(+ 5 3 4)
;Value: 12
(- 9 1)
;Value: 8
(/ 6 2)
;Value: 3
(+ (* 2 4) (- 4 6))
;Value: 6
(define a 3)
;Value: a
(define b (+ a 1))
;Value: b
(= a b)
;Value: #f
(if (and (> b a) (< b (* a b)))
b
a)
;Value: 4
(cond ((= a 4) 6)
((= b 4) (+ 6 7 a))
(else 25))
;Value: 16
(+ 2 (if (> b a) b a))
;Value: 6
(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1))
;Value: 16
1.2
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))
いつ改行していいのかさっぱり分かりません。
1.3
(define (square-sum a b c)
(if (and (<= a b) (<= a c)) (+ (square b) (square c))
(if (and (<= b a) (<= b c)) (+ (square a) (square c))
(+ (square a) (square b)))))
適当ー。
1.4
bがプラスならば、(+ a b)が実行され、bがマイナスか0ならば、(- a b)が実行される。
bがマイナスの時、(a-(-b))となり、bの絶対値とaを足すことと同等。
1.5
作用的順序では最初の(define (p) (p))が展開できない。
正規順序では展開されて、0が返される。
正規順序でも(p)を展開しそうに思えるけど、必要とされるまで遅延されるので、うまく行くらしいです。
1.6
condは、全ての項を評価してしまうので、
(sqrt-iter (improve guess x) x)を評価してしまい、無限に再帰しようとする。
1.7
(define (good-enough? guess x)
(= (improve guess x) guess))
学校の課題で提出したらダメ出しされそう。
1.8
(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))
(define (good-enough? guess x)
(= (improve guess x) guess))
(define (cube-root x)
(cube-root-iter 1.0 x))
1.9
(+ 4 5)
(inc (+ 3 5))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ 0 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9
再帰的プロセス
(+ 4 5)
(+ 3 6)
(+ 2 7)
(+ 1 8)
(+ 0 9)
9
反復的プロセス
1.10
(define (A x y)
(cond ((= y 0) 0)
((= x 0) (* 2 y))
((= y 1) 2)
(else (A (- x 1)
(A x (- y 1))))))
(A 1 10)
;Value: 1024
(A 2 4)
;Value: 65536
(A 3 3)
;Value: 65536
(define (f n) (A 0 n))
; f(n) = 2*n, f(0)=0
(define (g n) (A 1 n))
; g(n) = f(g(n-1)) = 2*g(n-1) = 2^n, g(0) = 0
(define (h n) (A 2 n))
; h(n) = g(h(n-1)) = 2^h(n-1) = 2^2^...2, h(0) = 0
1.11
(define (F n)
(F-iter 0 0 0 1 n))
(define (F-iter n-one n-two n-three count max-count)
(if (> count max-count) n-one
(F-iter (if (< count 3) count
(+ n-one (* 2 n-two) (* 3 n-three)))
n-one n-two (+ count 1) max-count)))
1.12
(define (c n k)
(if (= k 0) 0
(if (= k n) 1
(+ (c (- n 1) (- k 1))
(c (- n 1) k)))))
1 n
1 1
1 2 1 |
1 3 3 1 v
1 4 6 4 1
k ->
(if (or (= k 1) (= k n)) 1 …の方がすっきりしそうです。
1.13
Fib(n)はn=0のとき0、n=1のとき1、n≧2のときFib(n-1)+Fib(n-2)となる。
P(n) = (φ^n-ψ^n)/√5 (ただしφ=(1+√5)/2、ψ=(1-√5)/2とする)が、
任意の自然数nについてFib(n)になることの証明。
φは黄金比であり、
φ^2 = (φ+1)
両辺にφ^(k-1)をかけて
φ^(k+1) = φ^k+φ^(k-1) …(1)
ψとφの関係は
ψ = 1/(-φ) …(2)
(1)と(2)より、
ψ^(k+1) = 1/(-φ)^(k+1)
= 1/(-φ)^k+1/(-φ)^(k-1)
= ψ^k+ψ^(k-1) …(3)
k=0のとき
P(0) = (φ^0-ψ^0)/√5
= (1-1)/√5
= 0
k=1のとき
P(1) = (φ^1-ψ^1)/√5
= (φ-ψ)/√5
= ((1+√5)/2-(1-√5)/2)/√5
= (1+√5-1+√5)/2√5
= 2√5/2√5
= 1
n=k,k-1の成立を仮定する。
n=k+1のとき
P(k+1) = (φ^(k+1)-ψ^(k+1))/√5
(1)と(3)を使って
= ((φ^k+φ^(k-1))-(ψ^k+ψ^(k-1))/√5
= (φ^k-ψ^k)/√5+(φ^(k-1)-ψ^(k-1))/√5
= P(k)+P(k-1)
Fib(n)がφ^n/√5に最も近い整数であることの証明。
|Fib(n)-φ^n/√5| < 1/2であれば良いと考える。
|Fib(n)-φ^n/√5|
= |(φ^n-ψ^n)/√5-φ^n/√5|
= |ψ^n/√5|
|ψ| = |1-√5/2| = 0.618033988749895 < 1
√5 = 2.23606797749979 > 2
|ψ^n/√5| < 1/2
1.14
cc(11,5)
+---------+
| |
cc(-39,5) cc(11,4)
| +---------+
0 | |
cc(-14,4) cc(11,3)
| +-----------------------------------+
0 | |
cc(1,3) cc(11,2)
+---------+ +--------+
| | | |
cc(-9,3) cc(1,2) cc(6,2) cc(11,1)
| +-------+ | |
0 | | (A) (B)
cc(-4,2) cc(1,1)
| +-------+
0 | |
cc(0,1) cc(1,0)
| |
1 0
(A)
|
cc(6,2)
+-----------------------+
| |
cc(1,2) cc(6,1)
+--------+ +-----------cc(6,0)-0
| | |
cc(-4,2) cc(1,1) cc(5,1)
| +-------+ +------------cc(5,0)-0
0 | | |
cc(0,1) cc(1,0) cc(4,1)
| | +------------cc(4,0)-0
1 0 |
cc(3,1)
+------------cc(3,0)-0
|
cc(2,1)
+------------cc(2,0)-0
|
cc(1,1)
+-------+
| |
cc(0,1) cc(1,0)
| |
1 0
(B)
|
cc(11,1)
+------------cc(11,0)-0
|
cc(10,1)
+------------cc(10,0)-0
|
cc(9,1)
+------------cc(9,0)-0
|
cc(8,1)
+------------cc(8,0)-0
|
cc(7,1)
+------------cc(7,0)-0
|
cc(6,1)
+------------cc(6,0)-0
|
cc(5,1)
+------------cc(5,0)-0
|
cc(4,1)
+------------cc(4,0)-0
|
cc(3,1)
+------------cc(3,0)-0
|
cc(2,1)
+------------cc(2,0)-0
|
cc(1,1)
+-------+
| |
cc(0,1) cc(1,0)
| |
1 0
1.15
a.
f(0) = 12.15
f(n) = (1/3)*f(n-1) (n > 0)
f(n-1) > 0.1 かつ f(n) <= 0.1 のときのnを求める。
一般項は
f(n) = 12.15*(1/3)^n
仮に f(n) = 0.1 として、
0.1 = 12.15*(1/3)^n
1/121.5 = (1/3)^n
n = log(1/3) (1/121.5)
n = -log(1/3) 121.5
n = log3 121.5
n = 4.36907024642854
nは f(n) <= 0.1 が成り立つ整数なので、5。
b.
nをステップ数として漸化式を考える。
aは1ステップで3倍の処理をするので、
a = 3*Θ(n)
一般項は
a = 3^Θ(n)
増加量を求めると
Θ(n) = log3 a
ステップ数の増加の程度はΘ(n) = log3 a
スペースの増加の程度も同じ。
イメージ
^ x
| |
l +-+-+
| | | |
| n n n 3n
(log3 a) |
| +-+-+
| | | |
| n n n 3n
| |
| ... ...
v a = 3^n
1.16
(define (fast-expt b n)
(fast-expt-iter b n 1))
(define (fast-expt-iter b n a)
(cond ((= n 0) a)
((even? n) (fast-expt-iter (square b) (/ n 2) a))
(else (fast-expt-iter b (- n 1) (* a b)))))
(define (even? n)
(= (remainder n 2) 0))
1.17
(define (fast-multi a b)
(cond ((= b 0) 0)
((even? b) (double (fast-multi a (halve b))))
(else (+ a (fast-multi a (- b 1))))))
(define (even? n)
(= (remainder n 2) 0))
(define (double n)
(+ n n))
(define (halve n)
(if (= (remainder n 2) 0)
(/ n 2)
(/ (- n 1) 2)))
1.18
(define (fast-multi a b)
(fast-multi-iter a b 0))
(define (fast-multi-iter a b m)
(cond ((= b 0) m)
((even? b) (fast-multi-iter (double a) (halve b) m))
(else (fast-multi-iter (double a) (halve b) (+ a m)))))
最終更新：2008年05月03日 15:54
