アルゴリズムの状態更新と再帰

要点と定義

アルゴリズムは、入力から目的の結果を得るための処理手順です。手順を読むときは、変数や配列の状態、条件判定、更新の順序を追います。過去の午後問題にあるC風コードや旧形式の設問は、配列添字や累計値を追う基礎練習として役立ちますが、現在も同じ試験形式だとは限りません。

編集処理の状態更新では、数字の桁をパターンの数字位置に対応させ、先頭の不要なゼロや後続文字をどう表示するかを状態で管理します。たとえば signif を「有効数字の処理中か」を表す状態とし、開始時は off とします。先頭ゼロに対応する □ は埋め文字にし、■ は規則に応じて有効数字の開始を示す扱いにできます。有効数字が始まった後は数字を残します。正数では数字列の後ろに正を表す記号があるため、末尾の数字では状態を off に戻し、その後の数字以外の文字を埋め文字にできます。□ と ■ は異なる制御文字なので、同じ規則で処理できるとは限りません。

隣接要素の入替えによる順序調整では、配列内で隣り合う二つの作業について、現在の順序と逆順の遅延合計を計算します。作業終了までの累計日数を ft、作業日数を d、目標期間を T とすると、その作業の遅延は max(0, ft + d − T) です。逆順の遅延合計のほうが小さい場合に二要素を交換します。配列の位置 i と i+1 を交換するので、右側の添字は i+1 です。交換したとき i>0 なら前の組合せに戻り、累計 ft から直前の作業日数を除いて再確認します。たとえば、添字を先に減らす --i を使えば、減らした位置の作業日数を参照して ft から差し引けます。交換しない場合は、現在位置の作業日数を ft に加えてから i を進めます。

遅延を表示するときは、一つの作業の遅延と、そこまでの累計遅延を分けます。例として、3番目までの累計作業日数が73日で、3番目の目標期間が29日なら、3番目単独の遅延は 73−29＝44 日です。2番目までの遅延が16日なら、3番目までの累計遅延は 16＋44＝60 日です。

再帰は、関数がより小さい入力について同じ関数を呼び、問題を段階的に解く方法です。非負整数の階乗では n! = n×(n−1)! なので、n>0 で F(n)=n×F(n−1)、基底条件を F(0)=1 とします。呼出しごとに引数が基底条件へ近づき、そこで呼出しを止めることが必要です。たとえば F(3)=3×2×1×F(0)=6 です。