反復と選択のアルゴリズム

要点と定義

アルゴリズムは、入力を受け取り、定めた手順で処理し、結果を得る方法です。処理を追うときは、各変数の値がどの命令で変化するか、条件判定がどの値を見ているか、分岐後にどこへ進むかを順に記録します。繰返しの終了条件を誤ると、必要な処理を飛ばしたり、終わらないループになったりします。

「集計してから選ぶ」処理では、入力を一件ずつ読み、キーに対応する領域へ値を加算して集計できます。チーム番号を添字とする配列なら、各選手の秒数を該当チームの合計に足します。入力を読み終えた後、合計を比較して最小のものを選び、処理済みの印を付けて次の最小値を探せば、昇順に並べた結果を得られます。人数が各チームで同じなら、合計の大小と平均の大小は一致します。

最小値を探す基本形では、現在の最小値と候補を比較し、候補の方が小さい場合だけ最小値と選択対象を更新します。探索対象を番号の大きい方から調べ、同値のときは更新しないなら、同じ値の対象は先に調べた方が選ばれます。したがって、同値の順序は探索方向と更新条件の両方で決まります。

カウンタで繰返しを制御するときは、カウンタを更新する前後のどちらの値で判定するかを明確にします。たとえば、比較対象を一つ処理した後に添字を減らし、まだ正なら比較箇所へ戻る設計では、添字がゼロになった時点で比較を終えます。一方、出力する対象数を減らした後、残数が正なら次の探索へ戻れば、残数がゼロになったところで処理を終えられます。

適用条件と例

数値を桁ごとに取り出すには、除数で割った商と余りを利用できます。除算命令がない場合でも、値から同じ除数を繰り返し引き、引けた回数を商として数えられます。たとえば、1628秒を分・秒へ分解するなら、600を2回引いて428、60を7回引いて8、10は0回引きます。600秒単位の商が分の十の位、60秒単位の商が分の一の位、10秒単位の商が秒の十の位です。最後に残る8が秒の一の位です。

この方法では、除数を一つ決めたら、その除数での減算を値が除数未満になるまで続けます。減算後に同じ比較へ戻ることで、商を正しく数えられます。次の桁に移るときは除数を切り替えます。桁数カウンタが正の間だけ次の除数の読込みへ戻すなど、内側の反復（同じ桁の商を求める）と外側の反復（次の桁へ進む）を区別します。