アルゴリズムの基本

要点と定義

アルゴリズムは、入力から目的の結果を得るための処理手順です。流れ図や擬似言語を読むときは、順次実行、条件による分岐、繰返しを見分け、各変数の初期値・更新の順序・判定時点・終了条件を追います。手順を一回ずつたどり、判定に使う値と更新後の値を混同しないことが基本です。

反復による二進数の乗算では、乗数の各ビットを順に調べます。そのビットが1なら被乗数を積に加え、次の桁に進むため被乗数を左へ、乗数を右へ1ビット移します。乗数の各ビットと被乗数の重みが対応するため、この手順をビット数分繰り返せば積を作れます。16ビットの乗数なら、最下位ビットから始めて16回調べます。

再帰は、手続が自分自身を、より小さな問題として呼び出す方法です。停止する基底条件と、呼び出すたびにその条件へ近づく引数の変化が必要です。最大公約数を求めるユークリッドの方法では、f(x, y)を、y=0ならx、そうでなければf(y, x mod y)とします。たとえばf(775, 527)は、余りを使ってf(527, 248)、f(248, 31)、f(31, 0)と進み、基底条件で31を返します。最初の余りで止めず、呼出しが終わるところまで追います。

2分探索は、検索キーの順に整列したデータから値を探す方法です。中央の値と検索キーを比べ、大小関係から候補範囲の片側を除きます。昇順なら、中央の値が検索キーより小さいときは中央より右側に候補を絞ります。検索キーで整列されていなければ、大小関係から候補を安全に除外できません。

検査文字は、文字に割り当てた数値と位置ごとの重みを使って作る検査用の文字です。重み付きの合計を法Nで計算し、合計と検査文字を合わせた値がNで割り切れるように検査文字を選びます。検証時に合計の余りが0なら検査を通過し、0でなければ誤りを検出します。この方法は誤りを検出する仕組みであり、あらゆる誤りを必ず検出する保証ではありません。複数の変化の影響が剰余上で打ち消し合えば、誤りがあっても通過することがあります。

適用条件と例

2分探索を適用する条件は、データが探したいキーの順に整列されていることです。たとえば顧客番号で探すなら、顧客番号順に並んでいる必要があります。追加された順や番地順に並んでいるだけでは、中央の番号との大小から片側を除く根拠になりません。候補範囲を半分に絞れるのは、並び順が検索キーの大小と一致している場合です。

検査文字を表形式で使う場合は、行だけでなく列も文字列とみなして検証します。表を誤りなしと判定するには、追加した行の検査と対象となる各列の検査がすべて通る必要があります。行検査に通っても列検査に失敗することがあり、一方向だけの合格では表全体の整合性を確認できません。

バッチ処理で同じキーのレコードをまとめるには、先にそのキー順に整列し、同じキーのレコードが連続するようにします。たとえば年月順に売上伝票を並べ、年月が切り替わったら、それまで蓄積した年月分を書き出して次の集計を始めます。各伝票の金額は支店番号に対応する欄へ加算し、年月分を書き出す際には支店別の累積値を合計します。代入で金額を置き換えると、同じ支店の先行伝票の金額が失われます。

集計処理では、整列キー、集計単位、初回処理、終端処理を区別します。年月順でなければ同じ年月の伝票が離れて現れるため、年月の切替だけで正しいまとまりを作れません。また、ファイル終端は年月の切替とは別の条件です。最後に蓄積した年月分も終端時に書き出します。