手順とプログラム

要点と定義

アルゴリズムは、目的を達成するための処理手順です。流れ図や擬似言語で表し、プログラム言語で記述すると、コンピュータで実行できます。手順を読むときは、初期値、処理、条件判定、更新の順を確認します。

繰返しでは、初期値・増分・終値から実際に使われる値を列挙します。同じ更新式でも、繰返し変数の値が変われば結果も変わります。たとえば初期値1に毎回「2×繰返し変数」を加え、変数が1、2、3なら、値は1→3→7→13です。

合計を求める処理では、合計用の変数を0で初期化し、各回の値を加えます。1から4までを足すと、合計は0→1→3→6→10と変わります。

整数の割り算は「割られる数＝割る数×商＋余り」と表せます。余りは0以上、割る数未満です。たとえば49を11で割ると商は4、余りは5です。次の処理がこの余りを受け取り、11を5で割るなら、その余りは1です。出力のどれを次の入力にするかを追います。

終了条件を含む処理では、各回の比較・更新・終了判定の順番が大切です。二つの値の大きい方から小さい方を引き、等しくなれば終わる場合、98と42から始めると、組は(56,42)、(14,42)、(14,28)、(14,14)となります。終了時の値は14です。

選択では、条件に合う場合だけ処理します。たとえば1から7までを調べ、3で割った余りが0の値を合計するなら、該当する3と6を足して9です。条件判定と累積更新を分けて追います。

整列では、隣り合う要素を比べ、左が大きければ交換する処理を繰り返すと昇順になります。最大値を選んで整列対象の末尾へ移す手順では、対象が1個以上なら続ける条件の場合、1個だけ残った回も実行します。

線形探索は先頭から順に調べる方法で、整列されていない配列にも使えます。最悪の場合の比較回数は要素数に比例します。二分探索は整列済み配列の中央要素を手がかりに探索範囲を半分ずつ絞ります。

二桁以下の整数jの各桁の和は、jを10で割った商をkとすると、k＋(j−10×k)で求められます。kは十の位、j−10×kは一の位です。jが三桁以上なら、この式だけでは全桁の和になりません。

配列の各要素が1ならA、それ以外ならBを末尾に加える変換では、出力文字列から各位置の条件を逆にたどれます。出力がAABABなら、条件は「1、1、1以外、1、1以外」です。

二進数を整数に直すときは、右端から数えた位置ごとの重みを掛けて合計します。右から1、2、3番目の重みは1、2、4です。たとえば101は1×1＋0×2＋1×4＝5です。

適用条件と例

処理を表にするときは、各回の入力、条件、更新後の値を記録します。繰返し変数がどの値を取るか、更新後に終了条件を判定するのかも確認します。式と繰返し範囲を合わせて値の推移を再現できます。

商と余りを使う処理では、商と余りを混同せず、次の処理に渡る値を確認します。49÷11の余り5を次の入力に使うと、11÷5の余りは1です。