[平成２６年度秋] 午後 問8解説

[問題文・解答]

平成２６年度１０月に実施された基本情報技術者試験の午後試験の問題・解答はIPA公式ページからダウンロード出来ます。（以下リンク）

[H26秋 午後 問題文]　　　[H26秋 午後 解答]

[問題概要]

この問題は必須問題です。
出題分野はデータ構造及びアルゴリズムで、問題の題材は編集距離の算出です。
ある文字列から別の文字列へエディットグラフを用いて変換するプログラムについて問われます。専門知識が無くても、問題文をよく理解出来れば解答可能な問題です。

[設問1]

プログラムの処理の流れは以下の通りです。
①点(0,0)→点(X,Y)への最短移動距離を格納する配列Dを定義する。
②点(0,0)→点(X,0)への最短移動はX軸上を横に移動するだけなのでD[X,0]にXを格納する（0≤X≤Str1Len)
③点(0,0)→点(0,Y)への最短移動はY軸上を縦に移動するだけなのでD[0,Y]にYを格納する（0≤Y≤Str2Len)
④上記以外の点(X,Y)について最短移動距離を求めて格納する。ここで、点(X-1, Y-1)から直接点(X,Y)へ移動出来る場合とそうでない場合で条件分岐する。（P.42②の部分参照）
④-1)直接移動できる場合は、D[X-1, Y-1]、D[X-1, Y]+1、D[X, Y-1]+1のうち最小値をD[X, Y]に格納する。
④-2)直接移動できない場合は、D[X-1, Y]+1、D[X, Y-1]+1のうち最小値をD[X, Y]に格納する。
⑤点(0,0)→点(Str1Len, Str2Len)への最短移動距離D[Str1Len, Str2Len]を返す。

a) aの行では上記の処理④の条件分岐判定を行います。P.42上段「Str1[X]とStr2[Y]が同一の文字の場合、点(X, Y)から点(X+1, Y+1)に線分を引く」とあるようにStr1[X]とStr2[Y]が同一であれば点(X, Y)→点(X+1, Y+1)への直接移動が可能となります。
ただし、ここで処理している移動は点(X-1, Y-1)→点(X, Y)なので、aの条件判定はStr1[X-1]とStr2[Y-1]が等しいかどうかとなるので「ア」が適切です。

b) bの行では上記の処理⑤を実行するため、「ウ」が正解です。

[答] a) ア　b) ウ

[設問2]

c) Str1="peace"とStr2="people"ののエディットグラフは、縦軸５本、横軸６本の格子となります。
また、Str1とStr2で以下の６カ所が同じ文字となっているため、それに対応する点から右上に向かって斜線が引かれます。
・1文字目と1文字目　→　点(0, 0)
・1文字目と4文字目　→　点(0, 3)
・2文字目と2文字目　→　点(1, 1)
・2文字目と6文字目　→　点(1, 5)
・5文字目と2文字目　→　点(4, 1)
・5文字目と6文字目　→　点(4, 5)
従って、「ウ」のグラフが正解です。

d) αの行は点(X, Y)から点(X+1, Y+1)に線分を引いている部分つまりc)で述べた６カ所で実行される処理なので、「ウ」の6回が正解です。

e) βの行は点(X, 0)(0≤X≤5)、点(0, Y)(0≤Y≤6)及びdの６カ所を除く全ての点に対して実行されます。よって「カ」の24回が正解となります。

f) エディットグラフより点(0, 0)→点(5, 6)の最短移動距離は5となるため「イ」が正解です。

[答] c) ウ　d) ウ　e) カ　f) イ

上記の解説は問題と解答を元に自分なりの考え方を記述しており、間違っている部分もあるかと思いますので、ご了承願います。また、誤りについては正しい考え方をご指摘・ご教授頂けると助かります。