互除法・二分探索・シミュレーション｜定番アルゴリズムの読み方

「初期化して、繰り返して、判定して、更新する」。前回の読み方を覚えたのに、変数が増えると手が止まる。何が足りないのでしょうか？

足りないのは、それぞれの変数が何を覚えているかの整理かもしれません。

今回は4題を、変数の役割から読み解きます。

先に結論：変数名の横に「役割」を書こう

まず「何を覚える変数か」、次に「いつ、どう変えるか」。この順で、図と具体例を追っていきましょう。

道場の後編：入れ物は、どれですか？

夜の部室。ユウキは前回の4色の付箋を持って、新しい問題の前に座りました。

ユウキ「先輩。変数が3つあります。どれが入れ物ですか」

テッパン先輩「……全部」

Sandy「付箋1枚に、箱1個とは限らへんで。それぞれ、何を覚えてもらうかを見よか」

以下のコードや数値は、本文用の学習例です。実際の共通テスト問題からの引用ではありません。表記は共通テスト用プログラム表記を参考にし、添字などは各例で指定します。

一問目：互いに素か、最大公約数で調べる

2つの正の整数が互いに素とは、最大公約数が1であることです。 「共通の約数がない」ではありません。1は、いつでも両方の約数だからです。

たとえば8の約数は1・2・4・8、15の約数は1・3・5・15。共通するのは1だけなので、8と15は互いに素です。両方が素数である必要はありません。

最大公約数を求める方法の1つが、ユークリッドの互除法です。

割る数と余りへ、2つの数を置き換える

48と18なら、次の割り算を繰り返します。

余りが0になった割り算の割る数が最大公約数。1なら互いに素。

48と18を、18と12へ。次は12と6へ。余りが0になった割り算の、割る数6が最大公約数です。したがって、48と18は互いに素ではありません。

28と15では、余りは13→2→1→0となり、最後の割る数は1。こちらは互いに素です。

なぜ置き換えてよいのでしょう。元の2数に共通する約数は、割る数と余りにも共通し、その逆も成り立ちます。共通の約数を保ちながら、調べる数を小さくしているのです。

代入の順番と、答えが残る場所を見る

a = 48
b = 18
b != 0 の間繰り返す:
｜ r = a % b
｜ a = b
⎿ b = r
表示する(a)

最初の1周では、次の順に値が変わります。

1. r = a % b：48を18で割った余り12を、rへ保存する。
2. a = b：aを18へ更新する。
3. b = r：bを、保存しておいた12へ更新する。

これで、次に調べる組が48と18から、18と12へ変わります。先に a = b とすると元の48を使えなくなるため、余りを先に求める順番が大切です。

最後の更新後はa＝6、b＝0。このコードで表示する答えはaの6で、終了条件に使ったbの0ではありません。

1から小さいほうの数まで割り切れるか試す方法もありますが、互除法なら余りを使って数を縮められます。正のbに対して余りは0以上b未満になることも、終了を考える手がかりです。

二問目：二分探索は、候補の範囲を覚える

先頭から順に調べる方法が線形探索です。データがN個なら、最悪でN個を調べます。

一方、二分探索は、中央の値と比べて、候補の範囲をほぼ半分に狭める方法です。ここでは、昇順に整列済みの配列を使います。

中央の値が探す値より大きければ、中央とその右側は候補から外せます。小さければ、中央とその左側を外せます。順番がバラバラでは、この判断はできません。

1〜100から37を探すと、3回で見つかる

Data[0]＝1、Data[1]＝2、…、Data[99]＝100とします。候補の両端を含む添字を、hidari・migiで覚えます。

中央の添字は、mannaka = (hidari + migi) ÷ 2。ここでの ÷ は整数の商です。

候補の添字範囲を更新し、中央の値と中央の添字を区別する。

表の各行で、「中央の値を比較→候補の添字を更新」の順に読みます。

1. 中央の値50は37より大きい → 50とそれ以上を外し、右端の添字を49−1＝48にする。
2. 中央の値25は37より小さい → 25とそれ以下を外し、左端の添字を24＋1＝25にする。
3. 中央の値37が一致 → 見つかった添字は36。

更新するのは「値50・25」ではなく、その値が入っている場所の番号49・24を基にした範囲です。

Sandy「37と、37が入っとる場所の番号を混ぜんようにな。値と添字は別もんやで」

中央を調べて外した後は、中央−1または中央＋1へ進めます。 同じ中央が候補に残り続ける更新では、範囲が縮まらず、終了しないことがあります。

見つからない場合も考えます。左端が右端を超えたら候補は空なので、探索を終了します。今回の単純な形は、一致する要素を1つ探すものです。重複がある場合の最初の位置などを探すには、別の条件設計が必要です。

検索回数は、最後の1個を確認する回も含む

ここでは中央の要素を1つ調べることを1回と数えます。条件式や演算子を実行した総回数ではありません。

最後の候補を調べる回も含め、実装と回数の定義をそろえる。

1000個でも最大10回という少なさが、二分探索の特徴です。ただし、「半分にして1個になったら終わり」ではありません。最後の1個が探す値かどうかも確認します。

たとえば1024個なら最大11回です。10回で足りるのは、この方式では最大1023個まで。回数を問われたら、実装と、何を1回と数えるかをそろえてください。

整列のための処理は、ここでの探索回数には含めていません。未整列のデータを1回だけ探す場合まで、準備を含めて必ず二分探索が有利とは限りません。

三問目：乱数で勝負を再現する

2人がそれぞれ、1〜13の数を1つ選び、大きいほうが勝つゲームを考えます。2人の選択は独立で、各数が同じ確率で出るものとします。毎回同じ条件で、新しく選び直します。

乱数は、こうした選択をプログラムで再現するために使えます。関数名や引数は問題によって違うため、今回は「1以上13以下の整数を均等に返す関数」が用意されたものとして考えます。

場合分けは3つです。

• a＞bなら勝ち。
• a＜bなら負け。
• a＝bなら引き分け。

勝ちと負けだけ数えて、同じ数の扱いを忘れないようにしましょう。

引き分けの確率は1/13

2人の組み合わせは13×13＝169通り。同じ数の組は（1,1）から（13,13）まで13通りなので、引き分けの確率は13/169＝1/13です。

独立で均等な選択なら、引き分け13/169、勝ちと負けは各78/169。

勝ちと負けは対称で、それぞれ78/169＝6/13、約46.2％です。引き分けは約7.7％になります。

これは理論上の確率で、13回遊べば必ず1回引き分けるという意味ではありません。また、1〜13を各1枚そろえた同じ山から、戻さずに2枚引くモデルなら同じ数は出ません。カードの選び方が違えば、確率も変わります。

回数を数えて、割合へ直す

勝ち・負け・引き分けの回数を0で初期化し、1000回試すなら、毎回それぞれの数を選んで結果に応じた回数を1増やします。

最後に、勝ちの割合＝勝ち数 / 試行回数を求めます。百分率なら、さらに100を掛けます。たとえば1000回中460回勝ったなら、460 / 1000＝0.46、つまり46％です。これは計算方法の例で、今回の実測結果ではありません。

ここでは小数まで求める / を使います。整数の商を求める ÷ とは区別しましょう。1000回の結果が理論値とぴったり一致する必要はなく、試行を増やしても誤差が毎回必ず小さくなるわけではありません。

このように、乱数を使って繰り返し試し、結果の分布を調べるのはシミュレーションの一例です。シミュレーション全般が、必ず乱数を使うわけではありません。

また、多くの実装が使う疑似乱数は、初期状態などの条件をそろえると同じ列を再現できます。「同じプログラムでも必ず毎回違う結果」とは覚えないようにしましょう。

四問目：平均に最も近い人を探す

4人が30・45・60・65を出し、平均に最も近い人が勝つゲームです。

合計は200、平均は200/4＝50。各値と50との差の絶対値を比べると、20・5・10・15になります。

平均からの距離は差の絶対値で比べ、最小の差5を選ぶ。

最も小さい差は5なので、45を出した2人目が勝ちです。絶対値は、符号を外して距離として考えるために使います。 30−50＝−20でも、平均からの距離は20です。差をそのまま比べると−20が最小になり、平均に最も近い人を選べません。

平均を計算する割り算は / です。今回の答え50は整数になりますが、平均が小数になる場合もあるので、整数の商を求める ÷ と混同しないようにしましょう。

最初の候補を、仮のチャンピオンにする

配列の添字は0からとします。最初に、先頭の人を仮の勝者にし、その人の実際の差を覚えます。

• best＝0：今の勝者の添字。
• bestdiff＝20：その人と平均との距離。

2人目の差5が来たら、bestを1、bestdiffを5へ更新。その後の差10、15では更新しません。最後は添字1、つまり2人目です。

候補の番号0は正しくても、最小差はその候補の実際の差で初期化する。

更新するときは、候補の番号bestと、その候補の差bestdiffを両方変えるのがポイントです。片方だけ変えると、「誰の差を覚えているか」が食い違います。

ここでbestdiffを根拠なく0にすると、差は0未満にならないため、差 < bestdiff が成立しません。今回の最小差5を選べなくなります。

ユウキ「でも、bestも0からですよね？」

Sandy「そっちは先頭の番号や。0にしたらあかんのは、今回の候補と合ってへん『仮の最小差』のほうやねん」

「何でも0で初期化」でも、「0は全部だめ」でもありません。その変数が何を表すかに合った値を入れます。この方法では、少なくとも1つ候補があることも前提です。

差が同じ人が複数いる場合の扱いも決めましょう。小さいときだけ更新するなら先に出た人が残り、同じときも更新するなら後の人が残ります。全員を勝者にしたいなら、複数の番号を記録する仕組みが必要です。

学習例：30と18は互いに素？

本文用の学習例です。実際の入試問題ではありません。

30と18を互除法で調べると、余りは12→6→0になります。最大公約数は6なので、互いに素ではありません。

もし「最後の余り0が最大公約数」と答えたなら、終了時にどの変数が何を持つかを見直します。求めたいのは、余りが0になった割り算の割る数です。

まとめ：入れ物に何を覚えさせるかを決める

ユウキは、付箋を貼る前に、変数の横へ「左端」「右端」「中央」と書き込みました。

テッパン先輩「……先に、何を持つかを決めたね」

変数の役割が分かれば、判定や更新の理由も追いやすくなります。名前だけで判断せず、実際に入る値と、その変化を確かめていきましょう。

ほかのテーマは情報Ⅰサバイバルの記事一覧から読めます。アルゴリズムを実際のプログラムや作品制作で使ってみたい方は、プログラミングスクールSandboxもご覧ください。

参考資料

• CP-Algorithms：Euclidean algorithm — 最大公約数と余りによる置き換え。
• NIST：binary search — 整列済み配列で範囲を狭め、発見または候補が空になるまで調べる方法。
• CP-Algorithms：Binary Search — 範囲の設計と更新、回数の増え方。
• Python公式：random — 整数の一様選択、疑似乱数と再現性。
• 大学入試センター：試作問題「情報」の概要（PDF） — 共通テスト用プログラム表記、演算子、当該問題の指示の優先。