アルゴリズム（演算法）とは、コンピュータを使ってある特定の目的を達成するための処理手順のことである。そしてそれをプログラミング言語を用いて具体的に記述したものがプログラムである。ここでは、プログラミングの慣用句とも言われるアルゴリズムについてまとめる。
アルゴリズムはプログラミングの「慣用句」
アルゴリズムはプログラミングの慣用句と言われる。それは、外国語学習によくたとえられる。自分の考えを相手にうまく伝えるために必要な知識は、単語や文法を丸暗記するだけでは十分ではない。会話でよく使われる慣用句を知ってはじめて、うまく会話できるようになるからだ。これがプログラミング言語を学ぶことは、外国語を学ぶことと似ていると言われる理由である。
１ 問題を解く手順が明確で有限回である
アルゴリズム（algorithm）とは演算法と訳され、「明確に定義された有限個の規則の集まりであって、有限回適用することにより問題を解くもの。たとえば、sin xを決められた制度で求める算術的な手順をもれなく記述した文」と定義されている（JIS：日本工業規格）。
わかりやすく言えば、アルゴリズムとは「問題を解く手順を、もれなく、文書や図（プログラム）で表したもの」である。
２ 勘に頼らず機械的に問題が解ける
コンピュータは自らものを考えることができない。したがって、コンピュータに与えるプログラムのアルゴリズムは、機械的な手順でなければならない。機械的な手順とは、何ら頭を使うことなく手順どおりにやれば必ずできるという意味である。
最大公約数（2つの整数に共通した約数の中で最大の値）を求めるという問題を機械的に解くアルゴリズムとして「ユークリッドの互除法」がある。ユークリッドの互除法には除算を使う方法と、減算を使う方法があるが、ここでは減算を使う方法を以下に示す。2つの数で大きい方から小さい方を引くこと（手順）を、2つの数の値が同じになるまで繰り返す（手順の終わり）。最終的に同じ数になったらそれが最大公約数である。
３ 定番アルゴリズムを知り応用する
プログラマが最低限知っておくべき定番アルゴリズムは、以下の7種類である。
- ユークリッドの互除法：最大公約数を求める
- エラトステネスのふるい：素数を求める
- 線形探索：データを探索する
- 2分探索：データを探索する
- ハッシュ法：データを探索する
- バブル・ソート：データを整列させる
- クイック・ソート：データを整列させる
こういった定番アルゴリズムを覚えるとともに、最小公倍数の求め方（2つの整数の乗算結果÷2つの整数の最大公約数）といったものを自ら考えて応用することが大事である。
４ コンピュータの処理スピードを利用する
コンピュータの処理スピードを利用することでアルゴリズムを考えてもよい。例えば「91が素数かどうかを判定する」といった問題を解くアルゴリズムには「エラトステネスのふるい」がある。これは、ある数の範囲にある素数を抽出するためのアルゴリズムであるが、基本的な考え方は「判定したい数より小さいすべての数で割ってみる」というものだ。他にも鶴亀算といった連立方程式を解くのにも、コンピュータの処理スピードを利用すればよい。
５ スピードアップを目指して工夫する
1つの問題を解くアルゴリズムは1種類だけとは限らない。もし複数のアルゴリズムが考えられる場合は、プログラムとして実行したときに処理時間の短い方が、よいアルゴリズムといえる。
例えば素数の判定では「判定したい数より小さいすべての数で割ってみる」という手順を工夫して「判定したい数の1/2より小さいすべての数で割ってみる」とすればよい。それは1/2より大きい数で割れるはずがないからである。
アルゴリズムの工夫の例として有名なものに「番兵」がある。番兵とは、探索を行う際に、一致するデータが配列に存在しない場合の終了条件として、配列の最後に付加する要素のことである。データがn件ならば、n+1件目に番兵を置く。番兵を置く理由は、それを用いないときよりもループ中の処理が減り、処理が早くなるからである（図１）。番兵は、複数のデータの中から目的のデータを見つける「線形探索」と呼ばれるアルゴリズムなどで利用される。「複数のデータを先頭から末尾まで１つずつ順番に調べて目的のデータを見つける」というのが線形探索の基本的な手順である。
図１．
番兵のイメージを伝える例として、真っ暗な夜に海岸の崖の上で行う危険なゲームが挙げられる。自分が立っている場所から崖まで100mある。1m間隔で様々な品物が置いてある。その中にりんごがあるかどうかを見つけるというものである。
まず番兵を使わない場合は、1m進むごとに品物を取り上げ、りんごかどうかをチェックする。それと同時に崖に達していないかどうかをチェックする（そうしないと海に落ちてしまうため）。この2つのチェックが何度も繰り返される。
番兵を使う場合には、スタート位置を崖から101mにして、崖の直前にりんごを置いておく（このりんごが番兵）。番兵を置いたことで、必ずりんごを見つけることになる。1m進むごとに行うチェックは、品物がりんごかどうかを調べるだけで済む。りんごが見つかったら、その時点で1回だけ一歩先をチェックする。まだ崖に達していないなら目的のりんごは見つかったのである。崖に達していた場合は、現在手にしているりんごは番兵であり、目的のりんごは見つからなかったことになる。
６ 数値の法則性を見いだす
コンピュータの都合の１つに「あらゆる情報を数値で表す」ということがある。このことからアルゴリズムとして、数値の中にある法則性を利用する場合がある。例えば、じゃんけんの勝ち負けを判定するアルゴリズムを考える。グー、チョキ、パーを0、1、2という数字で表すとする。Aさんが出した手を表す変数AとBさんの手を表す変数Bに、いずれかの数値が入っているとして、AとBの勝ち負けを判定するというものだ。
何ら工夫のないアルゴリズムでは、3×3=9通りの組み合わせを考えて勝ち負けを判定するだろう。しかしこれは長い処理になってしまう。
ここで、Aの勝ち、Bの勝ち、あいこの3つの結果を簡単に判定するための数値の法則性を見つけようと努力する。すると、以下の3つの法則性があることがわかるため、プログラムが単純になり、実行速度も速くなるのである。
- AとBが等しければ「あいこ」である
- B+1を3で割った余りがAに等しければ「Bの勝ち」である
- それ以外は「Aの勝ち」である
ほかにも給与計算を行う業務アプリケーションソフトを作成する場合には、給与を計算するルールが数値の法則性だといえる。「給与＝基本給＋残業手当＋通勤手当−源泉税」というルールを見いだせたならば、問題を解く手順が明確で有限回なため、立派なアルゴリズムとなる。
７ 紙の上で手順を考える
アルゴリズムを考えるときには、いきなりプログラムを打ち込むのではなく、まず紙の上に文書や図で手順を書いてみることが重要である。その形式は、フローチャートでも日本語の文書としての手順でも構わない。とにかく紙の上に書くことが重要である。
最後に
筆者は学生時代に統計は学んだものの、基本的には文系であった。そのためアルゴリズムと聞くと、その反対がヒューリスティック（発見的・経験則）であるという程度しか思い浮かばなかった。しかし、本項目を学ぶことで、非常に効率的で気持ちいい方法論であることが理解できた。
その昔、プログラマを目指す人なら必ず読むべきだといわれていた名著があったそうだ。それは、Niklaus Wirthの「アルゴリズム＋データ構造＝プログラム」（新訳は以下）である。アルゴリズムとデータ構造を知ることで、やっとプログラミングの知識が完成するということである。
次回はデータ構造についてまとめる。
 |
 |
