アルゴリズムは問題を解くための明確な手順
アルゴリズムは、ある問題を解いたり目的を達成したりするための手順です。例えば「複数の数から最大値を見つける」という目的なら、最初の値を仮の最大値にし、残りを一つずつ比べ、より大きい値があれば仮の最大値を置き換える、という手順にできます。入力は数の並び、出力は見つかった最大値です。手順を実行する人や機械が変わっても解釈が分かれないように、処理の順番、比較する条件、終わる条件を明確にします。
アルゴリズムとプログラムは区別します。アルゴリズムは処理の考え方であり、自然言語、図、擬似言語などでも表せます。プログラムは、その考え方を特定のプログラミング言語の規則に従って実行可能な形にしたものです。また、手順が正しいとは、例として与えられた一つの入力で答えが合うことだけではありません。空のデータ、同じ値が複数ある場合、探す値がない場合など、想定する入力の範囲で正しい結果になり、処理が終了するかを確認する必要があります。
同じ結果を出す方法が複数あることも重要です。名簿から名前を探すなら、先頭から順番に見る方法も、並べ替えた名簿の中央から範囲を絞る方法もあります。どちらを選ぶかは、データが整列済みか、探索を何度行うか、データがどの程度増えるかによって変わります。アルゴリズムを考えるときは、「答えが正しいか」と「無駄な処理がどの程度あるか」を分けて点検します。
順次・分岐・反復が処理の骨組みになる
複雑に見える処理も、基本となる制御の流れは順次・分岐・反復の組み合わせとして整理できます。順次は、書かれた処理を上から順に一度ずつ実行する構造です。「値を入力する」「税込みの金額を計算する」「結果を表示する」では、この順番を入れ替えると計算前の値を表示するなど、意味が変わります。代入は右辺を先に計算してから左辺へ保存するため、同じ変数を更新する式でも順序が結果を左右します。
分岐は、条件が成り立つかどうかで次の処理を選ぶ構造です。「得点が基準以上ならメッセージAを表示し、そうでなければメッセージBを表示する」のように、実行時にはどちらかの道へ進みます。条件の結果は真か偽のどちらかで、大小比較や等しいかどうかの比較を論理演算で組み合わせることもできます。よくある誤解は、分岐の両方を順番に実行すると考えることです。通常の二択分岐では、選ばれなかった側は実行されません。
反復は、決めた回数だけ、または条件が成り立つ間、同じ処理を繰り返す構造です。五つの値の合計なら、合計を0にしてから、値を一つ読むたびに加えます。このとき必要なのは、現在どこを見ているか、いつ次へ進むか、いつ終わるかの三点です。位置を更新し忘れると同じ要素を調べ続け、終了条件を満たせない無限ループになります。反復の中に分岐を置けば、「現在の値が仮の最大値より大きいときだけ更新する」という最大値探索になります。
フローチャートで流れと戻り先を描く
フローチャートは、処理を図形に分け、矢印で実行順を示す表現です。開始と終了は端が丸い図形、計算や代入などの処理は長方形、条件判断はひし形、入力と出力は平行四辺形で表すのが基本です。判断の出口には「はい／いいえ」など条件の結果を書きます。反復では、処理後の矢印を前の判断へ戻します。矢印が交差して読みにくいときは処理を小さく分けるか、図の向きをそろえます。
図を書くときは、最初に開始と終了を置き、その間へ入力・処理・出力を順次で並べます。次に、処理が選ばれる箇所を判断へ置き換え、最後に繰り返す矢印を追加します。この順番なら、終了へ到達しない経路や、条件を書いていない分岐を見つけやすくなります。「回数を一つ増やす」のような更新処理は、反復の矢印の直前にあるかを確認します。
フローチャート・手順表エディタで確かめる
- フローチャート・手順表エディタを開き、上部で「フローチャート」が選ばれていることを確認します。初期状態では、開始、入力、条件判断、処理、見直し、終了を矢印で結んだサンプルが表示されます。
- 左の「Mermaidコード」で、
check{条件を満たす？}が判断、process[処理を実行する]が処理を表す部分だと対応付けます。「いいえ」の矢印は「内容を見直す」から入力へ戻り、「はい」の矢印は処理から終了へ進みます。 - 「入力補助」にある「処理」「判断・分岐」「ループ」「入力/出力」の説明を読み、必要な図形のひな型を挿入できます。まず初期サンプルの図形内の文章だけを書き換え、右側のプレビューが更新されることを確かめます。
- 判断の「はい」と「いいえ」を順に指でたどり、どちらも終了するか、反復する側では条件を変える処理があるかを説明します。完成した図は画面の「PNG」「SVG」「PDF」から書き出せます。
フローチャートは図形の形を覚えることが目的ではありません。判断の前に必要な値が用意されているか、すべての矢印に行き先があるか、反復から抜ける条件があるかを目で点検するために使います。図が大きくなりすぎたら、まとまりを別の処理として切り出します。そのまとまりをプログラムにするときは、関数として名前を付ける考え方につながります。
擬似言語DNCLを1行ずつ読む
擬似言語は、特定のプログラミング言語の細部から離れ、処理の意味を読み取るための表記です。このサイトのDNCLトレーサーの例題では、gokei = 0が代入、Data[i]が配列Dataの位置iにある要素の参照、表示する(...)が出力です。=は右側の値を左側へ保存する代入、==は左右が等しいか調べる比較なので、同じ記号として読まないようにします。
「iを0から4まで1ずつ増やしながら繰り返す」は、iの初期値、終わりの値、増分を一行で示します。その次の字下げされた行が反復の本体です。「もし〜ならば」の下に字下げされた処理は条件が真のときだけ実行され、「そうでなければ」は偽の場合の道です。字下げが戻った行は、その分岐や反復の外側です。括弧やキーワードだけでなく、字下げの深さを縦にそろえて読むと、入れ子の範囲を見失いにくくなります。
プログラムのなぞり書きで確かめる
- プログラムのなぞり書きを開き、例題「合計を求める」を選びます。配列の番号は例題の記述に合わせて「0から」のままにします。
- 「1行ずつ動かす」を押し、「次の1行へ」で進めます。実行中の行には印が付き、右側の表には変数の中身が表示されます。値が変わった変数には「← 変わった」と示されます。
- 反復を進めながら、iが指すDataの値とgokeiを紙に二列で記録します。gokeiが0から3、4、8、9、14へ変わることと、最後の出力「合計は14」が一致することを確認します。「1行もどる」で一つ前の状態へ戻り、同じ行をもう一度進めても同じ変化になることも確かめられます。
- 次に「最大値を探す」を選び、saidaiが毎回ではなく、現在の要素のほうが大きいときだけ変わる行を探します。順次の中に反復があり、その中に分岐が入っている構造を、字下げと変数表の両方から説明します。
このツールではコードを書き換えたうえで再び1行ずつ実行でき、「はじめから」「1行もどる」「最後まで一気に」も選べます。読むときは、各行について「参照する値」「変更される値」「次に進む行」の三つを答えます。出力だけを先に予想するのではなく、途中の状態を表にすると、配列の番号のずれや初期値の誤りを見つけやすくなります。
線形探索と二分探索を比べる
探索アルゴリズムは、データの集まりから目的の値や位置を見つける手順です。線形探索は先頭から一つずつ比較します。並び方に規則がなくても使えますが、目的の値が末尾にある場合や存在しない場合は、すべての要素を調べます。途中で見つけたら終了するため、反復の条件には「まだ調べる要素がある」と「まだ見つかっていない」の両方が必要です。
二分探索は、整列済みのデータの中央を調べ、目的の値との大小関係から不要な半分を除きます。中央より目的の値が大きければ左側を、小さければ右側を候補から外し、新しい範囲の中央で繰り返します。最大の注意点は、整列されていないデータにはその判断が使えないことです。中央の値が小さくても、その右側に大きい値だけがあるとは限らないからです。
てじゅんカードで二つの探索を動かす
- てじゅんカードを開き、「順番に探す（線形探索）」を選びます。カード右側の▲▼、またはカードを選んだ後に現れる「ここに入れる」を使い、注目する、比較する、見つかったら終わる、違えば右へ移る、の順に並べます。
- 「採点する」を押します。不正解の場合は、先頭から何枚目まで正しいかと、見直す位置のヒントが表示されます。正解後に「実行を見る」を押し、「次へ」で箱の注目位置を進めます。例では5を探すために3、8、1、5の順で比べ、四回目で見つかります。
- 問題選択へ戻って「半分ずつせばめて探す（二分探索）」を選びます。全体を範囲にする、中央を見る、一致を確かめる、大小に応じて左右どちらかへ狭める、新しい中央から繰り返す、という役割を並べます。
- 正解後の実行では、整列された1、3、5、7、9、11、13から11を探します。最初に中央の7を比べた後、左側が「範囲外」になり、次の中央11で見つかる表示を確認します。線形探索は注目位置が一つずつ移り、二分探索は候補範囲そのものが縮む、と言葉で比較します。
整列は比較・交換・確定範囲に注目する
整列アルゴリズムは、数値の大小や文字の順序など、決めた基準でデータを並べ替える手順です。交換法では隣り合う二つを比べ、逆順なら入れ替えます。左から右まで一周すると、その範囲で最も大きい値が右端へ移動して位置が確定します。次の周では確定した右端を除き、残りを同じように調べます。
値を入れ替えるとき、AへBを代入してからBへAを代入すると、元のAは上書きされて失われます。そのため、元のAを一時的な変数へ保存し、BをAへ、一時変数をBへ移す三段階にします。DNCLトレーサーの「交換法で並べかえる」では、Dataの隣り合う要素と一時変数taihiがこの順で変わる様子を追えます。外側のiは確定済みの範囲を増やし、内側のjは現在比べる隣同士の位置を進めます。
選択法は、未整列の範囲から最小の値を探し、その範囲の先頭と入れ替えます。一周の途中で隣同士を何度も交換するのではなく、一周につき位置を確定させる交換を行う点が交換法と異なります。てじゅんカードには「となり同士をくらべて並べかえる（交換法）」と「いちばん小さいものを選んで並べかえる（選択法）」の両方があります。各問題を正解させて実行表示を進め、交換法では右側、選択法では左側から「確定」の箱が増えることを比べると、似た反復でも目的が違うと分かります。
「小さい順に並んだ」という結果だけでは、どのアルゴリズムか判断できません。どの要素を比較したか、いつ交換したか、どの範囲が確定したかを一コマずつ記録します。途中の配列が同じでも、次に選ぶ要素が異なる場合があります。最終結果ではなく途中状態を説明できることが、手順を理解したかどうかの確認になります。
計算量を入力の増え方から捉える
計算量は、入力の大きさをnとしたとき、比較や交換などの基本操作がどの程度増えるかを捉える考え方です。実行時間を秒で断定するものではありません。同じ手順でも端末や言語で時間は変わりますが、入力を二倍、十倍と増やしたときの増え方にはアルゴリズムの特徴が表れます。
線形探索は、最悪の場合にn個すべてを比べるためO(n)と表します。データが二倍なら比較回数もおおむね二倍です。二分探索は一回ごとに候補を半分にするためO(log n)です。候補が8個なら半分にする操作を三回、16個なら四回、32個なら五回で一つの候補まで絞れます。データが二倍になっても、必要な段階がおおむね一つ増えるだけ、という違いを表しています。
交換法や選択法は、未整列の範囲を端から端まで調べる処理を、範囲を一つずつ短くしながら繰り返します。比較回数はおおよそn×nに比例して増えるためO(n²)と捉えます。nが二倍になると仕事量はおおむね四倍になる、という直感です。O記法では、入力が十分大きくなったときに増え方を支配する部分へ注目し、定数倍や小さい項を省いて比べます。
ただし、計算量が小さい方法を常に選べばよいわけではありません。二分探索の前には整列が必要で、データを一度しか探さないなら、整列にかかる処理のほうが大きい場合があります。データを何度も探索するなら、先に整列しておく費用を後の探索で取り戻せます。データ数、現在の並び、操作する回数、実装の複雑さを合わせて判断します。
最後に三つのツールを往復します。てじゅんカードで手順の順序を組み、フローチャートで分岐と反復の矢印を描き、DNCLトレーサーで変数と配列の途中状態を追います。同じアルゴリズムを「カードの文章」「図形と矢印」「擬似言語」の三通りに置き換え、それぞれで開始条件、更新処理、終了条件を指し示せれば、表現が変わっても処理の骨組みを読み取れています。