整列済みの配列の併合｜擬似言語のトレース解説と練習問題
関数 merge は、昇順に並んだ二つの配列 a と b を、昇順を保ったまま一つの配列にまとめて返す。配列の要素番号は 1 から始まる。
プログラム
| 1 | ○整数型の配列: merge(整数型の配列: a, 整数型の配列: b) |
| 2 | 整数型の配列: c ← {} |
| 3 | 整数型: i ← 1 |
| 4 | 整数型: j ← 1 |
| 5 | while (i ≦ aの要素数 and j ≦ bの要素数) |
| 6 | if (a[i] ≦ b[j]) |
| 7 | cの末尾に a[i] を追加する |
| 8 | i ← i ＋ 1 |
| 9 | else |
| 10 | cの末尾に b[j] を追加する |
| 11 | j ← j ＋ 1 |
| 12 | endif |
| 13 | endwhile |
| 14 | while (i ≦ aの要素数) |
| 15 | cの末尾に a[i] を追加する |
| 16 | i ← i ＋ 1 |
| 17 | endwhile |
| 18 | while (j ≦ bの要素数) |
| 19 | cの末尾に b[j] を追加する |
| 20 | j ← j ＋ 1 |
| 21 | endwhile |
| 22 | return c |
何をしているか
i は a の、j は b の「まだ移していない先頭」を指します。2つの先頭を比べ、小さいほうを c の末尾に移して、その番号を 1 進めます。どちらかを移し終えたら、残りをそのまま末尾に移します。
トレースのコツ
- 表には
i、j、cを書きます。1回の繰返しで進むのはiかjのどちらか一方だけです。 - 最初の while が終わった時点で、
iとjのどちらが範囲を超えたかを確かめます。 - 残り2つの while のうち、実際に回るのは片方だけです。
よくある間違い
- 値が等しいときにどちらを取るかを読み違える。
≦なのでaを先に取ります。 - 最初の while の条件式が評価される回数を、移した要素の数と同じにしてしまう。偽になる最後の1回があります。
andの右側が評価されない場合を見落とす。左が偽なら、右は評価されません。
例題：merge({4, 5, 6}, {2, 5}) を最後まで追う
上のプログラムを merge({4, 5, 6}, {2, 5}) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。
| # | 行 | したこと | a | b | c | i | j |
|---|---|---|---|---|---|---|---|
| 1 | 2 | 宣言 | {4, 5, 6} | {2, 5} | {} | — | — |
| 2 | 3 | 宣言 | {4, 5, 6} | {2, 5} | {} | 1 | — |
| 3 | 4 | 宣言 | {4, 5, 6} | {2, 5} | {} | 1 | 1 |
| 4 | 5 | 条件判定（真） | {4, 5, 6} | {2, 5} | {} | 1 | 1 |
| 5 | 6 | 条件判定（偽） | {4, 5, 6} | {2, 5} | {} | 1 | 1 |
| 6 | 10 | 追加 | {4, 5, 6} | {2, 5} | {2} | 1 | 1 |
| 7 | 11 | 代入 | {4, 5, 6} | {2, 5} | {2} | 1 | 2 |
| 8 | 5 | 条件判定（真） | {4, 5, 6} | {2, 5} | {2} | 1 | 2 |
| 9 | 6 | 条件判定（真） | {4, 5, 6} | {2, 5} | {2} | 1 | 2 |
| 10 | 7 | 追加 | {4, 5, 6} | {2, 5} | {2, 4} | 1 | 2 |
| 11 | 8 | 代入 | {4, 5, 6} | {2, 5} | {2, 4} | 2 | 2 |
| 12 | 5 | 条件判定（真） | {4, 5, 6} | {2, 5} | {2, 4} | 2 | 2 |
| 13 | 6 | 条件判定（真） | {4, 5, 6} | {2, 5} | {2, 4} | 2 | 2 |
| 14 | 7 | 追加 | {4, 5, 6} | {2, 5} | {2, 4, 5} | 2 | 2 |
| 15 | 8 | 代入 | {4, 5, 6} | {2, 5} | {2, 4, 5} | 3 | 2 |
| 16 | 5 | 条件判定（真） | {4, 5, 6} | {2, 5} | {2, 4, 5} | 3 | 2 |
| 17 | 6 | 条件判定（偽） | {4, 5, 6} | {2, 5} | {2, 4, 5} | 3 | 2 |
| 18 | 10 | 追加 | {4, 5, 6} | {2, 5} | {2, 4, 5, 5} | 3 | 2 |
| 19 | 11 | 代入 | {4, 5, 6} | {2, 5} | {2, 4, 5, 5} | 3 | 3 |
| 20 | 5 | 条件判定（偽） | {4, 5, 6} | {2, 5} | {2, 4, 5, 5} | 3 | 3 |
| 21 | 14 | 条件判定（真） | {4, 5, 6} | {2, 5} | {2, 4, 5, 5} | 3 | 3 |
| 22 | 15 | 追加 | {4, 5, 6} | {2, 5} | {2, 4, 5, 5, 6} | 3 | 3 |
| 23 | 16 | 代入 | {4, 5, 6} | {2, 5} | {2, 4, 5, 5, 6} | 4 | 3 |
| 24 | 14 | 条件判定（偽） | {4, 5, 6} | {2, 5} | {2, 4, 5, 5, 6} | 4 | 3 |
| 25 | 18 | 条件判定（偽） | {4, 5, 6} | {2, 5} | {2, 4, 5, 5, 6} | 4 | 3 |
| 26 | 22 | 戻る（{2, 4, 5, 5, 6}） | {4, 5, 6} | {2, 5} | {2, 4, 5, 5, 6} | 4 | 3 |
この例題で問われること
問 merge({4, 5, 6}, {2, 5}) を呼び出したときの戻り値はどれか。
答え {2, 4, 5, 5, 6}
- 戻り値になる c は、{} → {2} → {2, 4} → {2, 4, 5} → {2, 4, 5, 5} → {2, 4, 5, 5, 6} と変わります。
- 22行目で返す時点の値 {2, 4, 5, 5, 6} が答えです。
問 5行目の条件式が評価される回数はどれか。
答え 5
- 5行目の条件式は5回評価され、真が4回、偽が1回です。
問 7行目が実行される回数はどれか。
答え 2
- 7行目が実行されるのは、6行目の条件が真になったときだけです。
- 6行目の条件は4回評価され、真になるのは2回です。したがって 7行目は2回実行されます。
問 10行目を1回目に実行した直後の、変数 i の値はどれか。
答え 1
- 10行目は全部で2回実行されます。
- 実行した直後の i は、順に 1 → 3 です。
- 1回目の直後なので、答えは 1 です。
練習問題 標準（10問）
本試験と同じくらいの量。レベル：中級
- 問題01 merge({5, 8}, {2, 6, 7})
- 問題02 merge({1, 6, 8}, {5, 6, 7})
- 問題03 merge({3, 8}, {2, 4})
- 問題04 merge({1, 2, 4}, {3, 4, 5})
- 問題05 merge({2, 5, 8}, {1, 6})
- 問題06 merge({2, 9}, {1, 3, 9})
- 問題07 merge({3, 5}, {2, 3, 4})
- 問題08 merge({1, 7}, {1, 6, 9})
- 問題09 merge({4, 7, 8}, {3, 7})
- 問題10 merge({2, 3, 4}, {2, 6})
もっと解く（追加の20問）
- 問題11 merge({1, 5, 7}, {6, 8, 9})
- 問題12 merge({3, 6, 7}, {1, 3, 5})
- 問題13 merge({1, 3, 9}, {1, 2, 9})
- 問題14 merge({4, 6, 8}, {1, 2, 6})
- 問題15 merge({4, 6, 7}, {1, 6, 8})
- 問題16 merge({3, 4, 7}, {6, 7, 9})
- 問題17 merge({4, 6}, {2, 4, 5})
- 問題18 merge({1, 3, 5}, {1, 9})
- 問題19 merge({8, 9}, {1, 8, 9})
- 問題20 merge({4, 9}, {3, 7, 8})
- 問題21 merge({6, 7, 9}, {1, 8})
- 問題22 merge({2, 4, 6}, {5, 9})
- 問題23 merge({3, 5}, {1, 4, 8})
- 問題24 merge({2, 4, 6}, {1, 5})
- 問題25 merge({6, 8, 9}, {5, 7})
- 問題26 merge({3, 5, 7}, {1, 2, 5})
- 問題27 merge({1, 5, 6}, {2, 3, 9})
- 問題28 merge({4, 8}, {1, 7, 8})
- 問題29 merge({1, 6, 9}, {3, 4, 9})
- 問題30 merge({5, 7, 9}, {3, 4, 7})