アルゴリズム

要点と定義

アルゴリズムは、目的を達成するための処理手順です。順次、条件による分岐、繰返しを組み合わせ、擬似言語や流れ図で表現します。入力条件、処理の順序、終了条件を明確にすると、正しさや終了性を確認しやすくなります。

整列では、比較する対象やデータの移し方に注目します。隣接要素を比べて逆順なら交換する方法、間隔を縮めながら部分列を整列する方法、ヒープから値を順に取り出す方法があります。過去の出題で扱った補足として、それぞれバブルソート、シェルソート、ヒープソートに当たります。

再帰は、処理の定義の中で同じ処理をより小さい問題に適用する方法です。終了するには、基底条件と、呼出しごとにその条件へ近づく引数の変化が必要です。過去の出題で扱った補足として、階乗は零の階乗を一とし、正の整数ではその数に一つ小さい数の階乗を掛けます。非負整数を一ずつ減らせば基底条件に到達します。

再帰式の値を求めるときは、条件に合う式を選び、呼出しを一段ずつ展開します。過去の出題で扱った補足として、アッカーマン関数の特定の値も、基底条件から再帰式を順に適用して求められます。

繰返し計算では、更新の前後で保たれる性質を確認します。過去の出題で扱った補足として、二つの整数を一方と他方で割った余りに置き換える処理では、最大公約数が保たれます。余りが零になったとき、残った数が最大公約数です。

近似計算では、停止条件と誤差の基準を対応させます。過去の出題で扱った補足として、連続関数が区間の両端で符号をまたぐ場合、中点を使って零点を含む区間を半分ずつ絞れます。反復回数は、区間幅が停止条件を満たすまで何回半分になるかで判断します。

後置記法では演算子を被演算子の後ろに置きます。値を順に保持し、演算子が来たら必要な値を使って計算し、結果を戻します。過去の出題で扱った補足として、通常の演算子の優先順位を保つには、先に行う演算の演算子をその被演算子の後に置きます。

適用条件と例

昇順にする例では、隣り合う二値を比べ、左の値が右より大きいときに交換します。一度の走査で全体が整列するとは限らないため、必要な回数だけ走査を繰り返します。シェルソートのように間隔を使う場合は、間隔を縮め、最後に間隔一で整列する点が手掛かりです。

再帰の例として、棚に残る冊数を数える処理を考えます。残りが零なら零を返し、それ以外なら一冊分を数えて、残りを一減らした処理結果を加えます。入力が非負整数なら、減少と基底条件の組合せで終了します。負数も受け付けるなら、その扱いを別に定めます。

二分探索は、比較順に整列したデータで、中央の値との比較を使って探索範囲を半分ずつ狭める方法です。対象がデータ中にない場合にも適用でき、範囲が尽きた時点で不在と判定できます。未整列データでは、中央との比較だけで範囲を捨てる根拠がないため、そのまま適用できません。零点を探す二分法では、連続性と端点の符号条件が、区間内に零点があることを支えます。

後置記法の評価では、値を順に保持し、演算子が来たら必要な値を取り出します。二項演算では、取り出す順序で引き算や割り算の意味が変わるので、左側と右側の被演算子を区別します。