アルゴリズム

要点と定義

アルゴリズムは、入力を決められた手順で処理し、目的の結果を得る方法です。処理を設計するときは、入力と出力、手順の順序、途中で変化する値、終了条件を明確にします。流れ図や擬似言語では、処理を順に行う「順次」、条件によって進路を選ぶ「判定」、同じ処理を繰り返す「繰返し」を表します。公式シラバスVer.9.2は、これらの表現に加え、整列・併合・探索、再帰、グラフ、文字列処理、ファイル処理などの基本と、アルゴリズムの設計を扱います。

整数を2進数に変換するには、整数を2で割った余りを下位桁から取り出し、次に商を処理します。たとえば13は、余りが下位から1、0、1、1となるため、逆順に読むと1101です。8桁で格納する場合は、残りの上位桁を0で埋めます。余りを保存してから値を商に更新する順序が必要です。先に商で上書きすると、元の値の余りを得られません。

再帰は、ある処理がより小さい入力について自分自身を呼び出す方法です。停止するための基底条件と、入力をその条件に近づける再帰部分が要ります。たとえば f(1)=1、f(n)=n+f(n−1) なら、f(2)=3、f(3)=6、f(4)=10、f(5)=15です。基底条件がない場合や、呼び出すたびに入力が小さくならない場合は、処理が止まらないことがあります。

配列の座標変換は、元の位置を変換後の位置へ対応づける処理です。行と列の添字が0から7までの8行8列を時計回りに90度回す例では、元の位置 (i,j) を新しい位置 (j,7−i) に移します。角の要素を一つ追えば、向きや添字のずれを確認できます。配列サイズが異なる場合は、7を最終添字に置き換えます。

整列では、比較規則と交換条件を先に決めます。バブルソートは隣り合う要素を比較し、昇順なら左が右より大きい場合に交換する方法です。走査するたびに未整列範囲の最大値が右端へ移ります。同じ値を交換しない規則なら、同値の要素の元の順序を保てます。たとえば出現回数の降順で並べ、同数ならコード順を保つ処理では、同数の要素を入れ替えないことが安定した並びに役立ちます。

適用条件と例

256要素を添字0から255まで走査するバブルソートでは、上限を255から1まで1ずつ減らす基本形の走査回数は255回です。走査中に最後に交換した位置を ix と記録した場合、その位置より右側は整列済みです。したがって次の上限を ix にできます。ix 自体は未確定範囲に残るため、上限を ix−1 にすると必要な比較を飛ばす場合があります。各走査の開始時に ix を初期化し、交換のたびに位置を更新します。交換がなかった走査では全体が整列済みなので、そこで終了できます。

ファイル処理では、並べ替えたレコードをキーごとに集計する方法があります。たとえば店舗番号と品目番号でまとめるなら、どちらか一方でも変わった時点で前の組の結果を出力し、新しい組の集計値を初期化します。入力終端では最後の組も出力します。最初のレコードを読む前の空の集計結果は出力しないよう、実際に組を処理したかを条件にします。これらの境界処理を欠くと、グループを誤って分割したり、最後の集計を落としたりします。