はじめに
今回は基本情報技術者試験(FE)のアルゴリズム問題について解説していきます。
年度としては令和元年(2019年)の秋季です。
世間には様々な解説書などが出ていますが、人によって理解しやすい表現は違うと思いますので、数ある考え方の1つとして読んでもらえると嬉しいです。
問題の概要
この年度は文字列関連の問題で、ある検索対象文字列の中で指定した文字列の有無を検索するプログラムが題材となっています。
文字列検索の方式はBitap法を使うと書いてありますが、これをあらかじめ知っている必要はありません。
問題を進めていくと「そういう方法で文字列検索するのね」と分かってくると思います。
配列の考え方、ビット演算、あたりが感覚的に分かれば読み進めていけると思います。
基本的には問題分に記載されているプログラムに対し、具体的な値を入れて動きを見ていくことで解ける問題ですね。
試験の中でこのプログラムの全容を理解する必要は必ずしもありません。
問題文中のプログラムの内容把握
まずは問題文の[プログラムの説明]の部分をさらっと読んでいきましょう。
最初の段落に「なお、本門では、例えば2進数の16ビット論理型の定数 0000000000010101 は、上位の0を省略して"10101"Bと表記する。」とありますので、この問題ではそういう表し方なんだな、と思っておきましょう。
次の段落の(1)の部分に書かれているように、文字列検索を行う関数はBitapMatchで、この関数には検索対象の文字列Text[]と検索する文字列Pat[]を渡して呼び出すようです。
Text[]に格納された文字列の中にPat[]で指定した文字列があるか検索する関数、ということですね。
まずは問題文の通り、Text[]が"AACBBAACABABAB"、Pat[]が"ACABAB"である場合を具体例として考えていきます。
配列を視覚的に表した図が以下です。
例えば、Text[1]="A"、Text[3]="C"、Pat[1]="A"、Pat[2]="C"のように、
要素番号を用いてそれぞれの値を指定する考え方です。
次に(2)の部分で、関数GenerateBitMaskというものが出てきました。
ここではまず、問題文の「このようにMask[1]～Mask[26]に文字"A"～"Z"に対応するビットマスクを格納する。」という部分から、26種類のアルファベットを表す情報をMask[1]～Mask[26]に格納しており、その情報というものが0と1の数字の列だということが分かれば大丈夫です。
具体的な表し方はこの後の問題文で出てきます。
また、ここで関数Indexが出てきました。
これは「n番目の英大文字を設定して呼び出すと、整数n(1≦n≦26)を返す」と書いてあるので、
Index("A")=1、Index("B")=2、Index("Z")=26、であることがわかります。
(3)の部分ではText[]とPat[]が上の具体例だった場合のGenerateBitMaskの実行結果について記載されています。
また、(4)はGenerateBitMaskのプログラムが記載されています。
この部分は見て考える、というより、具体例に数値を当てはめてプログラムの動作と出力結果を見ていくアプローチが良いと思います。
ここからは設問1を考えつつ、プログラムの動作を確認していきましょう。
設問1の考え方
まずは設問1のaですが、これはPat[]が"ACABAB"の場合に、関数GenerateBitMaskを実行した結果の中で、Mask[2]に入る数値を回答するものです。
bとcについてはGenerateBitMaskのプログラム中に入る値または処理内容を回答するものとなっています。
したがって、Pat[]が"ACABAB"の場合にGenerateBitMaskで行われる処理を問題文の内容と照らし合わせ、矛盾のないものを選ぶかたちでbとcは回答できます。
その上で処理結果を確認することでaも導くことができますね。
ではGenerateBitMaskの処理内容を上から順に見ていきましょう。
最初の行でPatLenにPat[]の文字数を格納しています。Pat[]が"ACABAB"の場合だと、PatLenは6です。
その下で繰り返し処理があり、i=1からi=26まで、iを1ずつ増加させて、Mask[i]に「設問bの回答」を格納しています。
この処理にはコメントとして、/* 初期化 */と書いてありますので、問題文の中で、GenerateBitMaskの初期化について触れている箇所を探しましょう。
すると、[プログラムの説明]の(2)の部分で「関数GenerateBitMaskはMask[]の全ての要素を"0"Bに初期化した後」と書いてあります。
したがって、設問bの回答には「"0"B」が入ります。
次に、設問bの回答の下の行を見ていきます。
ここではi=1からi=PatLenまで、iを1ずつ増加させる繰り返し処理となっています。
PatLenはPat[]の文字数なので、PatLen=6です。
この繰り返し処理の中で、Mask[Index(Pat[i])]に「設問cの回答」とMask[Index(Pat[i])]とのビットごとの論理和を格納しています。
まずは「ビットごとの論理和」ですが、下図のようなイメージです。
2つのビット列の要素をそれぞれ比較して、両方、またはどちらかが「1」であれば論理和は「1」となります。
さて、設問cの回答を考えるにあたり、問題文の(3)の内容を確認します。
「Pat[]が"ACABAB"の例の場合、関数GenerateBitMaskを実行すると、Mask[]は図2のとおりになる。」と記載があるので、
実際に関数GenerateBitMaskを実行した出力結果が以下の図2と同一になるような設問cの回答を選べば良いことがわかります。
ここで設問cの回答群を見てみると、「論理シフト」という言葉が出ていますね。
回答群にあるような1ビットの論理左シフトは下図のようなイメージです。
ビット列の各要素を1つずつ左にずらし、空いた部分には「0」を入れます。
論理シフトの動作が分かったところで、関数GenerateBitMaskの以下の部分について、i=1の場合を考えてみます。
Pat[1]="A"であり、Index("A")=1なので、Index(Pat[1])=1となります。
よって、Mask[1]に「設問cの回答」とMask[Index(Pat[i])]とのビットごとの論理和を格納する処理となっています。
この時点ではMask[Index(Pat[i])]=Mask[1]には設問bの回答から"0"Bが格納されているため、
Mask[1]に「設問cの回答」と"0"Bの論理和を格納していると理解できます。
まずは設問cの「ア」の場合を考えます。
「"1"Bを(i-1)ビットだけ論理左シフトした値」と"0"Bの論理和を、Mask[1]に格納することになります。
ここでi=1なので、Mask[1]に格納されるのは"1"Bと"0"Bの論理和となり、これは"1"Bとなります。
i=2の場合はIndex(Pat[2])=Index("C")=3となり、Mask[3]に格納されるのは「"1"Bを1ビットだけ論理左シフトした値と"0"Bの論理和」となるため、
これは"10"Bです。
同様に、i=3の場合はMask[1]に「"1"Bを2ビットだけ論理左シフトした値と"1"Bの論理和」となり、"101"Bとなります。
ここまでの出力結果を見ると、問題文中の下図のMask[1]の結果と矛盾していないので、選択肢「ア」は有力な回答候補であることがわかりますね。
次は設問cの回答が「イ」の場合を考えます。
i=1の場合、Mask[1]に格納されるのは"1"Bを1ビットだけ論理左シフトした値と"0"Bの論理和となり、これは"10"Bとなります。
この時点で問題文中のMask[1]の値と異なるので、この選択肢は不適です。
設問cの回答が「ウ」の場合、i=1でMask[1]に格納されるのは"1"Bを5ビットだけ論理左シフトした値と"0"Bの論理和となり、これは"100000"Bとなり、
不適ですね。
設問cの回答が「エ」の場合はi=1でMask[1]に格納されるのは"1"Bを6ビットだけ論理左シフトした値と"0"Bの論理和となり、不適です。
設問cの回答が「オ」の場合はi=1でMask[1]に格納されるのは"1"Bと"0"Bの論理和となり、これは"1"Bとなります。
i=2の場合、Mask[3]に格納されるのは"1"Bと"0"Bの論理和となり、これは"1"Bとなりますが、問題文中のMask[3]は"10"Bとなっており、矛盾しています。
したがって、設問cに当てはまるのは選択肢「ア」であることが導かれます。
ここまでで設問bと設問cの回答が分かったので関数GenerateBitMaskの内容が明らかになりました。
ここで具体的にプログラムの出力を見ていくことで設問aの回答は導かれます。
"B"に対応するビットマスクであるMask[2]の内容はi=4とi=6の場合に値が更新され、
最終的に"101000"Bとなるので、設問aの回答は「イ」となります。
これで設問1はクリアできました。
設問2以降の考え方
長くなってしまったので、続きは以下の記事で記載しています。
www.77-lifework.com
ここまで読んでいただきありがとうございました。
出典：令和元年度 秋期 基本情報技術者試験 午後 問8
