基本情報技術者試験【午後】のアルゴリズムの解き方

目次

1. はじめに
2. 疑似言語の記述形式
3. サンプル問題
4. アルゴリズム問題の解き方
5. おわりに

1. はじめに

基本情報技術者試験の午後試験で出題されるアルゴリズムの問題の解き方を解説します。
解き方は問題のアルゴリズムを１行づつ丁寧に分析していくというもので時間がかかりますが、確実に理解でき、また、慣れれば高速化できます。

2023年度から試験方法が変わり、アルゴリズム問題も問題量等に変更がありますが解き方自体は変わらないため解説します。
解説する問題はIPAにて公開されているサンプル問題を用います。
詳細は下記リンクを参照してください。

基本情報技術者試験（科目B試験）サンプル問題（20問）セット

情報処理技術者試験における出題範囲・シラバス等の変更内容の公表について

2. 疑似言語の記述形式

アルゴリズムは疑似言語で記載されるため、問題の最初に下図のように読み方が記載されています。
アルゴリズムの問題はこれを理解していることが前提になります。

3. サンプル問題

IPAのサンプル問題集の下図の問題を使用します。

4. アルゴリズム問題の解き方

この問題は無限ループする不具合が出るのでその条件を特定するというものです。
全ての解答群の条件でプログラムに当てはめることで解けます。
どの解答の場合に無限ループになるか分かればよいので、解答群をプログラムに当てはめて無限ループになる解答を探します。
順番に解いてみましょう。
解き方は[プログラム]の１行１行に数字や条件を代入していきます。
練習の時は時間がかかってもできるだけ細かく書いて解き方を覚えることを優先しましょう。
解けるようになればおのずと早くなります。

解答ア

【ア　要素数が１で、targetがその要素の値と等しい】
・「data」というリストの格納している数字は未定、かつ、一つしか入っていない。
→　格納している数字が未定のため、ここでは「target」と同一の「1」にする。
・「target」は「1」

serach(data[1], target = 1)

low = 1
high = 1 (dataの要素数)

while (1(low) <= 1(high))
    whileの条件：True
    middle = (1 + 1) // 2 = 1    /* (low + high) ÷　2　の商 */
    if (1(data[middle]) < 1(target)) 
    /* data[middle] = data[1] = dataリスト内の１番目の要素 */
    ifの条件：False、次のelse ifへ進む
    else if (1(data[middle]) > 1(target))     
    else ifの条件：False、次のelseへ進む
    else
        return 1(middle)    

無限ループせずに正しい回答を返したため「ア」は不適切

解答イ

【イ　要素数が２で、targetがdataの先頭要素の値と等しい】
・「data」というリストの格納している数字は未定、かつ、二つ入っている。
→　格納している数字が未定のため、ここでは「1, 2」にする。
・「target」はdataの先頭要素の値と等しいため「1」

serach(data[1, 2], target = 1)

low = 1
high = 2 (dataの要素数)

while (1(low) <= 2(high))
    whileの条件：True
    middle = (1 + 2) // 2 = 1    /* (low + high) ÷　2　の商 */
    if (1(data[middle]) < 1(target)) 
    /* data[middle] = data[1] = dataリスト内の１番目の要素 */
    ifの条件：False、次のelse ifへ進む
    else if (1(data[middle]) > 1(target))     
    else ifの条件：False、次のelseへ進む
    else
        return 1(middle)    

無限ループせずに正しい回答を返したため「イ」は不適切

解答ウ

【ウ　要素数が２で、targetがdataの末尾要素の値と等しい】
・「data」というリストの格納している数字は未定、かつ、二つ入っている。
→　格納している数字が未定のため、ここでは「1, 2」にする。
・「target」はdataの末尾要素の値と等しいため「2」

serach(data[1, 2], target = 2)

low = 1
high = 2 (dataの要素数)

while (1(low) <= 2(high))
    whileの条件：True
    middle = (1 + 2) // 2 = 1    /* (low + high) ÷　2　の商 */
    if (1(data[middle]) < 2(target)) 
    /* data[middle] = data[1] = dataリスト内の１番目の要素 */
    ifの条件：True
        low = 1(middle)
while (1(low) <= 2(high))
    whileの条件：True
    middle = (1 + 2) // 2 = 1    /* (low + high) ÷　2　の商 */
    if (1(data[middle]) < 2(target)) 
    /* data[middle] = data[1] = dataリスト内の１番目の要素 */
    ifの条件：True
        low = 1(middle)
～　以下無限ループ　～  

無限ループしたため「ウ」が答え

解答エ

【エ　要素に-1が含まれている】
・「data」というリストの格納している数字は-1のみ確定、かつ、いくつ含んでいるか未定。
→　要素に-1が含まれていること以外が未定のため、無限ループしなかった「ア」の条件に合わせる
→　無限ループしなかった条件に合わせないと無限ループする場合がある。
→　dataの要素数は１、かつ格納している数字は[-1]。
・「target」は未定のためdataの格納している数字の「-1」にする。

serach(data[-1], target = -1)

low = 1
high = 1 (dataの要素数)

while (1(low) <= 1(high))
    whileの条件：True
    middle = (1 + 1) // 2 = 1    /* (low + high) ÷　2　の商 */
    if (-1(data[middle]) < -1(target)) 
    /* data[middle] = data[1] = dataリスト内の１番目の要素 */
    ifの条件：False、次のelse ifへ進む
    else if (-1(data[middle]) > -1(target))     
    else ifの条件：False、次のelseへ進む
    else
        return 1(middle)    

無限ループせずに正しい回答を返したため「エ」は不適切

5. おわりに

アルゴリズムは最初に見たときは全く分からなかったのですが、１行１行を丁寧に紙に書いてプログラムをトレースすることで理解できるようになりました。
python等のアルゴリズム問題も同様に解答を導き出せるため、応用が利きます。
面倒くさいやり方ではありますが、「急がば回れ」です。
確実に読解力・理解力が向上します。
何度も１行づつ丁寧に紙に書いていると、自分なりのやり方もできてきますので試してみてください。
宜しくお願い致します。