アルゴリズムの条件判定と状態更新

要点と定義

アルゴリズムは、目的を達成するための処理手順です。流れ図や擬似言語では、順次処理、条件による分岐、繰返しを組み合わせて表します。手順を読むときは、各変数が何を表すか、どの条件で処理が続くか、反復のたびに何が更新されるかを追います。

条件分岐では、仕様にある境界値をそのまま条件に写します。例えば「63点以上76点以下の場合に追加判定する」なら、その範囲は両端を含みます。「77点以上なら該当」「63～76点なら別の合計を調べ、76点以上なら該当」という段階的な判定は、枝ごとの役割と境界を分けて読む必要があります。領域Bが62点なら追加判定せず、63点なら追加判定へ進み、76点もその範囲に入り、77点なら最初の判定で該当します。

論理和は、条件のいずれか一つ以上が真なら真です。箱詰めのように「重量が5 kg以上、または個数が4個」のどちらかを満たした時点で止める仕様は論理和で表します。両方を満たすまで続ける論理積とは異なります。

配列を使う処理では、添字の意味を区別します。例えばメロンを順に読む行番号を i、箱番号を j とすると、処理中の重量は集計表の i 行から取り、蓄積先は箱 j の合計欄にします。変数名だけで判断せず、参照先が入力データか、処理中の箱かを確かめます。

ビットマスクは、各位置の状態をビット列で表す方法です。文字列の各文字について、その文字が検索パターンのどの位置に現れるかを対応するビットに記録できます。検索パターン「ABACA」なら、Aのマスクは下位から1、3、5番目のビットが1になります。初期値を0にしてから、該当位置のビットを論理和で加えると、同じ文字が複数回現れても既存の1を保てます。

論理左シフトはビット列を上位側へずらします。下位から i 番目のビットを立てるには、1を i−1 ビット左へずらします。例えば i=3 なら「001」を「100」にし、3番目の位置を立てます。位置を一つずらす誤りを防ぐには、i=1のときシフト量が0になることを確かめます。

検索処理の状態変数は、入力を一文字読むたびに更新されます。典型的には、状態を左へずらして新しい先頭状態を加え、現在文字のマスクとのビットごとの論理積を取ります。論理積は両方の列で1の位置だけを残すため、現在まで連続して一致する候補を保てます。各反復で「更新前」「シフト後」「マスク適用後」を分けて追うと、状態の意味が分かります。

適用条件と例

判定の条件を作るときは、仕様文を条件式へ分解します。例えば「合計点が77以上、または63以上76以下で、別の合計が76以上」なら、次のように整理できます。

• 77以上なら該当。
• 63以上76以下なら、別の合計を確認する。
• その別の合計が76以上なら該当。
• それ以外は該当しない。

「以上」「以下」は境界を含みます。「未満」は境界を含みません。63、76、77など境界そのものを代入して、重複や抜けがないか確認します。