平成 26 年度プログラミング言語 II 期末試験解答例問題1 次の

平成 26 年度プログラミング言語 II 期末試験解答例
問題1
次の(𝑎𝑎)～(𝑐𝑐)の計算結果を記述せよ。(プログラムや計算過程を記述する必要はない。)
(𝑎𝑎) 79 +
53 − 35
82
+ 47 × 10 × � + 9 × 50�
82
40
(解答例)
212542 59/82
(解答例)
212542.71951219512
(解答例)
17428503/82
[求め方]
(+ 79 (/ (- 53 35) 82) (* 47 10 (+ (/ 82 40) (* 9 50))))
で計算する。
100000
(𝑏𝑏) � 𝑖𝑖
𝑖𝑖=1
(解答例)
5000050000
[求め方]
(reduce + 0 (range 1 100000))で計算できる。
100 200
(𝑐𝑐) � �(𝑖𝑖 + 𝑗𝑗)2
𝑖𝑖=1 𝑗𝑗=1
(解答例)
539350000
[求め方]
(define sum 0)
(for (range 1 100)
(lambda (i)
(for (range 1 200)
(lambda (j)
(set! sum (+ sum (* (+ i j) (+ i j))))))))
sum
とすれば計算できる。または、
1
(3点×3)
(reduce (lambda (i x)
(+ x (reduce (lambda (j y)
(+ y (* (+ i j) (+ i j))))
0
(range 1 200))))
0
(range 1 100))
とreduceで解くか、式を分解して、
(+ (* 200 (reduce + 0 (map (lambda (x) (* x x)) (range 1 100))))
(* 2 (reduce + 0 (range 1 200)) (reduce + 0 (range 1 100)))
(* 100 (reduce + 0 (map (lambda (x) (* x x)) (range 1 200)))))
と解くこともできる。
問題2 次の(a)～(c)の式を置き換えモデルにより計算せよ。 (3点×3)
(a)
((lambda (x y z) (* x (+ y z))) 3 8 43)
(解答例)
((lambda (x y z) (* x (+ y z))) 3 8 43)
=(* 3 (+ 8 43))
=153
(b)
((lambda (x y) (x (x y))) (lambda (a) (* a 30)) 200)
(解答例)
((lambda (x y) (x (x y))) (lambda (a) (* a 30)) 200)
=((lambda (a) (* a 30)) ((lambda (a) (* a 30)) 200))
=((lambda (a) (* a 30)) (* 200 30))
=((lambda (a) (* a 30)) 6000)
=(* 6000 30)
=180000
(解答例)
((lambda (x y) (x (x y))) (lambda (a) (* a 30)) 200)
=((lambda (a) (* a 30)) ((lambda (a) (* a 30)) 200))
=(* ((lambda (a) (* a 30)) 200) 30) ; 上記の解とここからが異なる
=(* (* 200 30) 30)
=(* 6000 30)
=180000
(c)
(((lambda (a) (lambda (b) (a b))) (lambda (x) (* x x))) 10)
2
(解答例)
(((lambda (a) (lambda (b) (a b))) (lambda (x) (* x x))) 10)
=((lambda (b) ((lambda (x) (* x x)) b)) 10)
=((lambda (x) (* x x)) 10)
=(* 10 10)
=100
問題3(円周率の問題) 次の漸化式により円周率(𝜋𝜋)を求めることができる。
𝑎𝑎0 =
1
2√3
,
𝑏𝑏0 =
1
𝑎𝑎𝑛𝑛 = (𝑎𝑎𝑛𝑛−1 + 𝑏𝑏𝑛𝑛−1 ),
2
1
3
𝑏𝑏𝑛𝑛 = �𝑎𝑎𝑛𝑛 𝑏𝑏𝑛𝑛−1
𝑎𝑎も𝑏𝑏もどちらも円周率の逆数に収束する。与えられた自然数𝑛𝑛に対し、1/𝑎𝑎𝑛𝑛 を計算する関数を再帰的プロ
セスと反復的プロセスでそれぞれ記述せよ。ただし、再帰的プロセスによる関数の関数名はpi-rとし、反
復的プロセスによる関数の関数名はpi-iとせよ。
(6点)
(解答例)
[再帰的プロセス]
(define (pi-r n) (/ 1 (a n)))
(define (a n)
(if (= n 0)
(/ 1 (* 2 (expt 3 0.5)))
(* 0.5 (+ (a (- n 1)) (b (- n 1))))))
(define (b n)
(if (= n 0)
(/ 1 3)
(expt (* (a n) (b (- n 1))) 0.5)))
[反復的プロセス]
(define (pi-i n)
(pi- (/ 1 (* 2 (expt 3 0.5))) (/ 1 3) n))
(define (pi- an-1 bn-1 cnt)
(if (= cnt 0)
(/ 1 an-1)
(let ((an (* 0.5 (+ an-1 bn-1))))
(pi- an (expt (* an bn-1) 0.5) (- cnt 1)))))
3
問題4(転置行列)
行列をリストのリストで表現することにする。例えば、次の行列
は次のリストのリストで表すことにする。
10 8
6
4
�
8 15
9
5
3
21
�
2
6
'((10 8 3)
(6 4 21)
(8 15 2)
(9 5 6))
このとき、ある行列を受け取ってその転置行列を返す関数transposeを記述せよ。例えば、上記の行列に対し、
次の行列が返されれば良い。
'((10 6 8 9)
(8 4 15 5)
(3 21 2 6))
(6点)
(解答例)
(define (transpose x)
(if (or (null? x) (null? (car x)))
'()
(cons (map (lambda (y) (car y)) x)
(transpose (map (lambda (y) (cdr y)) x)))))
問題5(ユークリッドの互除法)
を求めることができる。
2つの自然数𝑎𝑎, 𝑏𝑏が与えられたとき、次の手続きにより𝑎𝑎, 𝑏𝑏の最大公約数
1. 𝑎𝑎 ≥ 𝑏𝑏とする。
2. 𝑎𝑎を𝑏𝑏で割ったときの余りを𝑟𝑟とする。
3. もし𝑟𝑟 = 0なら、𝑏𝑏が求める答えとなるので、これを返して終了。
4. 𝑎𝑎を𝑏𝑏とし、𝑏𝑏を𝑟𝑟とし、2.に戻る。
この手続きを実現する関数mygcdを記述せよ。ただし、組み込み関数のgcdを用いてはいけない。また、
その実装した関数は、再帰的プロセスか、反復的プロセスか答えよ。
(6点)
(解答例)
(define (mygcd a b)
(if (> a b) (mygcd- a b) (mygcd- b a)))
4
(define (mygcd- a b)
(let ((r (remainder a b)))
(if (= r 0) b
(mygcd- b r))))
反復的プロセスである。
(解答例)
(define (mygcd a b)
(if (= b 0)
a
(mygcd b (remainder a b))))
反復的プロセスである。
(テスト例)
1071, 1029 => 21
21, 15 => 3
40, 6 => 2
5, 9 => 1
24, 30 => 6
42, 7 => 7
21, 98 => 7
33, 88 => 11
5

Download Report