令和元年(R01)秋期 基本情報技術者試験 アルゴリズム問題 解き方解説

令和元年度秋期午後のアルゴリズム問題である問8の私の解き方・考え方について解説していきます。

問題

IPAの公式サイトで公開されています。このページでは問8についての解説を行います。

https://www.jitec.ipa.go.jp/1_04hanni_sukiru/mondai_kaitou_2019h31_2/2019r01a_fe_pm_qs.pdf

問題の概要

作成するプログラムは文字列検索に関するものですが、どちらかというと論理演算(ビット演算)に関する問題と言った方が良さそうです。

スポンサーリンク

設問1

設問1は関数 GenerateBitMask が生成するビットマスクを求める問題と、プログラムの穴埋め問題になります。

関数 GenerateBitMask がどのようなものであるかは [プログラムの説明] の(2)に記載されています。なので、この(2)がしっかり理解できれば設問1は解けます

ただ(2)の説明は文章として非常分かりにくいので注意が必要です。特に Mask[Index(Pat[i])] が配列の要素番号に関数 Index が組み込まれているのが分かりにくいです。

なので、まず先に関数 Index のみに注目して Index の動きを整理するのが良いと思います。関数 Index の説明は下記のようになっていますが、要は指定された英大文字がアルファベット順で何番目かを取得する関数です。

関数 Index は、引数にアルファベット順で n 番目の英文字を設定して呼び出すと、整数 n (1 ≦ n ≦ 26)を返す。

例えば Index(“A”) の返却値は “1”、index(“B” ) の返却値は “2″ といった感じです。なので、図1の Pat[ ] では関数 Index の返却値は下記のようになります。

  • i = 1:Index(“A”) = 1
  • i = 2:Index(“C”) = 3
  • i = 3:Index(“A”) = 1
  • i = 4:Index(“B”) = 2
  • i = 5:Index(“A”) = 1
  • i = 6:Index(“B”) = 2

ここを先に整理しておくと(2)の説明も分かりやすくなると思います。上記を踏まえて(2)に記載された関数 GenerateBitMask を図1の Pat[ ] に関して実行すると、下記のように Mask[ ] に値が格納されていきます。

  • Mask [ ] をすべて “0”B で初期化
  • i = 1:Mask[1] の下位から1番目のビットの値を1にする
    • Mask[1] が “000000000000000” から “000000000000001” になる
  • i = 2:Mask[3] の下位から2番目のビットの値を1にする
    • Mask[3]  が “000000000000000” から “000000000000010” になる
  • i = 3:Mask[1] の下位から3番目のビットの値を1にする
    • Mask[1] が “0000000000000001” から “0000000000000101” になる
  • i = 4:Mask[2] の下位から4番目のビットの値を1にする
    • Mask[2] が “0000000000000000” から “0000000000001000” になる
  • i = 5:Mask[1] の下位から5番目のビットの値を1にする
    • Mask[1] が “0000000000000101” から “0000000000010101” になる
  • i = 6:Mask[2] の下位から6番目のビットの値を1にする
    • Mask[2] が “0000000000001000” から “0000000000101000” になる

最終的な Mask[ ] の値は下記になります。

  • Mask[1]:”0000000000010101″
  • Mask[2]:”0000000000101000″
  • Mask[3]:”0000000000000010″

ここで図2を見てみると Mask[1] と Mask[3] の値が上記で求めた結果と一致しているのでここまでの考え方は合ってそうですね!

ここまでが説問1を解くために必要な GenerateBitMask の動きの整理です。

では設問を解いていきましょう。まず [  a  ] で問われているのは Mask[2] の値です。Mask[2] は先ほど求めた通り “0000000000101000” になりますので、[  a  ] の答えは「イ」となります。

次の問題はプログラムの穴埋め問題です。(2)の説明のどの部分がプログラムのどの部分に対応しているかを考えると解きやすいです。

関数 GenerateBitMask は下記の下線の色で分けたように2つの処理から構成されています。1つは青線で示した Mask[ ] の初期化で、もう一つは赤線で示した Mask[ ] への値の設定です。

これらの2つの処理をプログラムに対応させると下のようになります(色で区別してます)。

ですので、[  b  ] が含まれる行は Mask[ ] を “0”B で初期化するため処理であると考えられます。ここで選択肢を見ると、これを実現できそうなのは「ア」のみですね。他の選択肢だと “0”B 以外の値で初期化されてしまいます。ですので、[  b  ] の答えは「ア」となります。

次に [  c  ] について考えます。[  c  ] が含まれる行は(2)の説明の赤下線部を実現する処理となります。つまり、

Mask[Index(Pat[i])]に格納されている値の下位から数えて i ビット目を1にする処理

です。

まずプログラムで出てくる論理和とは、下記のような処理を行う演算です。

2つのビット入力値の一方でも "1" であれば "1" を返却し、両方が "0" の場合のみ "0" を返却する

プログラムの赤枠内ではこの論理和をビット毎に行うようになっていますので、[  c  ] が下位から数えて i ビット目のみ “1” である値であれば、下記を実現する事ができます。つまり [ c ] は下位から数えて i ビット目のみ “1” である値です。

Mask[Index(Pat[i])]に格納されている値の下位から数えて i ビット目を1にする処理

続いて [  c  ] の選択肢を見てみると、「”1″B を〇〇ビットだけ論理左シフト」という言葉が確認できます。論理左シフトとは下記を行う処理になります。

  • 指定された値を指定されたビット分左方向にずらす
  • ずらすことで右側に空いたビットは “0” で埋める

例えば指定された値が “1”B であるとき、シフト結果は指定されたビット x に応じて下記のようになります。

  • x = 0:”0000000000000001″
  • x = 1:”0000000000000010″
  • x = 2:”0000000000000100″
  • x = 3:”0000000000001000″

つまり、下位から数えて (x + 1)番目のビットのみが1となることになります。一方 [  c  ] には、前述の通り下位から数えて i 番目のビットのみが “1” である値が入りますので、シフトするのは「i – 1 ビット」となります。したがって [  c  ] の答えは「ア」となります。

間違えやすいのは「イ」だと思います。ただし「 i ビット」論理左シフトしまうと、シフト結果は下位から数えて「 i + 1」番目のビットが1の値になります。「 Mask[Index(Pat[i])] に格納されている値の下位から数えて i + 1 ビット目を1にする処理」になってしまい、説明と異なった動きになってしまいますので間違いです。

設問2

設問2は [プログラム2] のある時点の変数の値を答える問題になります。

[ プログラム2 ] は空欄になっている部分もありませんので、プログラムがどういう動きをして仕様を実現しているかを理解することなく、単に変数の動きをトレースするだけで解く事ができます。しかもこの設問の場合、文章で他の変数の値を教えてくれていますので割と簡単に解く事ができます。

[  d  ] で問われているのは i が 2 の時の β 行実行直後の Status の値です。設問2の文章より i が 2 の時に α 行実行直後の Status の値が “11”B であり、Mask[Index(Text[2])] が “10101”B である事が記載されています。さらに β 行で実行されるのは下記の処理です。

Status ← Status と Mask[Index(Text[i])] のビットごとの論理積

したがって、単純に文章で記載されている Status と Mask[Index(Text[2])] とのビットごとの論理積を求めれば良いだけです。論理積は下記のような処理を行う演算です。

入力された2つのビットの値が両方とも "1" の場合のみ "1" を、それ以外の場合は "0" を返却する

ですので Status には元々の Status と Mask[Index(Text[2])] の両方が “1” であるビットが “1” 、それ以外のビットが “0” である値、つまり “1”B が格納されます。したがって [  d  ] の答えは「イ」となります。

[  e  ] は単に Mask[Index(Text[9])] の値が問われている問題です。図1をみると Text[9] は “A” である事が確認できます。したがって Index(Text[9]) の値は “1” (”A” はアルファベット順で1番目)となります。さらに Mask[1] は図2より “0000000000010101” (つまり “10101”B)である事が確認できますので、[  e  ] の答えは「キ」となります。

[  f  ] は i が 9 の時の β 行実行直後の Status の値が問われている問題です。i が 8 の時の β 行実行直後の Status は設問2の文章より “10”B である事がわかります。したがって、i が 9 の時の α 行実行直後の Status は “101”B となります。

さらに [  e  ] で回答したように、 Mask[Index(Text[9])] は “10101”B ですので、これらの Status と Mask[Index(Text[9])] の値をビットごとに論理積をとった結果は “101”B となります。したがって [  f  ] の答えは「カ」となります。

設問3

設問3は正規表現で検索文字列を指定可能にするための GenerateBitMask を拡張した関数 GenerateBitMaskRegex に関する問題です。

結局は、この関数に検索文字列 Pat[ ] が “AC[BA]A[ABC]A” と “AC[B[AB]AC]A” とした時の Mask[1] と関数の返却値を答える問題ですので、素直に入力値に対してこれらがどのようなものになるかをプログラムを追っていけば解けます。

Pat[ ] が “AC[BA]A[ABC]A” の時に各ループ処理の終了直後の各変数の値の動きを表で表すと下記のようになります。

最終的な Mask[1] と PatLen がそれぞれ [  g  ] と [  h  ] の答えとなります。したがって [  g  ] の答えは「カ」[  h  ] の答えは「イ」となります。” [ ” から ” ]” までの間は PatLen の値が変化せず、同じビットを “1” とする処理が行われる事が理解できれば、最後まで書き出さなくても回答することは可能だと思います。

また Pat[ ] が “AC[B[AB]AC]A” の時に各ループ処理の終了直後の各変数の値の動きを表で表すと下記のようになります。

最終的な Mask[1] が [  i  ] の答えとなりますので、[  i  ] の答えは「ウ」となります。こちらも ” [ ” から最初の ” ] ” までは PatLen が変化しないことをプログラムから読み取れれば、文字数を数えるだけでも解けてしまう問題だと思います。が、時間があるのであれば各変数の動きを上の表のように地道に追っていった方が無難だと思います。

スポンサーリンク

解いてみた感想

問題をパッと見た感想は「難しい…」でした。特に [プログラム2] は難しいです。なぜあれで文字列の検索ができるのかはいまだに理解できてません。

ですが、実際に問題を解いてみて、難易度は低めだったのではないかと感じてます。理由は変数をトレースするだけで解ける問題が多かったことです。プログラムの穴埋めも少なかったですので、とにかく機械的に変数の動きを追うだけで得点は稼げる問題だったと思います。

今回解いてみて感じたポイントをまとめておきます。

  • 問題分が一見難しそうでも解くのは簡単な場合がある(むしろこういうケースは多い)ので、拒絶反応を示さずにじっくり問題を読み解いていく事が重要
  • (特に穴埋め問題以外は)プログラムの全体像・全容を理解する必要はない

★オススメページ★
下記ページから他の回の解説もたどれます。他の回のアルゴリズム問題の解き方がわからない場合は是非読んでみてください!

基本情報技術者試験 午後問題「アルゴリズム」過去問の解き方 解説 まとめ

本ページの図・プログラム・問題文について

図やプログラム、問題文はIPA公開の過去問題から引用しています。また図やプログラムに関しては説明に必要な部分に関してのみ加工して使用させていただいております。

出典:令和元年度 秋期 基本情報技術者試験(FE)試験区分 午後 問8

3 COMMENTS

まき

daeuさん。
お久しぶりです。まきです。先日試験を受けてきました。
先日の試験ですが前回の時よりも、心が落ち着いて受験することができました。
前回は仕事のことで、鬱病で精神的にかなり参った状態で受けたので
結果があまりできませんでした。

しかし、今回は心身共に快方に向かい今回は落ち着いて、アルゴリズムの問題もイメージもこんな感じになんだろうかなと思いながら解答しました。
(正解しているかは別として)

今まで気負いしていた気持ちが、今回はちゃんと抜けたので、あとは何回も問題を再現する練習して得点できるようになります。

また解説を読んでもう一度解いてみます。

解説ありがとうございます。

返信する
daeu

まきさん

コメントありがとうございます。
そしてお久しぶりです!

セキュリティ満点は素直にすごいです!!
私はセキュリティ苦手なのでセキュリティ得意なのは羨ましいです…。

精神的にも落ち着いてきているということで、私としても嬉しいです。
やっぱり心身ともに健康なのが一番ですからね!
私も年取って特にそう感じるようになりました…w
健康なら試験は何回でも受けれますし。

いい結果が出ていると良いですね…。心の奥底から願ってます。
やっぱり読者の方が合格してくれると嬉しいです。
私ももっと、ためになるページが作れるように頑張ります!

返信する

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です