アルゴリズムの設計と処理

要点と定義

アルゴリズムは、入力から目的の結果を得るための処理手順です。手順を配列や変数の状態変化として追うと、各分岐が何を判定し、どの値を更新するかを確認できます。過年度の午後問題にあるプログラム読解は、この基礎を学ぶ例として有用です。

演算式を解析する方法の一つは、数値、演算子、各演算子の優先度を別々に記録し、優先度の高い演算から順に計算することです。括弧の内側の優先度を外側より高く設定すれば、括弧内を先に計算できます。内側の優先度を上げる幅は、演算子間の優先度差より大きくします。これにより、括弧の深さが一段増す効果が、同じ括弧内での演算子の優先度差を上回ります。

同じ優先度の演算をどちらから実行するかは、アルゴリズムの選び方に関わります。優先度を更新する条件が「現在の優先度より大きい」なら、同順位では先に見つけた演算子が残り、左側から実行されます。「以上」にすれば同順位でも後から見た演算子に更新され、右側から実行されます。加算や乗算のように順序を入れ替えても結果が変わらない演算がある一方、減算や除算では一般に結果が変わります。

符号付き整数の符号を演算子として読む設計もあります。例えば、負数を「0から数値を引く」と扱えば、負号を通常の減算として処理できます。式の「2×(−1)」を解析すると、負号の直前にある値を0として記録し、「0−1」を掛け算より先に処理すれば「2×−1」になります。この方法では、符号の前に値がない場合も0を補うことが前提です。

グラフの到達可能性は、ある頂点から辺をたどって目的の頂点に着けるかを調べる問題です。再帰関数は、現在の頂点が目的地なら到達可能とし、そうでなければ隣接頂点を順に調べます。各呼出しでは「次の頂点から同じ目的地へ行けるか」を調べ、どれか一つでも到達できれば成功です。列車の進行例では、行先までの経路があることに加えて、次区間が空いていることも進行条件でした。再帰探索が経路条件を担い、信号確認が空き区間の条件を担います。

整列済みファイルの併合では、各ファイルの現在レコードを一つずつ保持し、キーを比較して小さい側を処理して読み進めます。キーが一致したら、対応する値を比較して結果を決めます。片方が終端でも、もう片方に未処理レコードが残ることがあるため、両方の終端に達するまで処理を続けます。注文と入金の照合では、番号が一致する場合に金額を比較し、一致しなければ不一致として扱います。番号が一致しない注文は、支払方法に応じて出荷待ちまたは出荷対象を判定します。

適用条件と例

演算子の優先度を数値で持つ方式では、優先度の割当てと括弧の深さの増分を一貫させます。たとえば加減算の優先度を1、乗除算を2とし、括弧の深さごとに値を10ずつ加えるなら、内側にある低優先度の演算子も、外側の高優先度演算子より上位になります。異なる定数を使う場合も、括弧一段分の増分が同じ階層内の優先度差を超える必要があります。最優先の演算子を一つ選んで計算し、右隣の値と演算子を配列から詰めると、演算子数が一つずつ減り、最後に値が一つ残ります。

例として「12−3−1」は、左からなら「(12−3)−1＝8」、右からなら「12−(3−1)＝10」です。したがって、同順位を右から処理する設計を採るなら、その規則が式の意味に合うか確認します。通常の演算規則を実装するには、単に優先度だけでなく、演算子ごとの結合方向も定義します。

経路探索の再帰には、目的地に着いたときの終了条件と、隣接頂点を順に調べる処理が必要です。たとえば分岐する駅から目的駅へ向かうとき、片方の経路が目的駅へ続くなら、その経路を選べます。探索対象を次の頂点へ進めつつ、目的地は変えずに渡します。列車を一つの次区間へ移した後は、同じ列車について別の分岐も試さないよう、その内側の探索を終了します。