IP02-08 実践プログラム①　探索アルゴリズム　線形探索

情報活用編プラス

第3章「コンピュータとプログラミング」

IP02-08

実践プログラム①　探索アルゴリズム　線形探索

7 フローチャートからPythonコードへ

8 ✏️Pythonで線形探索プログラムを作ろう

9 ✏️Pythonで線形探索のプログラムを作ろう2

Pythonで線形探索のプログラムを作ろう2

学習の目的

・番兵法(ばんぺいほう)とは
・番兵法を使ったプログラムを完成させよう

線形探索には番兵法(ばんぺいほう)という方法があります。

1. 番兵法を使ったプログラム

線形探索のアルゴリズムの一つに「番兵法」があります。

番兵ってなにか強そうな感じがする。

でも、守ってくれそう。

そうですよね。でもイメージは合っています。番兵が比較を止めてくれる役割をしてくれます。

それではどうやって比較を止めてくれるか、仕組みを学習しましょう。

番兵法とは、探索する値を配列の最後に追加する方法です。

そのため、データを探索すると必ずデータが見つかります。

なるほど、これまで配列内に探索するデータが無かった場合でも、最後に必ず見つかるようになるのですね。
だから番兵かぁ。納得です。

データが必ず見つかるので、探索の終了条件が変わります。

番兵法を使わないときの探索の終了条件は次のとおりでした。

条件1：探索値と配列の要素の値が一致した場合、探索処理を終了する
条件2：配列の最後まで探索して探索値が見つからない場合に終了する

番兵法を使うとこの条件のうち、条件2がいらなくなります。

そうか、必ず見つかるので見つからないっていうことは考えなくて良いんだ。

そうなのです。探索の条件は単純に見つかったかどうかだけ判定すれば良いことになります。

その他にもう一つ変更する箇所があります。

それは、表示の判定です。表示する内容を変えるための判定は、見つかった見つからなかったかを制御する発見フラグの値で行っていました。しかし、番兵法では必ず探索データは発見されるので「発見フラグ」の内容は常に「True」になっています。

探索値は必ず見つかるのですが、番兵法の場合はどこで探索値が見つかったか、添字の位置が重要になります。

① 配列には、5件のデータが入った状態から始まります。

② 探索値を m とした場合、番兵として配列末尾に探索値 m を追加します。

③ 探索値 m が配列の末尾以外にある場合、見つけた添字位置で探索処理を中断します。

④ 探索値 m が配列の末尾にしかない場合、配列の末尾で探索処理を中断します。

③、④でわかるように、探索処理を中断したときの添字の位置が2種類あることがわかります。

添字の値を確認することで、データが配列内にあったのか、なかったのかが判断できることがわかりましたね。

探索処理が終わったときの添字の値が、配列の最後の要素の添字位置より小さかったら、見つけたってことですよね。

そうです。この処理を行うためにPythonで配列の末尾にデータを追加し、配列の最後の要素の添字番号を取得する方法を知りましょう。

処理内容	命令	例
配列の末尾に追加する	append()メソッド	data.append(100) # 配列の末尾の要素に100を追加する。data[5]に100が代入される。
配列の末尾の要素の添字位置を取得する	len()関数	len(data) - 1 # 配列dataの要素数を返す。len()は要素数を返すので、添字番号は -1 する必要がある。

配列の最後の要素位置を取得する場合は注意が必要です。

例えば、下記の配列の場合、「len(data)」とすると、取得した値は6になります。

配列の要素位置は0番目から始まるので、要素数が6のときは最後の要素の添字位置は5になります。

そのため、配列の最後の要素位置は「len(配列) - 1」で求めます。

それでは、Pythonで番兵法のプログラムを作りましょう。

番兵法を使ったプログラムを完成させよう

次のプログラムは、番兵法を使って線形探索を行うPythonプログラムです。

ただし、プログラムは（ｃ）と（ｄ）の２箇所が空欄になっています。空欄を埋めてプログラムを完成させましょう。

import random

# 配列をランダムに生成する関数
def generate_array(size=10, low=1, high=100):
    """
    ランダムな整数の配列を生成する
    size : 要素数
    low  : 最小値
    high : 最大値
    """
    return random.sample(range(low, high+1), size)  # 重複なし

# ===== メイン処理 =====

# ランダムに配列を作成
data = generate_array(20, 1, 100)
print("探索対象データ:", data)

# 探す値を入力
target = int(input("探す値を入力してください: "))

# 番兵の設定
data.append(target)

# フラグと位置変数
found_flag = False
i = 0

# フラグを条件に使った線形探索
while （ｃ）:
    if data[i] == target:
        found_flag = True
    else:
        i = i + 1

# 結果表示
if （ｄ）:
    print("見つかりました。")
else:
    print("見つかりませんでした。")

Pythonプログラムの空欄（ｃ）、（ｄ）を埋めてGoogle Colabで実行してみましょう。

Google Colabを開いていない場合は次のリンクから開きましょう。

Google Colab

プログラムの空欄（ｃ）に入る条件式を下記の命令から選んで答えてください。