アルゴリズムの設計と追跡

要点と定義

アルゴリズムは、目的を達成するための処理手順です。入力、処理、条件による分岐、繰返し、出力の関係を整理し、流れ図や擬似言語などで表現します。設計では、何を入力し、どの条件で処理を進め、どの状態になれば終了するかを明確にします。

整列済みのファイルをキーの値ごとにまとめる処理では、同じキーのレコードが連続して現れるため、キーが変わる時点でそれまでの件数や合計を出力できます。たとえば、キーAの金額が4、7、2なら、Aの件数は3、合計は13です。キーが変わった時点で集計を出力して次のキーの件数と合計を初期化し、入力の終わりでも最後の集計を出力します。入力が空の場合は、出力すべき集計がない点にも注意します。

ユークリッドの互除法は、二つの整数の最大公約数を求める方法です。引き算を使う形では、二数を比較し、大きい方から小さい方を引く操作を繰り返します。二数が等しくなった値が最大公約数です。正の整数を対象にし、等しいかを確認してから次の引き算へ進むことで終了を判定します。たとえば、18と12は、(18,12)→(6,12)→(6,6)となり、最大公約数は6です。問題の入力値876と204では、比較のたびに大きい方から小さい方を引くと、組は(876,204)、(672,204)、(468,204)、(264,204)、(60,204)、(60,144)、(60,84)、(60,24)、(36,24)、(12,24)、(12,12)となり、11回目の比較で終了します。

ヒープは、各親の値が子の値以上である二分木です。この最大ヒープでは根が最大値になります。配列で表すと、添字iの左の子は2i+1、右の子は2i+2、親は切り捨て((i−1)/2)です。要素を追加するときは親と比べ、子の方が大きければ交換して親方向へ進みます。これで親が子以上という性質を保てます。

ヒープソートでは、根の最大値を整列対象領域の末尾と交換して、その位置を整列済みにします。残った領域の根から下へヒープを再構成し、最大値の取り出しを繰り返すと、末尾側から昇順に並びます。下方向の再構成では、左右の子がある場合は大きい方の子を選んで親と比べます。同値ならどちらを選んでも値の大小関係は保たれますが、与えられた手順が「右の子が左の子以上なら右を選ぶ」なら、その規則に従います。例としてヒープ[60,30,45,15,5,10,20]の根と末尾を交換すると、根は20になります。残った範囲では子30と45のうち45を選び、20と交換して下へ進みます。

ファイル処理では、突合せに使うキー順をそろえると、双方を先頭から順に読み進められます。同じキーの中で新しい実施年月が先になるように整列し、キーが同じレコードを一つにまとめれば、先頭の一件を最新として扱えます。たとえば、社員コードを昇順、実施年月を降順に並べ、社員コードだけで重複をまとめると、社員ごとの最新レコードが残ります。最新レコードの判定結果が空白なら未判定、再検査要否が「要」なら再検査が未完了と判断できます。「否」は再検査後にも設定され得るため、それだけで未受診とは判断できません。