アルゴリズムの設計と実行

要点と定義

アルゴリズムは、入力に対して処理の順序や条件を明確に定め、求める結果を得る手順です。順次処理は記述した順に進み、分岐は条件の真偽で進路を選び、反復は条件や回数に従って処理を繰り返します。流れ図、擬似言語、決定表は、こうした手順や条件を表す方法です。どの表現でも、初期値、条件、更新、終了の扱いが読み取れることが重要です。

流れ図の条件を追うときは、各判定時点の値を記録します。たとえば二つの正整数を引き算でそろえる処理では、どちらが大きいかで引く側を決め、値が等しくなれば終了します。所定の分岐順になる条件を追うと、初期値に必要な関係は三倍した一方が二倍した他方に等しいことだと分かります。条件を満たすだけでなく、各分岐の大小関係も順番に確かめます。

アルゴリズムを設計・確認するときは、処理を小さな段階に分け、各段階で変数が表すものを明確にします。最大値を選ぶ処理なら、最初の値を返す条件は、その値が残り二つの両方より大きいことです。片方との比較だけでは、もう片方がさらに大きい場合を除けません。三つの値が異なる条件なら、等しい場合の扱いを追加する必要はありません。

適用条件と例

素数を列挙する処理では、候補の数を二から上限まで調べ、各候補を割る数があるか判定します。候補を割り切れる数が見つかったら、その候補は素数ではありません。最小の素因数は候補の平方根以下にあるため、平方根の整数部分までの除数を調べれば足ります。たとえば二十五なら二から五までを確認し、五で割り切れるので素数ではないと判定できます。割り算の商が特定の値かではなく、余りがゼロかで割り切れを判定します。候補の範囲を上限より一つ先まで広げると、求める範囲外の値まで結果に混ざることがあります。

整列では、クイックソートのように基準値を決め、左右から値を調べて基準値をまたぐ位置で交換し、部分列に分けて処理する方法があります。分割時は、走査位置が交差または一致した時点で区切りを確定するため、必ず交換が起こるとは限りません。たとえば中央の値が基準値そのものなら、左右の走査が中央で止まり、そのまま分割が終わる場合があります。手順を追う際は、基準値、左右の位置、交換後の配列を順に記録します。

整列済みの二つの配列を併合するときは、それぞれの先頭を比べ、小さい方を出力先に移して、その配列の位置だけを進めます。一方を使い切ったら、もう一方の残りを順に追加します。たとえば「二、三」と「一、四」を併合すると、一、二、三を順に選んだ後、残った四を追加します。末尾の追加処理を省くと、片方に残った値が欠落します。

区間内の四の倍数を数える方法は、区間の始点から一つずつ調べる方法と、始点以上で最初の四の倍数を見つけて四ずつ進む方法があります。始点が五なら最初の倍数は八です。始点からその倍数までを進める回数は最大三回で、その後、終点以下の値を数えます。刻み幅を四にすることで、倍数以外を数えずに済みます。

組合せを数える処理では、場合分けごとの数を求めて合計します。硬貨の例では、十円玉を使う枚数を固定すると、残額を一円玉と五円玉で作る方法は、五円玉を使う枚数がゼロから残額を五で割った商までなので、商に一を足した数です。残額を十ずつ減らして場合分けし、残額がゼロのケースも数えます。たとえば二十円なら残額は二十、十、ゼロとなり、それぞれ五、三、一通りで合計九通りです。条件を正より大きいにすると、残額ゼロのケースが抜けます。