アルゴリズム入門

共通問題（2015 年度 A セメスター試験）[試験日時：2015 年 12 月 25 日第 3 限（60 分），答案用紙：1 部，計算用紙：1 枚，持ち込み一切不可]
内容に関する質問は受け付けない．問題の記述が曖昧な場合は，適切な仮定をおいて回答し，どのような仮定をおいたのか明記せよ．
以下の問題で用いられている make2d(m, n) は m × n の 2 次元配列を作る．これは定義済みとしてよい．

問題 1
トリボナッチ数列は以下の 3 項間漸化式で定義される．

T0 = T1 = 0, T2 = 1
Ti = Ti−1 + Ti−2 + Ti−3 (i ≥ 3).
トリボナッチ数列の第 n 項 Tn を計算したい．これに関して以下の問に答えよ．

(1) 図 1 の空欄 (A) ∼ (C) を埋め，再帰を用いて Tn (n ≥ 0) を計算する関数 tri_rec を完成させよ．
(2) 図 2 の空欄 (D) ∼ (F) を埋め，ループを用いて Tn (n ≥ 3) を計算する関数 tri_loop を完成させよ．
(3) 図 3 の空欄 (G) ・ (H) を埋め，3 × 3 行列の乗算を用いて Tn (n ≥ 3) を計算する関数 tri_mat を完成させよ．なお，matpower(a, n) は 2 次元配列 a を行列とみなしたときに，その n 乗を計算する関数である．
(4) 3 つの関数 tri_rec, tri_loop, tri_mat を計算量の観点から比較せよ．
def tri_rec(n)
if
(A)
0else
if(B)

1else
(C)
end
end
end
図 1: プログラム tri rec

def tri_loop(n)p3 = 0

def tri_mat(n)a = make2d(3, 3)

p2 = 0p1 = 1c = 1

for i in 0..2
for j in 0..2if(G)for i in 4..np3 = p2a[i][j] = 1else

p2 =(D)

p1 =(E)c =(F)

a[i][j] = 0end
end

end
cend
図 2: プログラム tri loopendb = matpower(a,(H))

b[0][0]end
図 3: プログラム tri mat

問題 2(1) 二次方程式 ax2 + bx + c = 0（ただし a ̸= 0）の解を公式 x = (−b ±計算することを考える．以下の問に答えよ．

√b2 − 4ac)/2a を用いて Ruby で

1. a = 1.0，b = −4.0，c = 3.0 の場合と，a = 0.1，b = −0.4，c = 0.3 の場合は，本質的には同じ二次方程式であり，x = 1 が解の 1 つである．しかし，Ruby で計算してみたところ，前者に対しては1.0，後者に対しては 0.9999999999999996 という結果が得られた．この原因を述べよ．
2. a = 0.5，b = −0.9999999，c = 0.4999999 の場合を考える．このときは x = 1 が解の 1 つであるが，Ruby で計算してみたところ，1.0000000005138276 と大きな誤差を含む結果が得られた．この原因を述べよ．
3. a = c = 10−5 ，b = 104 の場合を考える．このとき，Ruby で計算してみたところ，解の 1 つが 0.0と得られたが，x = 0 は解ではない．この原因を述べよ．
(2) 原点を中心とした半径 1 の四半円（四分円）の面積

include(Math)def pi(n)を 4 倍することで円周率を計算したい．このために，図4 に示す，台形公式による数値積分プログラムを作成した．ここで sqrt(n) は n の平方根を求める関数である．

delta = 1.0 / n
s = 1.0 / 2.0
for i in 1..(n - 1)

以下の問に答えよ．

s = s + sqrt(1 - (end

1. 空欄 (A) ・ (B) を埋めよ．
2. pi(10)，pi(1000)，pi(100000) の結果はそれぞ(B)

れ 3.1045183262483182，3.141555466911023，(A)) ** 2)* 4

end

3.141592616402008 であった．これらの値が円周率と異なる理由，および，引数 n を大きくする

図 4: 円周率を計算するプログラムと円周率に値が近づいてゆく理由を説明せよ．

3. 引数 n が大きければ大きいほど，計算結果は円周率に近いだろうか．理由と共に述べよ．

問題 3
K 市の中心部は道が碁盤の目のように繋がっている．いま，南または東にのみ進んで 2 地点間を移動する経路

地図-(0, 0)sの数を数えるプログラムを作りたい．

K 市の地図は以下のデータ構造として表す．各地点は，南北方向の座標

y と東西方向の座標 x で (y, x) と表す．ただし y および x は非負の整数

p?
南(y)

東(x)

sNS


[1, 1, 1, 0, 1, 1],[1, 0, 0, 1, 1, 1],
[1, 0, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 1],
[1, 1, 1, 1, 0, 1],
[0, 0, 0, 0, 0, 0]

WE
[1, 1, 1, 1, 1, 0],[1, 1, 1, 0, 1, 0],
[1, 1, 0, 1, 1, 0],
[1, 1, 1, 1, 1, 0],
[0, 1, 1, 1, 1, 0],
[1, 1, 1, 1, 0, 0]

図 5: 地図と NS と WE の対応であり，南ないし東に行くほど値は大きい．道は 2 次元配列 NS と WE で表す．NS [y][x] は地点 (y, x) から南に向かう道がある場合に 1，そうでなければ 0 である．同様に，WE [y][x] は地点 (y, x) から東に向かう道がある場合に 1，そうでなければ0 である．これらの配列はプログラムのどこからでも参照できるとしてよい．図 5 に地図と NS と WE の対応の例を示す．
以下の問に答えよ．

(1) 図 5 の地図において，地点 (0, 0) から地点 (3, 3)（図中点 p）への経路は何通りあるか．
(2) 地点 (0, 0) から地点 (y, x) への経路の数 S(y, x) は以下の漸化式を満たす．空欄 (A) ∼ (D) を NS と

WE を用いて埋めよ．
S(0, 0)=1

S(0, x)=S(0, x − 1) ×(A)(x > 0)S(y, 0)=S(y − 1, 0) ×(B)(y > 0)S(y, x)=S(y, x − 1) ×(C)+ S(y − 1, x) ×(D)(x > 0, y > 0)(3) 設問 (2) の漸化式をふまえ，図 6 に示す再帰関数 cp1 を作った．空欄 (E) ∼ (H) を埋めよ．
(4) cp1 を動的計画法を用いて改善し，図 7 のプログラム cp2 を作った．空欄 (I) ∼ (N) を埋めよ．
(5) cp2 の計算量のオーダーを x と y を用いて表せ．導出の過程も簡単に示すこと．
def cp1(y, x)
if y == 0
if x == 0
(E)
else
(F)
end
else
if x == 0(G)else

def cp2(y, x)
count = make2d(y + 1, x + 1)
for i infor j indef calc(y, x, count)
if y == 0
if x == 0

(I)

(K)

(J)
else

count[i][j] = calc(i, j, count)
end
end

(L)
end
else

count[y][x]end

if x == 0
(M)
else

(H)

(N)

end
end
end
図 6: プログラム cp1

end
endend
図 7: プログラム cp2