最大値を探す・値を探す処理の読み方

「いちばん大きい値は」「その値は何番目にあるか」——探す処理も出題の定番です。 集計と同じく箱を用意して更新していく形ですが、 更新の条件と「位置を覚える」という考え方が加わります。

BASIC

最大値は「今までの一番」と比べ続ける

最大値を求めるプログラムは、「今までの最大」を覚えておく箱を1つ用意し、 それより大きい値が出てきたときだけ入れ替える、という形です。

Nums = [4, 9, 2, 7]
mx = Nums[0]                 ← 最初の値を仮の最大とする

i を 0 から 要素数(Nums) - 1 まで 1 ずつ増やしながら繰り返す:
｜もし Nums[i] > mx ならば:
⎿⎿ mx = Nums[i]

表示する(mx)

初期値の置き方に2通りある

mx = 0 と書いてよいのは、データに0以上しか出てこないと分かっている場合だけです。 「この初期値でよいか」を問う出題があるので、根拠を言えるようにしておいてください。

最小値なら不等号を逆にするだけ

最小値を求めるときは Nums[i] < mn と向きを変えます。 不等号の向きだけで最大と最小が入れ替わるため、穴埋めで狙われます。

EXERCISE 1

例題1：更新条件を選ぶ

配列の最大値を mx に求めるには、［ ア ］に何を入れればよいですか。

Nums = [4, 9, 2, 7]
mx = Nums[0]

i を 0 から 要素数(Nums) - 1 まで 1 ずつ増やしながら繰り返す:
｜もし ［ ア ］ ならば:
⎿⎿ mx = Nums[i]

表示する(mx)

選択肢：① Nums[i] > mx　② Nums[i] < mx ③ Nums[i] == mx　④ mx > Nums[i]

EXERCISE 2

例題2：更新される回数を数える

次のプログラムにおいて、best = Nums[i] は何回実行されますか。

Nums = [6, 2, 8, 8, 3, 9]
best = 0

i を 0 から 要素数(Nums) - 1 まで 1 ずつ増やしながら繰り返す:
｜もし Nums[i] > best ならば:
⎿⎿ best = Nums[i]

表示する(best)

選択肢：① 2回　② 3回　③ 4回　④ 6回

POSITION

値ではなく「位置」を覚える

「最大値はいくつか」ではなく「それは何番目か」を聞かれることがあります。 その場合は、値ではなく添字を覚えます。

mx_pos = 0

i を 0 から 要素数(Nums) - 1 まで 1 ずつ増やしながら繰り返す:
｜もし Nums[i] > Nums[mx_pos] ならば:
⎿⎿ mx_pos = i

比べる相手が mx ではなく Nums[mx_pos] になる点に注目してください。 「覚えているのは位置なので、値を見るにはもう一度配列を引く」——この形が 選択法（選択ソート）でもそのまま使われます。

見つからなかったことを表す -1

探索では、見つからなかった場合をどう表すかが問われます。 添字は 0 から始まるため、pos = 0 を初期値にすると 「先頭で見つかった」と区別がつきません。そこで添字としてあり得ない -1 を使います。

EXERCISE 3

例題3：最初の1回だけ記録する

合計が target 以上になった最初の添字だけを pos に入れるには、［ ア ］に何を入れればよいですか。

Point = [12, 8, 15, 6, 20]
target = 30
total = 0
pos = -1

i を 0 から 要素数(Point) - 1 まで 1 ずつ増やしながら繰り返す:
｜total = total + Point[i]
｜もし total >= target かつ ［ ア ］ ならば:
⎿⎿ pos = i

表示する(pos)

選択肢：① pos == -1　② pos == i　③ pos >= 0　④ i == 0

BREAK

見つけたら止める（打ち切り）

探し物が見つかった時点で、それ以降を調べる必要はありません。 繰り返しを抜ける を使うと、そこで繰り返しが終わります。

Items = [4, 7, 3, 6, 5]
target = 18
total = 0
used = 0

i を 0 から 要素数(Items) - 1 まで 1 ずつ増やしながら繰り返す:
｜total = total + Items[i]
｜used = used + 1
｜もし total >= target ならば:
⎿⎿ 繰り返しを抜ける

表示する(used)

合計が 4 → 11 → 14 → 20 と増え、i = 3 で18以上に達して抜けます。 used は 4 です。最後の 5 は一度も足されません。

上の2つは答えが同じでも、調べる回数が違います。 「何回比較したか」を問われる問題では、この違いが直接得点に関わります。 動きを確かめたい場合は線形探索シミュレーターで 条件の書き方を切り替えて比べてみてください。

EXERCISE 4

例題4：見つかったかどうかを記録する

配列 Nums に target が含まれているかを found に入れるプログラム表記として、正しいものを選びなさい。

Nums = [3, 8, 1, 5]
target = 1

# found に True または False を入れる

選択肢：

① found = False
   i を 0 から 要素数(Nums) - 1 まで 1 ずつ増やしながら繰り返す:
   ｜もし Nums[i] == target ならば:
   ⎿⎿ found = True

② found = True
   i を 0 から 要素数(Nums) - 1 まで 1 ずつ増やしながら繰り返す:
   ｜もし Nums[i] == target ならば:
   ⎿⎿ found = False

③ found = target

④ found = Nums[0]

EXERCISE 5

例題5：用意された関数を使う

配列 Nums の中から最大値を表示するプログラム表記として、正しいものを選びなさい。

Nums = [3, 9, 1, 6]

# 最大値を表示する

選択肢：① 表示する(最大値(Nums))　② 表示する(最小値(Nums)) ③ 表示する(要素数(Nums))　④ 表示する(Nums[0])

CODE

3つの表記での書き方の違い

Nums = [4, 9, 2, 7]
mx = Nums[0]
mx_pos = 0

i を 0 から 要素数(Nums) - 1 まで 1 ずつ増やしながら繰り返す:
｜もし Nums[i] > mx ならば:
｜｜mx = Nums[i]
⎿⎿ mx_pos = i

表示する(mx, mx_pos)

nums = [4, 9, 2, 7]
mx = nums[0]
mx_pos = 0

for i in range(len(nums)):
    if nums[i] > mx:
        mx = nums[i]
        mx_pos = i

print(mx, mx_pos)

const nums = [4, 9, 2, 7];
let mx = nums[0];
let mxPos = 0;

for (let i = 0; i < nums.length; i++) {
  if (nums[i] > mx) {
    mx = nums[i];
    mxPos = i;
  }
}

console.log(mx, mxPos);

CHECK

このテーマのチェックリスト

• 最大値の更新条件が Nums[i] > mx（新しい値が左）だと分かる
• mx = 0 が負の数を含むデータで危険だと説明できる
• > と >= で更新回数が変わると分かる
• 位置を覚えるときは Nums[mx_pos] と比べると分かる
• pos = -1 が「未発見」と「まだ記録していない」の両方を表せると分かる
• 打ち切りの有無で調べる回数だけが変わると分かる
• フラグはFalse から始めて、見つかったら True にすると分かる
• 最大値(Nums) が繰り返し1つ分に相当すると読み替えられる

探索が読めるようになったら、最後はシミュレーション型の問題です。 ここまでの型を組み合わせた、発展レベルの読み方を扱います。