令和元年(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

アルゴリズム問題の対策(PR)

過去問を解いてみて感触はいかがだったでしょうか?

全く分からなかった...という方もいらっしゃるかもしれません。はっきりいってアルゴリズム問題は、特に慣れないと難易度は高いです。

なので、こういった方にはもっと "簡単なアルゴリズム問題を解いて慣れていく" ことをオススメします。で、この簡単なアルゴリズム問題を解くのにオススメの本が下記の うかる! 基本情報技術者 [午後・アルゴリズム編] です。

オススメする理由は、特に本の前半部分で難易度の低いアルゴリズムの紹介や解説が行われているところです。こういったアルゴリズムの動作などを実際にトレースして追ってみたりすることで簡単な問題からアルゴリズム問題に慣れていくことができます。

また、「アルゴリズムとは?」といったアルゴリズム入門から解説してくれているので、プログラミングをやったことない方にも親切な内容になっています。

アルゴリズム問題に全く手がつかないというような方は、まずは上記のような本でアルゴリズムに慣れるのがオススメです。

慣れてきたら、あとは実際の過去問を解いて "さらに考える力を養う" & "実際のアルゴリズム問題に慣れる" のが良いと思います。

私のサイトでも過去問の解説をしていますので是非参考にしてください。私の解説だけでなく、他の人の解説も参考にしたいような場合には、下記のような過去問の参考書もオススメです(アルゴリズム問題だけでなく、全問題の解説も充実しています)。

同じカテゴリのページ一覧を表示

9 COMMENTS

まき

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

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

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

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

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

返信する
daeu

まきさん

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

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

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

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

返信する
まき

3回問題を解いてみました。
設問2 fの解説なのですが、解説にもある通り
>i が 8 の時の β 行実行直後の Status は設問2の文章より “10”B である事がわかります。したがって、i が 9 の時の α 行実行直後の Status は “101”B となります。
ということは、
status”10B”→(論理左シフトした値)
→100Bと”1B”ごとの論理和
→101Bということで正解はカということですか?

返信する
daeu

まきさん

コメントありがとうございます!

そこの部分はあくまでも α 実行後の Status の値に解説になります。解説分かりにくくて申し訳ありません。

実際に「f」で問われているのは β 実行後の Status の値ですので、もう少し考える必要があります。

β では Status と Mask[index(Text[i])] との論理積を Status に格納する処理が行われています。

なので、Status と Mask[index(Text[i])] との論理積を計算結果が「f」の答えとなります。
Status の値は、まきさんも書いてくださっている通り “101”B です。

では Mask[index(Text[i])] の値は何であるかと言うと、これは「e」の答えですが、一応解説しておくと、

・Text[i] の値
・index(Text[i]) の値
・Mask[index(Text[i])] の値

と言う風に順に追っていくことで求めることができます。また設問2には Text[] や Pat[] は図1の通りに格納している旨が記載されていますし、図2の Mask[] は図1の Pat[] に対するものですので、図1と図2からこれらの値を求めることができます。

i は設問に記載の通り “9” です。

図1の表を見ると Text[9] には “A” が格納されていることが分かります。

また index(A) は問題文に下記のように記載されていますので、”1″ となります。

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

さらに Mask[1] は図2から “10101”B であることが確認できます。

したがって i = 9 の時の β においては

“101”B と “10101”B でビットごとの論理積を計算することになります。
一番右のビットを第0ビットとすると、各ビットの論理積結果は下記の通りになります。

第0ビット:”1″
第1ビット:”0″
第2ビット:”1″
第3ビット:”0″
第4ビット:”0″

したがって i = 9 の時の β 実行直後の Status の値は “101”B となります。

返信する
まき

要約
Status の値は、 “101”B 。

では Mask[index(Text[i])] の値は何であるかと言うと
・Text[i] の値
・index(Text[i]) の値
・Mask[index(Text[i])] の値
の順で追う
i は設問に記載の通り “9” です。

図1の表を見ると Text[9] には “A” が格納されている
また index(A) は問題文に下記のように記載されていますので、”1″ となる。
さらに Mask[1] は図2から “10101”B であることが確認できる

  “00101”B
  “10101”B でビットごとの論理積で
   “101”B となる
という理解でよろしいですか
また今回の午前試験は72点で午後38点でした

返信する
daeu

まきさん

バッチリです!
アルゴリズム問題はそんな感じで問題文をじっくり少しずつ、着実に読み解いていくことが重要です!大変ですが、これを繰り返していけば問題を解く力が付くと思います。

アルゴリズムはプログラミングでも力付きますのでプログラミングしてみるのもオススメです。例えば過去問をプログラミングしてみるとか。

午後対策は時間がかかりますが、午前はバッチリなようなので、試験直前までは午後問題に集中してじっくり力つけていけば良いと思います!

返信する
gg

すみません。
設問3が訳分からなくて、申し訳ないのですが細かく教えていただけますでしょうか?

返信する
daeu

gg さん

設問3に関しては、問題文で指定された Pat の値を実際にプログラムに入力した際に、
各変数がどのように変化していくかを追っていけば、解くことができると思います。

下の図のように、1行ずつどのような処理が行われるかを考えていけば、各変数がどのように変化しているかを追うことはできると思います。

・i=1の時の処理

・i=2の時の処理

・i=3の時の処理

・i=4の時の処理

・i=5の時の処理

↑のようなことを必要な回数繰り返していけば、答えは導き出せます。

そして、これらの変数の中から重要なものをまとめたものが、解説の中で示している表になります。

返信する

コメントを残す

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