アルゴリズムの基本と設計

要点と定義

アルゴリズムは、問題を解くための明確な処理手順です。入力の性質に合わせて処理の順序や終了条件を設計し、各段階で何を保持・更新するかを決めます。流れ図や擬似言語は、順次、判定、繰返しなどの処理を表す方法です。ここでは、再帰、整列したデータの照合、グラフ上の最短経路、リストのリンク更新、数値の編集を、設問で必要な手順とともに扱います。

再帰は、問題を同じ形式の小さな問題に置き換えて解く方法です。呼出しを止める基底条件と、呼出しのたびにその条件へ近づく変化が必要です。ユークリッドの互除法では、余りが0ならもう一方の数を返し、そうでなければ「二つ目の数」と「一つ目を二つ目で割った余り」を次の問題にします。231と15なら余りは順に6、3、0となり、最後に0でない除数の3が答えです。

整列とファイル処理では、レコードのキーを使って対応付けます。複数ファイルが同じキー順なら、先頭同士を比較し、小さい側を読み進めることで照合できます。順不同の結果を順序付きマスタと照合する場合は、結果側をキーで整列してから比較します。今回の日付など後で必要な情報は別に保持し、一致したレコードだけを更新します。今回分を履歴の先頭に挿入するなら、既存の履歴を末尾側から一つずつ後ろへ移します。

グラフの最短経路では、状態を頂点、状態間の遷移を辺、遷移にかかる日数などを重みとして表します。始点から各状態までの最小費用に加えて、その最小費用を実現した直前状態を記録すると、費用と経路の両方を求められます。例えば状態4までの最小費用が8で、そこから状態7へ5かかるなら候補は13です。状態5までの最小費用が9で、そこから状態7へ3かかるなら候補は12なので、状態7には12と直前状態5を記録します。終点から直前状態をたどると逆順になるため、始点から表示するときは順序を反転します。

リンクリストは、各要素に次の要素のアドレスを持たせて順につなぐ構造です。挿入位置の直前要素をA、次要素をB、新要素をXとすると、AからXへ、XからBへリンクを設定します。削除では、削除対象のリンクから次要素Bを読み、直前要素AをBへつなぎ替えます。要素の値とリンク欄は役割が異なるため、操作する位置を区別します。この知識は、別の主項目を扱う設問でも、空欄の命令がリストの接続を保つか判断するために必要です。

数値の編集は、数値を決められた表示パターンに配置する処理です。数字を置く制御文字と、そのまま残す文字を区別し、先行する不要な0やその前の区切りを埋め文字に置き換えます。状態signifは有効数字が始まったかを表します。白い制御文字□は先行する0を埋め文字にして状態を保ちます。黒い制御文字■は、先行する0を埋め文字にしつつ、符号が正を示さない場合には有効数字の開始として状態を切り替える働きがあります。数字を処理するときは現在の桁Value[v]が0かを見て置換を決め、状態を戻す条件では次の文字Value[v＋1]が「+」かを見ます。状態がoffの間は通常文字も埋め文字になり、onならそのまま残ります。

適用条件と例

再帰を使うときは、基底条件が到達可能か、各呼出しで引数が終了条件へ近づくかを確かめます。互除法なら、正の除数で余りを計算し、余りを次の除数にしていくと、余りは除数より小さくなります。231 mod 15＝6、15 mod 6＝3、6 mod 3＝0なので、最後の0でない除数は3です。余りが0のときに停止する判定がなければ、再帰は正しく終わりません。

キー順の照合では、比較結果に応じて読み進める側を決めます。例えばマスタの現在キーが結果キーより小さければ、対応する結果はまだ先にある可能性があるためマスタを進めます。一致すればそのレコードを更新します。異なるというだけで処理を終えると、後方にある一致を見逃します。履歴を先頭へ挿入する例で10件分の領域があるなら、9番目を10番目へ、8番目を9番目へと、末尾から逆順に移します。先頭から移すと、移動先を後続の処理で上書きすることがあります。