線形探索アルゴリズムを楽しく学ぼう！(2)

線形探索の応用編！ペア探索で最小値を見つけよう

本文は、リンク先notebookに基づいて、chatGPTが書いています。

Google Colab

こんにちは！
前回の記事で学んだ線形探索の基本に続いて、今回は応用編です。ここでは「ペア探索」と呼ばれる、2つのリストを組み合わせて探索する方法を学びます。しかも、「条件を満たす最小値」を求める実践的な例で説明します。プログラム初心者にもわかりやすく、そして中級者にとっても「なるほど」と思える工夫を盛り込んでいます。
それでは早速始めましょう！

---

ペア探索とは？

ペア探索では、2つのリストから要素を1つずつ取り出し、何らかの条件を満たすかどうかを調べます。
たとえば、リスト nums_a と nums_b があったとします。

nums_a = [20, 50]
nums_b = [30, 40, 60]

この2つのリストの要素をすべて組み合わせ、足し合わせた結果を調べるコードを書いてみましょう。

---

サンプルコード① 全ペアの合計を表示

以下のコードで、2つのリストの全てのペアを足し合わせ、その結果を出力します。

# リストを定義
nums_a = [20, 50]
nums_b = [30, 40, 60]

# 全てのペアの合計を出力
for num_a in nums_a:
    for num_b in nums_b:
        print(f"{num_a} + {num_b} = {num_a + num_b}")

これを実行すると、次のような結果が得られます。

20 + 30 = 50
20 + 40 = 60
20 + 60 = 80
50 + 30 = 80
50 + 40 = 90
50 + 60 = 110

おおっ！全てのペアが計算されました！

---

条件付き最小値の探索

次のステップとして、全てのペアの中から「条件を満たす最小値」を見つけてみましょう。今回の条件は「合計が70以下」です。

---

サンプルコード② 条件以下の最小値を求める

以下のコードを使って、70以下のペアの合計値の中で最小のものを探します。

# サンプルデータを定義
limit = 70  # 条件の値
nums_a = [20, 50, 70]
nums_b = [30, 40, 60, 90]

# 初期値として非常に大きな値を設定
INF = 20000000
min_value = INF  # 最小値

# 全てのペアを探索
for num_a in nums_a:
    for num_b in nums_b:
        pair_sum = num_a + num_b
        if pair_sum <= limit:  # 条件を満たす場合
            min_value = min(min_value, pair_sum)  # 最小値を更新

# 結果出力
if min_value == INF:
    print("条件を満たすペアはありません")
else:
    print(f"条件を満たす最小値: {min_value}")

これを実行すると…

コードをコピーする
条件を満たす最小値: 50

やった！リスト内のペアを全て調べ、条件を満たす最小値が見つかりました。

---

コードの解説

上記のコードでは、以下のポイントが重要です：

1. INF を使った初期値設定

   1. 初期値として非常に大きな値を設定しておくことで、最小値を安全に更新できます。

2. min() 関数

   1. 条件を満たすペアが見つかった場合、現在の最小値と比較して更新します。

3. 条件を満たさない場合の処理

   1. 条件を満たすペアがない場合は、「ありません」と出力する分岐を追加しています。

---

応用：条件を変えて試してみよう！

今回の条件は「70以下」でしたが、コードを少し変更するだけで他の条件にも対応できます。
例えば、「80以下」や「ちょうど60」といった条件で試してみると、新たな発見があるかもしれません！

---

まとめ

この記事では、線形探索の応用としてペア探索を学びました。
ペア探索は、リスト同士の組み合わせを全て調べる力技的な方法ですが、シンプルでわかりやすいので初心者にはぴったりです。