基本情報技術者 2014年 秋期 午後 問08

解答の導き方

誤りやすいポイント

• 配列の添字と、見た文字数を混同すること
  $X$文字目の添字は$X$ではなく$X-1$です。そのため、比較するのは$Str1[X-1]$と$Str2[Y-1]$です。
• 文字が一致しない場合にも、斜め移動を使えると考えること
  斜めの線分は、対応する文字が同じときだけあります。一致しないときは、縦または横の移動だけを候補にします。
• 返却値の添字を1つ小さくすること
  配列の最後の文字の添字は文字列の長さより1小さいですが、$D$の座標は処理した文字数を表します。終点は$(Str1Len,Str2Len)$なので、返す値は$D[Str1Len,Str2Len]$です。

FAQ

解答の導き方

1. 同じ文字の組合せから、エディットグラフを選びます。
   問題文では、文字が同じ場合に「点$(X,Y)$から点$(X+1,Y+1)$に線分を引く」と説明されています。つまり、グラフの斜め線は、変換元と変換先に同じ文字がある組合せを表します。
   「peace」の文字と「people」の文字をそれぞれ比べると、同じ文字の組合せは次のとおりです。

   同じ文字	変換元の位置	変換先の位置	組合せ数
   p	1	1、4	2
   e	2、5	2、6	4

   合計は$2+4=6$組です。したがって、グラフにはこの組合せに対応する斜め線が6本あります。これに当てはまるのはウです。
2. αとβが実行される条件を確認します。
   問題文の手順では、文字が同じなら斜め移動ができます。斜め移動の距離は0なので、その場合は、斜め移動を含めた候補から最小値を選ぶαを実行します。
   一方、文字が異なるときは斜め移動ができません。その場合は、縦または横に移動する候補だけから最小値を選ぶβを実行します。
   つまり、aには「$Str1[X-1]$と$Str2[Y-1]$が同じかどうかを判定する条件」が入ります。
3. αとβの実行回数を数えます。
   外側のループは$X=1$から$5$まで、内側のループは$Y=1$から$6$まで実行されます。したがって、文字の組合せを調べる回数は$5\times 6=30$回です。
   そのうち、同じ文字の組合せは先ほど数えた6組です。よって、αは6回実行されます。残りの$30-6=24$回は文字が異なる組合せなので、βは24回実行されます。
4. 返却値である編集距離を求めます。
   「peace」から「people」へ変換するとき、共通して順番どおりに残せる文字は「pee」の3文字です。「peace」にはaとcがあり、「people」にはそのどちらもないため、共通部分を4文字にすることはできません。
   共通の3文字を残すには、「peace」からaとcを削除し、「people」にある残りのo、p、lを追加します。1文字ずつ操作するので、合計は削除2回と追加3回で、$2+3=5$回です。
   これより少ない回数では変換できないため、返却値は5です。bには、最終地点の値である$D[Str1Len,Str2Len]$が入ります。

誤りやすいポイント

• 斜め線は、文字が同じ組合せにだけ引きます。同じ文字が複数ある場合は、組合せをすべて数えます。
• αは、すべての文字の組合せで実行されるわけではありません。文字が同じときだけ実行されます。
• βの回数は、ループ全体の回数からαの回数を引いて求めます。
• 編集距離では、文字を置き換える操作は使いません。使えるのは1文字の追加と削除です。

FAQ