はじめに
こんにちは。
今回の記事は令和元年(2019年)秋季の基本情報技術者試験(FE)のアルゴリズム問題についての解説の続きです。
問題文の内容や設問1の考え方については以下の記事を参照お願いします。
www.77-lifework.com
ビット列の論理積
設問2の中でビット列の論理積の演算が必要となる箇所がありますので簡単に説明します。
AとBの論理積は記号を用いると「A・B」などと表されます。
ここでは例として、A="0110001100"、B="0011011000"という2つのビット列があり、これらの論理積を演算する場合を考えると以下のようなイメージです。
それぞれのビット列で対応する値同士を確認し、両方とも「1」である場合のみ「1」を出力します。
よってこの例ではA・B = "0010001000" となります。
論理積の演算が出てきたら上記を参照して考えていきましょう。
では進めていきます！
設問2の考え方
ここでは問題文の図1のようにText[]とPat[]の値を設定し、関数BitapMatchを実行したときのMask[Index(Text[i])]とStatusの値を問われています。
上記を考える上で、具体的なText[]とPat[]の値を入れて関数BitapMatchを実行し、各値の変化を見てみましょう。
まずは問題文にある通り、Text[] = "AACBBAACABABAB"、Pat[] = "ACABAB" とします。
この状態で関数BitapMatchを実行すると、まず1行目でTextLenにTextの文字数が入るのでTextLen=14となります。
2行目では関数GenerateBitMaskが実行され、その戻り値をPatLenに格納しています。
関数GenerateBitMaskの動作については設問1で判明していますので詳細は省きますが、実行結果としては
Mask[1]="010101"B
Mask[2]="101000"B
Mask[3]="000010"B
となり、戻り値はPat[]の文字数となるので、PatLen=6ですね。
関数BitapMatchに戻り、3行目でStatus="0"B、4行目ではGoal="1B"を(6-1)ビットだけ論理左シフトした値="100000"B
となります。
ここから繰り返し処理となっていて、i=1からi=TextLen=14までiを1ずつ増加させて反復処理をする動作ですね。
【i=1の場合】
まずはi=1として、問題文αの部分での処理でのStatusの値は
Statusを1ビットだけ論理左シフトした値と"1"Bとの論理和
="0"Bを1ビットだけ論理左シフトした値と"1"Bとの論理和
="1"B
となります。
次に問題文βの処理ですが、Text[]の1文字目が"A"なので、Mask[Index(Text[i])]の値は
Mask[Index(Text[i])]
=Mask[Index(Text[1])]
=Mask[Index("A")]
=Mask[1]
="010101"B
です。
よってStatusの値は
StatusとMask[Index(Text[i])]とのビットごとの論理積
="000001"Bと"010101"Bとのビットごとの論理積
="1"B
ですね。
その下の行ではStatusとGoalとのビットごとの論理積が"0"Bかどうか判定する処理があります。
現状だと
StatusとGoalとのビットごとの論理積
="000001B"と"100000"Bとのビットごとの論理積
="0"B
となるので、return(i-PatLen+1)の処理は実行されず、繰り返し処理の最初に戻ります。
ここで改めてMask[Index(Text[i])]とStatusの値を確認してみましょう。
i=1なので、
Mask[Index(Text[i])]
=Mask[Index(Text[1])]
=Mask[Index("A")]
=Mask[1]
="010101"B
です。(最初の0は省略可能です)
そしてStatusは
Status="1"B
です。
したがって以下の問題文の表3の値と同一ですね。
では同じようにi=2の場合について考えてみましょう。
【i=2の場合】
Status="1"Bの状態で問題文のαの処理が実行されます。
したがって、αの処理実行後のStatusの値は
"1"Bを1ビットだけ論理左シフトした値と"1"Bとの論理和
="11"B
となります。
次にβの処理ですが、ここでのMask[Index(Text[i])]の値は
Mask[Index(Text[2])]
=Mask[Index("A")]
=Mask[1]
="010101"B
です。
よってβの処理実行後のStatusの値は
"11"BとMask[1]とのビットごとの論理積
="000011"Bと"010101"Bとのビットごとの論理積
="1"B
となります。
したがって設問dの解答は「イ」となります。
その下の行で
StatusとGoalとのビットごとの論理積
="000001B"と"100000"Bとのビットごとの論理積
="0"B
となるので、ここでもreturn(i-PatLen+1)の処理は実行されず、繰り返し処理の最初に戻ります。
次にi=3の場合、といきたいところですが、設問で問われているのはi=9のときにβの処理が実行された後のMask[Index(Text[i])]とStatusの値です。
繰り返し処理の中でMask[Index(Text[i])]の値が変更され得る箇所はなく、Statusについては1つ前の繰り返し処理の結果を使用すれば良いため、
問題文の表3のi=8の箇所を参照すれば大丈夫です。
よって、ここからはi=9の場合を考えます。
【i=9の場合】
まずはi=8の処理後のStatusの値ですが、表3より、Status="10"Bです。
次に問題文のαの処理実行後のStatusの値ですが、
Statusを1ビットだけ論理左シフトした値と"1"Bとの論理和
="10"Bを1ビットだけ論理左シフトした値と"1"Bとの論理和
="101"B
となります。
そして問題文のβの処理ですが、Text[]の9文字目は"A"なので、Mask[Index(Text[i])]の値は
Mask[Index(Text[9])]
=Mask[Index("A")]
=Mask[1]
="010101"B
です。
よってStatusの値は
"000101"Bと"010101"Bとのビットごとの論理積
="101"B
となります。
したがって設問eは「キ」、設問fは「カ」がそれぞれ適切です。
これで設問2はクリアですね。
