はじめに
基本情報技術者試験の午後問8アルゴリズムとデータ構造の問題を解説してみるという取り組みを以前行いました。
せっかくなのでその時の解説をQiitaにも投稿しておきます。
あくまで自分ならこう解くという解き方の例の1つですが、どなたかの参考になれば幸いです。
問題文と解答のダウンロード先URL
平成22年春期午後問題は下記IPAの公式サイトからダウンロードできます。
問題冊子
https://www.ipa.go.jp/shiken/mondai-kaiotu/ug65p90000004n2z-att/2010h22h_fe_pm_qs.pdf
解答例
https://www.ipa.go.jp/shiken/mondai-kaiotu/ug65p90000004n2z-att/2010h22h_fe_pm_ans.pdf
採点講評
https://www.ipa.go.jp/shiken/mondai-kaiotu/ug65p90000004n2z-att/2010h22h_fe_pm_cmnt.pdf
問題文の読み方
自分の場合、大概次の順序で読んでいます。
- 設問に軽く目を通す
- 問題文の設問と対応した箇所をチェックする
- 問題文を頭から読み、設問箇所まで来たら問題を解く
問題文を読むときは、大体次のような読み方をしています。
- 説明文は、キーワードをチェックしながら読む
- プログラム名や変数名等
- 終了条件や添え字の説明
- 図表が出てきたら、文章の説明の該当箇所を確認する
- プログラムが出てきたら、「共通に使用される疑似言語の記述形式」と突き合わせる
設問1
設問1は空欄a,b, cの穴埋め問題です。
設問1 a
aに関する解答群として、下記4択が与えられています。
ア num ≧ 0
イ num ≧ 1
ウ num > 1
エ num > 2
問題文中の空欄aはp. 45の[プログラム]の下図Sortプログラム中にあります。
ここでp. 3の 共通に使用される疑似言語の記述形式 を確認します。
空欄aは単岐選択処理の条件式であることがわかります。
Sortプログラムの処理の処理を続行する条件に着目して問題文を探すと、p. 43の[プログラムの説明]（2）①に下図のような記述があります。
「この再帰的な呼出しは、引数で渡される配列listのデータの個数が1になると終了する。」
配列listのデータの個数が1になると終了する、すなわち、配列listのデータの個数が1という条件を満たすまでは続行することがわかります。
ここで改めてaに関する解答群を検討します。
ア num ≧ 0
イ num ≧ 1
ウ num > 1
エ num > 2
ア、イはnum=1のときも続行されるためNG
エはnum=2のときに終了するためNG
したがって正解はウであるとわかります。
正解：ウ
設問1 b
bに関する解答群として、下記4択が与えられています。
ア list[i]
イ list[num+i]
ウ list1[num1+i]
エ list1[num2+i]
何をやっているか読んでみる
問題文中の空欄bもp. 45の[プログラム]の下図Sortプログラム中にあります。
対応する説明を問題文中から探すと、p. 43[プログラムの説明]に下図のような説明があります。
前の図と問題文を突き合わせると、空欄bはどうやら以下のようなことをやっているようだぞというのが判ります。
配列listに格納されているデータのうち残りnum - num / 2を配列slist2に格納する
また、疑似言語の問題で配列が出てきた場合は、添字が0始まりなのか1始まりなのかも確認しておく必要があります。
今回の場合は、p. 44 [プログラムの説明]の(4)に「配列の添字は0から始まる。」という記載があります。
値を代入して考えてみる
アルゴリズム問題を解くときに手頃な値を代入して考えてみるというのを個人的によくやります。
今回もその作戦でいきました。
仮にnum = 7とするとnum1とnum2はそれぞれ以下の値になります。
num=7
num1=num/2=3
num2= num–num/2=4
空欄bの1つ上の行に「i:0, i < num2, 1」とあることから以下が判ります。
iは 0 <= i < num2 の範囲を動く
ここまで判ったところで、選択肢ア~エに値を代入してみます。
今回のようにiが決まった範囲を動くときは、下限値と上限値に代入して境界値チェックを行うのが良さそうです。
i=0のとき
まずはiの下限値であるi=0を代入します。
ア list[i] なので list[0]
イ list[num+i] なので list[7+0]
ウ list1[num1+i] なので list1[3+0]
エ list1[num2+i] なので list1[4+0]
上記からアとイがNGだと判ります。
ア：list[0]はslist1に入るべきデータであるためNG
イ：添字が0始まりのため、list[7]は配列の範囲を超えてしまっているためNG
したがって、答えはウかエになります。
i=3のとき
次にiの上限値であるi=3を代入します。
ア list[i] なので list[3]
イ list[num+i] なので list[7+3]
ウ list1[num1+i] なので list1[3+3]
エ list1[num2+i] なので list1[4+3]
上記からア、イに加えてエもNGだと判ります。
エ：添字が0始まりのため、list[7]は配列の範囲を超えてしまっているためNG
したがって正解はウであると判ります。
正解：ウ
設問1 c
cに関する解答群として、下記8択が与えられています。
ア (i < num1) and (j < num2)
イ (i < num1) or (j < num2)
ウ (j < num1) and (i < num2)
エ (j < num1) or (i < num2)
オ (i + j) < (num1 + num2)
カ (i + j) ≦ (num1 + num2)
キ (i + j) > (num1 + num2)
ク (i + j) ≧ (num1 + num2)
何をやっているか読んでみる
問題文中の空欄cはp. 45の[プログラム]の下図Mergeプログラム中にあります。
疑似言語の記述形式を確認すると、空欄cは前判定繰り返し処理の条件式であることが判ります。
繰り返し処理の中にもう1つ条件式があり、slist1[i] < slist2[j]の真偽に応じて処理を分岐させています。
ここから以下のことが判ります。
変数iはslist1, jはslist2の範囲外の数を取ることはない。
slist1, slist2の範囲についてはp. 44の「表2 Mergeの引数の仕様」を確認します。
表2から、slist1のデータの個数はnum1, slist2のデータの個数はnum2です。
bを解くときに確認した通り、今回の問題では配列の添え字は0から始まります。
つまり、slist1の最後はslist[num1 - 1], slist2の最後はslist[num2 - 1]になります。
ここから、i < num1 かつ j < num2 である必要があることが判ります。
したがって、正解はアであると判ります。
正解：ア
設問2
設問2は下図のような問題です。
p. 45のSortプログラムを参照し、αを確認します。
αはMergeプログラムを実行した直後であることが判ります。
図を書いて問題を解く
p. 44に整列処理の流れの図があります。
今回はMergeプログラムによる値の移り変わりを解答するので、対象範囲は下図になります。
配列listのデータが5, 7, 4, 2, 3, 8, 1のときの整列処理を図にすると下図のようになります。
図 設問2の整列処理の流れ（問題文を参照し筆者作図）
そのうち、Merge処理に対応するのは下図の部分になります。
作成した図と回答の選択肢を見比べると、ウが正解であることが判ります。
正解：ウ
設問3
設問3は下図のような問題です。
βの出現箇所を確認すると、p. 45のMergeプログラムの後半箇所です。
解答群の処理を確認する
解答群ア～エの処理を確認し、おかしなところがある処理は選択肢から除外できそうです。
ア
設問アの処理内容を確認します。
前半の処理でslist1[i]をlist[i]に、後半の処理でslist2[j]をlist[j]に代入しています。
i <> jになることが保証されていないので、後半の処理で前半の処理を上書きしてしまう可能性があります。
したがって、アは除外できそうです。
イ
設問イの処理内容を確認します。
j < num2からjの取れる最大値はnum2 - 1と判ります。
設問1bで確認した通り、num2はnum - num / 2です。
したがって、j + num2の最大値は以下となります。
numが偶数のとき：num - 1
numが奇数のとき：num
添え字が0始まりなので、numが奇数のときlist[j+num2]でlistの範囲外にアクセスする可能性があります。
したがって、イは除外できそうです。
ウ
設問ウの処理内容を確認します。
list[j+num1]に代入する処理でi, list[i+num2]に代入する処理でjをインクリメントしています。
代入先が変わらず、j+num1-1番目とi+num2-1番目に繰り返し代入されています。
したがって、ウは除外できそうです。
エ
設問エの処理内容を確認します。
num1 + num2はnum以下の値を取ります。
i < num1, j < num2の条件から、list[i+num2], list[j+num1]はnum-1以下の値を取ります。
したがって、範囲外にアクセスすることはありません。
選択肢エは解答候補として残りそうです。
Mergeプログラムをトレースする
本番の試験で時間がない場合は選択肢の消去法で設問3の答えをエにしても良いかと思いますが、今回はMergeプログラムの処理内容を確認しておくことにします。
Mergeプログラムを再掲します。
ここで、空欄cは設問1 cから下記になります。
ア (i < num1) and (j < num2)
整列処理の流れの図の下図部分を使いながら、Mergeプログラムの処理内容を追いかけてみましょう。
開始前
上図の時点での値はそれぞれ下記になります。
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ , , , , , , ]
num1: 3
num2: 4
i: 0
j: 0
上半分の処理ブロック
まずは下図の上半分の処理ブロックについて見ていきましょう。
処理内容を1行ずつ追いかけているため、以下長文となります。
不要な方は読み飛ばしていただいて構いません。
上半分の処理ブロックのトレース
1周目
- 条件式に値を代入すると(0 < 3) and (0 < 4)となるため処理ブロック内へ進む
- slist1[0] = 4, slist2[0] = 1のため下図の下半分の処理に進む
- list[0 + 0]にslist2[0]すなわち1を代入
- jを1つインクリメント
1周目時点での値はそれぞれ下記になります。
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, , , , , , ]
num1: 3
num2: 4
i: 0
j: 1
2周目
- 条件式に値を代入すると(0 < 3) and (1 < 4)となるため処理ブロック内へ進む
- slist1[0] = 4, slist2[1] = 2のため下図の下半分の処理に進む
- list[0 + 1]にslist2[1]すなわち2を代入
- jを1つインクリメント
2周目時点での値はそれぞれ下記になります。
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, , , , , ]
num1: 3
num2: 4
i: 0
j: 2
3周目
- 条件式に値を代入すると(0 < 3) and (2 < 4)となるため処理ブロック内へ進む
- slist1[0 + 2] = 4, slist2[2] = 3のため下図の下半分の処理に進む
- list[2]にslist2[2]すなわち3を代入
- jを1つインクリメント
3周目時点での値はそれぞれ下記になります。
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, 3, , , , ]
num1: 3
num2: 4
i: 0
j: 3
4周目
- 条件式に値を代入すると(0 < 3) and (3 < 4)となるため処理ブロック内へ進む
- slist1[1] = 4, slist2[3] = 8のため下図の上半分の処理に進む
- list[0 + 3]にslist1[0]すなわち4を代入
- iを1つインクリメント
4周目時点での値はそれぞれ下記になります。
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, 3, 4, , , ]
num1: 3
num2: 4
i: 1
j: 3
5周目
- 条件式に値を代入すると(0 < 3) and (3 < 4)となるため処理ブロック内へ進む
- slist1[1] = 5, slist2[3] = 8のため下図の上半分の処理に進む
- list[1 + 3]にslist1[1]すなわち5を代入
- iを1つインクリメント
5周目時点での値はそれぞれ下記になります。
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, 3, 4, 5, , ]
num1: 3
num2: 4
i: 2
j: 3
6周目
- 条件式に値を代入すると(1 < 3) and (3 < 4)となるため処理ブロック内へ進む
- slist1[2] = 7, slist2[3] = 8のため下図の上半分の処理に進む
- list[2 + 3]にslist1[2]すなわち7を代入
- iを1つインクリメント
6周目時点での値はそれぞれ下記になります。
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, 3, 4, 5, 7, ]
num1: 3
num2: 4
i: 3
j: 3
7周目
- 条件式に値を代入すると(3 < 3) and (3 < 4)となるため、上半分の処理ブロックを終了
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, 3, 4, 5, 7, ]
num1: 3
num2: 4
i: 3
j: 3
slist2[3]を除きlist[]にマージされています。
下半分の処理ブロック（β）は、どうやら最後の1要素をマージするための処理らしいと判ります。
下半分の処理ブロック
続いて、下図の処理をトレースしてみましょう。
1周目
- 条件式に値を代入すると(3 < 3) or (3 < 4)となるため処理ブロック内へ進む
- 条件式に値を代入すると3 < 3となるため下半分の処理に進む
- list[3 + 3]にslist2[3]すなわち8を代入
- jを1つインクリメント
1周目時点での値はそれぞれ下記になります。
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, 3, 4, 5, 7, 8]
num1: 3
num2: 4
i: 3
j: 4
2周目
- 条件式に値を代入すると(3 < 3) or (4 < 4)となるため処理ブロックに入らず、処理終了
2周目時点での値はそれぞれ下記になります。
※1周目と変わらず
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, 3, 4, 5, 7, 8]
num1: 3
num2: 4
i: 3
j: 4
下半分の処理ブロック終了時点でマージが完了することが判ります。
設問3解答エをトレースする
上半分の処理ブロックが終了した時点での下図値を用いて、設問3解答エをトレースしてみましょう。
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, 3, 4, 5, 7, ]
num1: 3
num2: 4
i: 3
j: 3
これにより、エで副プログラムMergeのβ部分と同じ結果を得られることが確認できます。
エを再掲します。
1周目
- 条件式 i < num1 に値を代入すると3 < 3となるため上半分の処理ブロックには入らない
- 条件式 j < num2 に値を代入すると3 < 4となるため下半分の処理ブロックには入る
- list[3 + 3]にslist2[3]すなわち8を代入
- jを1つインクリメント
1周目時点での値はそれぞれ下記になります。
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, 3, 4, 5, 7, 8]
num1: 3
num2: 4
i: 3
j: 4
2周目
- 条件式 i < num1 に値を代入すると3 < 3となるため上半分の処理ブロックには入らない
- 条件式 j < num2 に値を代入すると4 < 4となるため下半分の処理ブロックにも入らず終了
2周目時点での値はそれぞれ下記になります。
※1周目と変わらず
slist1[]: [4, 5, 7]
slist2[]: [1, 2, 3, 8]
list[]: [ 1, 2, 3, 4, 5, 7, 8]
num1: 3
num2: 4
i: 3
j: 4
下半分の処理ブロック終了時点でマージが完了し、βと同じ結果を得られることが確認できます。
したがって、解答エが正解だと判ります。
正解：エ
おわりに
以上で解説を終わります。
お付き合いいただきありがとうございました。
皆様の合格をお祈りいたします。
出典
筆者作図のものを除き、本文中の画像は平成22年度 春期 基本情報技術者試験 午後 共通に使用される疑似言語の記述形式及び設問8から引用しています。