コンピュータ演習II 第12回 ドリル（授業中に解いて提出）

この問題集は、授業中に、解説を聞きながら自分の手を動かして解く 練習です。第12回の教材で学んだ 探索アルゴリズム（線形探索と二分探索） を、各節 1〜2 問ずつ練習します。

各問は「好きな値で入力を作り、こう処理してください」という形です。入力のリストは自分で自由に作ってください。作り方は各問の「入力の作り方」に示します。

進め方は次のとおりです。

• 配布の 解答用テンプレート 2xBxxxxx_12_drill.ipynb を Colab で開き、各問題の「入力の作り方」に従って自分でリストを作り、その下に処理を書いて実行してください。
• 各問に 入力例と出力例 を載せています。イメージがつかめないときは、まず入力例のとおりに動かしてから、自分の値に変えてください。
• 各問題に ヒントのフローチャート を載せていますが、一部 空欄（？①や？②）のブロックがあります。空欄に入る内容を自分で考えてみてください。フローチャートを完成させて流れをつかんでから、それを Python に翻訳して書いてください。ヒント図の変数名は例です。自分でつけた名前に読み替えてください。
• できたら、テンプレートを .py 形式でダウンロードして提出 してください。答え合わせはしません。自分で入力を決めて、思ったとおりに動くかを確かめることが目的です。
• わからなくなったら、第12回の教材を見返してかまいません。答えを写すのではなく、書き方を思い出して自分で書く ことが大切です。

なお、この演習では Colab のコード生成（生成AI の補完）は使わないでください。自分でプログラムを書いて、読めるようになることが目的です。今回の授業後の課題は フローチャートツールで組んで提出 するので、ヒント図の「構造」を読み取る練習も兼ねています。

なお、Flowchart Maker を使用してフローチャートを作成すると理解が深まります。

1. 線形探索

問題 1: 出現回数を数える

好きな整数を5 個入れたリストを numbers という名前で作り、その中に入れた値のどれかを target としてください（同じ値を2 回以上入れておくと確かめやすいです）。numbers の中に target が 何回あるか を count に数え、ループが終わったら count を出力してください。第06回で学んだ「数える」パターンの復習です。

入力の作り方:

numbers = [好きな整数を5 個]
target = リストに入れた値のどれか
count = 0

入力例:

numbers = [5, 3, 8, 3, 7]
target = 3

出力例（入力例のとき）:

2

これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。

考えるポイント: 「target と等しいたびに数える」は、どんな条件式で書けるでしょうか。ヒント図は if の条件が空欄？①です。

フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。

ヒント（フローチャート）:

---

問題 2: 最後に見つかった位置

問題1 と同じ numbers と target を使ってください。見つかった位置を入れる変数 pos を -1 から始め、target と等しい要素を見つける たびに 位置を記録して、ループが終わったら pos を出力してください。target が2 か所以上にあるとき、最後に見つかった位置 が出力されることを確かめてください。

入力の作り方:

問題1 と同じ numbers と target
pos = -1

入力例:

numbers = [5, 3, 8, 3, 7]
target = 3

出力例（入力例のとき）:

3

これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。

考えるポイント: 見つかるたびに上書きすると、なぜ「最後の位置」が残るのでしょうか。ヒント図は True 側の処理が空欄？①です。

フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。

ヒント（フローチャート）:

---

2. 見つかった後は比べない

問題 3: 最初の位置と比較回数

問題1 と同じ numbers と target を使ってください。こんどは 最初に見つかった位置 を求めます。教材3 章のとおり、ガード（まだ見つかっていないときだけ通す外側の if）の中で target と比べ、比べる直前に compare_count を1 増やしてください。ループが終わったら pos と compare_count をそれぞれ出力してください（出力は全部で2 行）。

入力の作り方:

問題1 と同じ numbers と target
pos = -1
compare_count = 0

入力例:

numbers = [5, 3, 8, 3, 7]
target = 3

出力例（入力例のとき）:

1
2

これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。

考えるポイント: ガード（外側の if）の条件は何でしょうか。「まだ見つかっていない」を pos の値で表します。ヒント図はガードの条件が空欄？①です。

フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。

ヒント（フローチャート）:

---

3. 二分探索

問題 4: 二分探索の動きを観察する

小さい順に並べた 好きな整数を5 個入れたリストを numbers という名前で作り、その中の値のどれかを target としてください。教材4 章の二分探索で target を探します。ただし、調べた位置が見えるように、mid を計算した直後に mid を出力する行を入れてください。ループが終わったら pos も出力してください。範囲が半分ずつに絞られていく様子を確かめてください。

入力の作り方:

numbers = [小さい順に並べた好きな整数を5 個]
target = リストに入れた値のどれか

入力例:

numbers = [2, 4, 6, 8, 9]
target = 8

出力例（入力例のとき）:

2
3
3

上の2 行が調べた位置（mid）、最後の1 行が pos です。これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。

考えるポイント: 真ん中の位置 mid は、low と high からどう計算するのでしょうか（割り算の種類にも注意）。ヒント図は mid の計算が空欄？①です。

フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。

ヒント（フローチャート）:

---

問題 5: 二分探索の比較回数

問題4 と同じ numbers と target を使ってください。観察用の出力の代わりに、比較回数 を compare_count に数えます。ループが終わったら pos と compare_count をそれぞれ出力してください（出力は全部で2 行）。同じ target を線形探索（問題3 の形）で探した場合と、回数を比べてみてください。

入力の作り方:

問題4 と同じ numbers と target
compare_count = 0

入力例:

numbers = [2, 4, 6, 8, 9]
target = 8

出力例（入力例のとき）:

3
2

これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。

考えるポイント: 数える1 行はどこに置けばよいでしょうか。「範囲が残っていて、実際に比べた周回」だけを数えます。ヒント図は数える処理が空欄？①です。

フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。

ヒント（フローチャート）:

---

問題 6: 見つからない値を探す

問題4 と同じリスト numbers で、こんどは リストに無い値 を target にして、二分探索で探してください。ループが終わったら pos を出力してください。見つからないとき、pos が はじめの値のまま 出力されることを確かめてください。

入力の作り方:

問題4 と同じ numbers
target = リストに無い値

入力例:

numbers = [2, 4, 6, 8, 9]
target = 5

出力例（入力例のとき）:

-1

これは例です。自分で決めた値で作ってかまいません（その場合、出力は例とは変わります）。

考えるポイント: pos のはじめの値は何にすればよいでしょうか。「見つからなかった」がひと目で分かる値を選びます。ヒント図は pos のはじめの値が空欄？①です。

フローチャートの？①に入る内容を考えて、図を完成させてから Python に翻訳してください。

ヒント（フローチャート）:

---

まとめ

この回のドリルでは、第12回で学んだ2 つの探索アルゴリズムを、教材の例から一歩ずらした形で練習しました。次のパターンを、見なくても書けるようにしておきましょう。

• 線形探索の骨格: for で先頭から順に、if numbers[j] == target:。「何回あるか」は count、「どこにあるか」は pos に記録する。
• pos = -1: 「見つからなかった」の合図。0 以上は位置と区別が付かないので -1 を使う。
• ガード: if pos == -1: を外側にかぶせると「見つかった後は何もしない」が作れる。比較回数はガードの中で数える。
• 二分探索の骨格: low・high で範囲を持ち、mid = (low + high) // 2 と比べて if-elif-else で範囲を半分に絞る。見つかったら low = high + 1 で範囲を空にする。ループは for k in range(0, n): の安全な上限で回す。
• 2 つの探索の対比: 線形は最悪 n 回、二分は「半分にできる回数」。ただし二分探索は 昇順に整列済み のリスト専用。

授業後の 課題 では、これらを自分の学籍番号から作るリストで、フローチャートツールで組んで 解きます。ここで骨格を手に入れておきましょう。