今週の午後問題〔解答〕アルゴリズム Bitap 法による文字列検索 2019 (令和元) 年度

今週の午後問題 では毎週月曜に午後の必須選択問題から 1 問ピックアップして出題し、 解答欄 を設け、読者の皆さまにも解答してもらっています!

今週の午後問題は「 2019 年度 秋期 アルゴリズム」でしたが、皆さん、手応えはいかがでしょうか?

金曜になりましたので、出題の 解答 と 矢沢久雄さんによる 解説 に加えて、皆さんの正解率を公開します。

今週の午後問題
2019 年度 秋期 アルゴリズム Bitap 法による文字列検索

解答と解説

設問 1b 説明の都合で、空欄 a より先に空欄 b を取り上げます

正解

プログラムの説明に

Mask[] のすべての要素を “0” B に初期化

とあり、それがプログラムの空欄 b に該当します。

さらに、プログラムに、

| ・Mask[i] ← b  /* 初期化 */

というコメントも付けられています。空欄 b の正解は、選択肢アです。

infoスマートフォンをご覧の際、プログラムは右にスクロールできます

設問 1c 説明の都合で、空欄 a より先に空欄 c を取り上げます

正解

プログラムの説明を見ると、空欄 c に入るのは

下位から数えて i 番目のビットを 1 にした値

であり、

i が 1 なら
0000000000000001
i が 2 なら
0000000000000010
i が 3 なら
0000000000000100

・・・

と思われます。 0000000000000001 を i – 1 だけ左論理シフトすればよいでしょう。

ところが、プログラムを見ると

■ i: 1, i ≦ PatLen, 1
| ・Mask[Index(Pat[i])] ← c と
|                   Mask[Index(Pat[i])] とのビットごとの論理和
■

になっています。

具体例を見ると、”ACABAB” の先頭(i = 1)の “A” に対応するビットマスクが
0000000000000001 ではなく、
0000000000010101 になっています。

このことから、 “ACABAB” の中に “A” が 3 個あるので、それらを論理和で重ね合わせていることがわかります

空欄 c は、0000000000000001 を i – 1 だけ論理左シフトするだけでなく、それまでに得られているビットマスクと論理和で重ね合わせるのです。したがって、正解は選択肢アです。

設問 1a

正解

先に、空欄 b と空欄 c を解いたことで、ビットマスクを作る方法がわかりました。

空欄 a には、 “B” に対応するビットマスクが入ります。問題に示された “ACABAB” では、先頭から 4 番目と 6 番目に “B” が登場します。

したがって、
0000000000001000 と
0000000000100000 を論理和で重ね合わせた
0000000000101000 が “B” に対応するビットマスクです。

正解は、選択肢イです。

設問 2

正解d ― イ、 e ― キ、 f ― カ

プログラムを i = 1 ~ 9 までトレースすれば、空欄 d 、e 、f を埋められます。

変数の値をトレースするのは、 β の直後の値であることに注意してください。トレースした結果を以下に示します。

i Mask[Index(Text[i])] Status
1 “10101” B “1” B
2 “10101” B “1” B
(空欄 d )
3 “10” B “10” B
4 “101000” B “0” B
5 “101000” B “0” B
6 “10101” B “1” B
7 “10101” B “1” B
8 “10” B “10” B
9 “10101” B
(空欄 e )
“101” B
(空欄 f )

空欄 d 、空欄 e 、空欄 f の正解は、選択肢イ、選択肢キ、選択肢カです。

設問 3h 説明の都合で、空欄 g より先に空欄 h を取り上げます

正解

Mode の初期値は 0 で、 Mode = 0 なら 1 文字処理するごとに PatLen の値を 1 増やしています。

“[” を処理すると、 PatLen を 1 増やし、 Mode を 1 にします。そして、 “]” を処理すると、 Mode を 0 に戻します。これは、 “[” と “]” で囲まれた部分では、その間に何文字あっても PatLen が 1 だけ増えるということです。

したがって、問題に示された “AC[BA]A[ABC]A” という具体例を処理したときの PatLen は、

“AC” で 2 増えて、
“[BA]” で 1 増えて、
“A” で 1 増えて、
“[ABC]” で 1 増えて、
“A” で 1 増えるので、

全部で 6 になります。

したがって、空欄 h の正解は、選択肢イです。

設問 3g

正解

“AC[BA]A[ABC]A” において、 “A” は 5 回登場し、 “[” と “]” で囲まれた部分では、その間に何文字あっても PatLen が 1 だけ増えるのですから、 “ACAAAA” を想定してビットマスクを求めればよいことになります。

“A” は、 1 文字目、 3 文字目、 4 文字目、 5 文字目、 6 文字目に登場するので、それらの桁位置を 1 とした “111101” B というビットマスクになります。したがって、空欄 g の正解は、選択肢カです。

設問 3i

正解

誤って Pat[] に “AC[B[AB]AC]A” が与えられた場合には、 “[B[A” の部分で PatLen が 2 増えてしまうので、 “A” のビットマスクは、 “ACBAACA” を想定して求められます。

“A” は、 1 文字目、 4 文字目、 5 文字目、 7 文字目に登場するので、それらの桁位置を 1 とした “1011001” B というビットマスクになります。したがって、空欄 i の正解は、選択肢ウです。

みんなの解答

では、皆さん、手応えはいかがだったでしょうか?

なお、以下はこの問題の IPA の講評です。今後の参考になれば幸いです。

 問 8 では, Bitap 法を用いて文字列検索を行うプログラムについて出題した。
 設問 1 では, a の正答率は平均的で,おおむね理解されていた。 b の正答率は高く,よく理解されていた。 c の正答率は低く,イやウと誤って解答した受験者が多く見受けられた。下位から数えて i ビット目だけ 1 の 2 進数の値は, “1”B を i ビットではなく, (i – 1) ビットだけ論理左シフトした値と等しいので注意してほしい。
 設問 2 では, d の正答率は平均的で,おおむね理解されていた。 e , f の正答率は低く,あまり理解されていなかった。 i が 8 のときに行 β を実行した直後の Status の値を参考にして, i が 2 のときの処理と同様に考え,プログラムの処理を丁寧に追っていけば, e , f とも正答できた。
 設問 3 の正答率は低く,あまり理解されていなかった。 g は “[]” の内部に含まれる全ての文字のビットマスクでは, “[]” に対応する位置のビットが 1 になることが理解できれば,正答できた。 h は,変数 PatLen の値が 1 増加する場合について読み取ることができれば,正答できた。 i は, “[” の出現の後, “]” が出現する前に “[” が更に出現した場合と, “]” の出現の後, “[” が出現する前に “]” が更に出現した場合における変数 Mode と変数 PatLen の値の変化に注意して処理を追っていけば,正答できた。
 与えられた仕様を基に,プログラム中で使われる変数の意味を理解し,ビット処理を実装する能力やプログラムの動作を追跡する能力は,アルゴリズムを理解する上で重要であるので,身につけておいてほしい。

ぜひ、来週の午後問題にも挑戦してみてください!

label 関連タグ
Q. 午前試験を
『免除』するには?
A. 独習ゼミで午前免除制度を活用しましょう。
免除試験を受けた 86% の方が、
1 年間の午前免除資格を得ています。
2022 年 下期 試験向け
コース資料公開中!
info_outline
2022 年 下期 試験向け
コース資料公開中!
詳しく見てみるplay_circle_filled
label これまでの『今週の午後問題』の連載一覧 label 著者