第一回小テスト解答

2016 年 データ構造とアルゴリズム 小テスト(第一回) 模範解答
1 マッチング
問 1-1
女性のグループは (Alice, Becky, Carol), (Alice, Becky), (Becky, Carol), (Carol, Alice) の 4 通り.これ
らのグループで場合分けを行い,いずれの場合も選好を操作してもグループの全員がより好ましい男性とペア
になることが不可能であることを示す.
(i) (Alice, Becky, Carol) のとき
Alice と Becky のより好ましい男性は John である.したがってこの二名が同時により好ましい男性と
ペアになることは不可能.
(ii) (Alice, Becky) のとき
(i) と同様にしてグループの全員がより望ましい男性とペアになることは不可能.
(iii) (Becky, Carol) のとき
Becky のより好ましい男性は John,Carol のより好ましい男性は Lee である.ここで選好を操作するこ
とで Carol と Lee がペアになるとする.このとき Alice は John を第 1 希望としているので,Becky が
John にプロポーズしても John とペアになることはない.したがってグループ全員がより好む男性とペ
アになることは不可能.
(iv) (Carol, Alice) のとき
Carol のより好ましい男性は Lee,Alice のより好ましい男性は John である.ここで選好を操作するこ
とで Alice と John がペアになるとする.このとき Becky は第 1 希望の John に断られるので第 2 希望
の Lee にプロポーズを行う.このとき Carol は Lee に断られてしまうので,グループ全員がより好む男
性とペアになることは不可能.
問 1-2
(Alice, Becky, Carol) のグループを考える.選好を操作して Alice, Becky, Carol がそれぞれ Ken, John,
Lee を第一希望にしたとする.このとき Alice-Ken, Becky-John, Carol-Lee のペアからなるマッチングが得
られる.Becky, Carol はより好ましい男性とペアになり,Alice は正直に行動した場合と同じ男性とペアにな
ることが可能.
1
2 川渡りパズル
問2
グラフは図 1 に示す.最短経路の長さは 7.
図1
川渡り
3 アルゴリズム設計
問 3-1
アルゴリズムを以下に示す.
STEP1 N umM erge = 0 とする.
STEP2 A, B を読み取り機械に入れてそれぞれのデータを 2N umM erge 個ごとに区切ってソートしていく.
それぞれ 2N umM erge 個のデータを読み取るまで 1 つずつデータを読み取って比較し,小さいほう
のデータを C に書き込む(C が排出されたら続きを D に書き込む).一方のテープから 2N umM erge
個読み取ったら他方のテープから 2N umM erge 個になるまでデータを読み取り C に書き込む.次の
2N umM erge 個ずつのデータについても同じ操作を行う.これをテープ A, B が排出されるまで行う.
STEP3 N umM erge = N umM erge + 1 とする.
STEP4 N umM erge = 7 なら操作を終了する.そうでないなら A と C,B と D の役割をそれぞれ入れ替え
て STEP2 に戻る.
2
問 3-2
N umM erge = 7 のとき操作を終了する.つまり STEP2 の操作を 7 回行うことになるが,1 回の操作で各
テープはちょうど 1 回セットされる.したがって A がセットされる回数は 7 回.
4 Θ 記法
ある定数 c1 , c2 , n0 が存在し,任意の n ≥ n0 に対して式 (1) が成立することを示す.
c 1 n2 ≤
(1) 式を n2 で割ると c1 ≤
1
3
−
2
n
1 2
n − 2n ≤ c2 n2
3
≤ c2 となる.c2 ≥
1
3
なら n ≥ 1 に対して右辺の不等式が成立.c1 ≤
なら n ≥ 7 に対して左辺の不等式が成立.したがって c1 =
3
1
21 , c2
(1)
1
21
= 13 , n0 = 7 とすれば式 (1) が成立する.