線形探索｜擬似言語のトレース解説と練習問題
関数 find は、配列 data を先頭から順に調べ、target と等しい最初の要素の要素番号を返す。見つからなければ 0 を返す。配列の要素番号は 1 から始まる。
プログラム
| 1 | ○整数型: find(整数型の配列: data, 整数型: target) |
| 2 | 整数型: i ← 1 |
| 3 | while (i ≦ dataの要素数 and data[i] ≠ target) |
| 4 | i ← i ＋ 1 |
| 5 | endwhile |
| 6 | if (i ≦ dataの要素数) |
| 7 | return i |
| 8 | endif |
| 9 | return 0 |
何をしているか
配列を先頭から1つずつ調べ、目的の値と等しい要素が見つかったら、その位置を返します。条件は「まだ配列の中にいる」かつ「目的の値ではない」の2つを and でつないでいます。
トレースのコツ
- 繰返しを抜ける理由は2つあります。見つかったか、配列の終わりを過ぎたかです。抜けたあとの
iで、どちらだったかを見分けます。 iを進める回数は、「目的の値より前にある要素の数」と同じです。- 条件式が評価される回数は、
iを進める回数より1回多くなります。最後に偽になる回があるからです。
よくある間違い
- 戻り値を、見つけた値で答える。返すのは要素番号です。
- 条件の2つの順番を気にしない。左の「i ≦ 要素数」を先に調べるので、範囲の外の要素を見にいかずに済んでいます。
- 見つからなかったときの
iを「要素数」と答える。実際は「要素数 ＋ 1」になって繰返しを抜けます。
例題：find({6, 12, 20, 5, 15}, 15) を最後まで追う
上のプログラムを find({6, 12, 20, 5, 15}, 15) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。
| # | 行 | したこと | data | target | i |
|---|---|---|---|---|---|
| 1 | 2 | 宣言 | {6, 12, 20, 5, 15} | 15 | 1 |
| 2 | 3 | 条件判定（真） | {6, 12, 20, 5, 15} | 15 | 1 |
| 3 | 4 | 代入 | {6, 12, 20, 5, 15} | 15 | 2 |
| 4 | 3 | 条件判定（真） | {6, 12, 20, 5, 15} | 15 | 2 |
| 5 | 4 | 代入 | {6, 12, 20, 5, 15} | 15 | 3 |
| 6 | 3 | 条件判定（真） | {6, 12, 20, 5, 15} | 15 | 3 |
| 7 | 4 | 代入 | {6, 12, 20, 5, 15} | 15 | 4 |
| 8 | 3 | 条件判定（真） | {6, 12, 20, 5, 15} | 15 | 4 |
| 9 | 4 | 代入 | {6, 12, 20, 5, 15} | 15 | 5 |
| 10 | 3 | 条件判定（偽） | {6, 12, 20, 5, 15} | 15 | 5 |
| 11 | 6 | 条件判定（真） | {6, 12, 20, 5, 15} | 15 | 5 |
| 12 | 7 | 戻る（5） | {6, 12, 20, 5, 15} | 15 | 5 |
この例題で問われること
問 find({6, 12, 20, 5, 15}, 15) を呼び出したときの戻り値はどれか。
答え 5
- 戻り値になる i は、1 → 2 → 3 → 4 → 5 と変わります。
- 7行目で返す時点の値 5 が答えです。
問 3行目の条件式が評価される回数はどれか。
答え 5
- 3行目の条件式は5回評価され、真が4回、偽が1回です。
問 4行目を4回目に実行した直後の、変数 i の値はどれか。
答え 5
- 4行目は全部で4回実行されます。
- 実行した直後の i は、順に 2 → 3 → 4 → 5 です。
- 4回目の直後なので、答えは 5 です。
練習問題 標準（10問）
本試験と同じくらいの量。レベル：入門
- 問題01 find({5, 12, 18, 6, 17, 9, 15, 11}, 9)
- 問題02 find({17, 4, 3, 19, 8, 7}, 8)
- 問題03 find({8, 10, 19, 16, 20, 15, 6}, 16)
- 問題04 find({4, 20, 17, 1, 3, 15, 16, 5}, 17)
- 問題05 find({9, 2, 16, 4, 1, 15, 6, 20}, 6)
- 問題06 find({4, 1, 13, 14, 8, 11, 15, 7}, 7)
- 問題07 find({19, 12, 15, 7, 10, 18, 1}, 18)
- 問題08 find({19, 18, 10, 1, 13, 4, 7, 16}, 4)
- 問題09 find({16, 18, 8, 10, 13, 11}, 13)
- 問題10 find({5, 3, 19, 6, 2, 8, 12, 16}, 8)
もっと解く（追加の20問）
- 問題11 find({20, 14, 17, 19, 15, 5, 1, 10}, 19)
- 問題12 find({4, 16, 8, 10, 9, 20, 11, 6}, 8)
- 問題13 find({18, 10, 15, 8, 2, 17}, 17)
- 問題14 find({4, 8, 18, 2, 16, 9, 12}, 12)
- 問題15 find({6, 2, 4, 11, 10}, 4)
- 問題16 find({11, 1, 9, 10, 15}, 9)
- 問題17 find({16, 3, 19, 14, 12, 11, 13}, 14)
- 問題18 find({7, 14, 5, 13, 2, 3, 12}, 12)
- 問題19 find({8, 2, 9, 14, 1, 10, 16, 20}, 10)
- 問題20 find({5, 9, 16, 4, 17, 6}, 6)
- 問題21 find({2, 13, 20, 19, 11, 17, 18}, 11)
- 問題22 find({20, 10, 19, 13, 7}, 13)
- 問題23 find({14, 5, 17, 7, 15, 13, 8}, 13)
- 問題24 find({18, 7, 1, 10, 4, 11, 6, 12}, 11)
- 問題25 find({7, 12, 8, 18, 6, 3, 17, 10}, 10)
- 問題26 find({1, 19, 14, 9, 4, 3, 10, 2}, 4)
- 問題27 find({12, 3, 10, 11, 4, 7, 2, 9}, 4)
- 問題28 find({13, 9, 6, 12, 8, 11, 1, 4}, 4)
- 問題29 find({9, 20, 7, 14, 8, 1, 3, 16}, 8)
- 問題30 find({10, 11, 20, 12, 2, 3}, 3)