アルゴリズム

要点と定義

アルゴリズムは、目的の結果を得るための処理手順です。流れ図を読むときは、処理の順序、条件による分岐、繰返し、変数の更新、終了条件を追います。近似計算では、二分探索のように判定結果で候補区間を半分に絞る方法があります。区間幅が一回ごとに半分になるなら、初期幅が1の場合、4回後は1/16、5回後は1/32です。終了条件が「未満」なら、境界と等しい段階では終了しません。この考え方と厳密な境界判定が、近似値を得る反復回数の判断に必要です。過去の出題で扱った補足です。

整列はデータを順序に並べる処理で、方式は要素の扱い方で見分けます。ヒープソートは、ヒープの根から要素を取り出し、整列済み部分へ移して未整列部分を縮めます。ヒープの順序関係によって、取り出す根が次の要素になります。この操作の特徴を捉えることが、他の整列方式との判別に必要です。過去の出題で扱った補足です。

再帰は、処理の中で同じ形式の処理を呼び出す方法です。終了には、基底条件があるだけでなく、呼出しが有限回でその条件に到達する必要があります。例えば、非負整数の階乗では、0の階乗を1とし、正の整数 n の階乗を n と n−1 の階乗の積で定めます。引数が一回ごとに1ずつ減るため、有限回で0に達します。この基底値と引数の変化が、再帰定義を正しく選び、終了するか判断するために必要です。過去の出題で扱った補足です。

入れ子になった再帰関数は、定義の条件を一段ずつ適用して値を求めます。外側の呼出しだけから値の増え方を決めず、内側の呼出しがどの条件に当たるかを確認します。この手順が、関数値を正しく判断するために必要です。過去の出題で扱った補足です。

ユークリッドの互除法は、二つの数を「割る数」と「余り」に置き換えながら最大公約数を求めます。x を y で割った余りを r とすると、x=qy+r です。d が x と y の公約数なら r=x−qy も割り切ります。逆に d が y と r の公約数なら x=qy+r も割り切ります。したがって、(x,y) と (y,r) は同じ公約数を持ち、最大公約数も保たれます。余りが0になったときの非零の値を答えとできる理由を判断するために、この両方向の関係が必要です。過去の出題で扱った補足です。

再帰の例として定義された関数の値を求めるときも、条件を順にたどります。例えば、第一引数が1の関数では、第二引数が0のときの値を出発点にし、正の第二引数について定義を展開して値を確かめられます。このような展開が、入れ子の関数呼出しの結果を求める判断に必要です。過去の出題で扱った補足です。

シェルソートは、離れた位置の要素から成る部分列を整え、間隔を段階的に狭めていく方法です。各段階で間隔を更新した後、終了条件を確認して次の整列へ進むか判断します。この更新と判定の順序が、指定された手順の反復回数を数えるために必要です。過去の出題で扱った補足です。

逆ポーランド表記では、演算子を対象となる値の後ろに置きます。例えば、二つの値を先に掛け、その結果に別の値を加える式なら、二つの値、乗算、加える値、加算の順です。スタックで評価する場合、値を積み、演算子が来たら必要な値を取り出して計算し、結果を戻します。演算の順序と、演算子より前に必要な値がそろっているかを確かめることが、表記変換を判断するために必要です。過去の出題で扱った補足です。

適用条件と例

併合は、すでに整列された複数の列を一つにまとめる処理です。例えば「2、6、9」と「1、5、8」を併合するなら、両方の先頭を比べて小さい方を出力し、その列の次の値を候補に加えます。これを繰り返すと「1、2、5、6、8、9」になります。各列が整列済みであることが、この方法をそのまま使う条件です。