生物生産科学科 担当 國分 尚（5月28日、6月4日、6月11日）
アルゴリズムとはある問題や物事に対して、それを解くあるいは実現するための手順のことで、算法などとも言う。もちろん、一つの問題について解法のアルゴリズムは一つとは限らない。例えば、２次方程式の解を求めるのに解の公式を使えばすべての場合に答えが出るが、簡単な因数分解でできることもある。コンピュータの場合はニュートン法を使うことが多い。
アルゴリズムは一見複雑な問題をうまく解くための手順であり、これをコンピュータが実行できるようにしたものがプログラムである。
例えば、かけ算は習ったが、分数はまだ知らない小学生にいきなり分数のかけ算の問題を出しても答えがわかるはずはない。しかし、分数のかけ算はまず分子同士を掛けてその答えを書き、その下に横線を引いてさらにその下に分母同士のかけ算の答を書く、という手順を教えれば一応の解答は得られる。（約分の手順、つまり最大公約数を求めることは大変良いプログラムの例題なので、一度紙に書いてみるとよい。）
コンピュータに何かをさせる場合もこのように手順を細かく書いてやれば良い。特に解き方はわかっているが、手間がかかりすぎて人の手では計算できないことはコンピュータにおあつらえ向きの仕事である。例えば、1000番目の素数は何か、などプログラムは簡単に書けるが、手ではやりたくない。
プログラムはあるプログラミング言語で書かなければならないが、アルゴリズムそのものは普遍的であり、すべてのプログラムに共通である。とは言っても、プログラミング言語に機能が欠けている時はアルゴリズムを変更する必要もある。例えば、再帰的アルゴリズムはBASICやFORTRANでは実現できない。
あとで実際にプログラムに書き換えてみるが、今の1000番目の素数を求めるアルゴリズムは次のように書ける。これはしらみつぶし法と言う最も単純だが効率の悪いアルゴリズムであり、アルゴリズム事典のような参考書にはもっと賢いアルゴリズムが紹介されている。
アルゴリズム１．1000番目の素数を求める
2以外の偶数は素数ではないことに注目し、3から順にすべての奇数について素数であるかどうかを調べ、素数が１つ見つかるごとにカウンターを増やしていって、カウンターが1000になったらその素数を打ち出して終了する。
これではプログラムに書きにくいのでこれを土井・筧（1987）の記法で書き直すと、次のようになる。素数の判断部分は省略した。
アルゴリズム２．（概要）
●注目する奇数を3とする ●カウンターを2とする（これから見つけようとしている奇数、3は2番目） ■カウンターが1000以下である限り繰り返す ▼注目する奇数が素数であるなら ●注目する奇数を最後に見つかった素数として覚えておく ●カウンターを1増やす ●注目する奇数を次のものにする ●最後に見つかった素数を出力出力して終了する
ここで、●で始まる行は何かの操作を示す。■で始まる行は次の１段下げてある部分を繰り返すことを示す。▼は条件に当てはまるかどうかによって次の１段下げてある部分を実行する。
それでは、上の「素数であるなら」というのは具体的にどうすればよいだろうか。もう少し詳細に考えてみると、次のように書ける。
素数であるかどうかの判断は、調べたい数をまず３で割る。割り切れれば素数でないと判断する。割り切れなければ次の奇数である５で割ってみる。割り切れれば素数でないと判断する。割り切れなければ次の奇数である７で割ってみる。割り切れれば素数でないと判断する。割り切れなければ次の奇数である９で割ってみる。
・・・と繰り返していき、除数が調べたい数の1/3より大きくなったら素数であると判断する。
以上をまとめてもう少しプログラムらしく書くとこのようになる。
アルゴリズム３．（詳細） ●nを3とする（いま注目している奇数、3から始める） ●cを2とする（今見つけようとしている素数はc番目である） ●lastを2とする（最後に見つかった素数、3の１つ前は2） ●targetを1000とする（これを変えると任意の位置の素数が求められる） ■cがtarget以下である限り繰り返す ▼nが素数ならば ●lastをnとする ●cを1増やす ●nを2増やす（次の奇数を対象とする） ●lastを出力する 素数の判定（対象の数はnに入っている） ●iを3とする（除数、3からの奇数で割っていく） ■i =< n/3 であり（n/3より大きい数が約数になることはあり得ないので）、 なおかつnをiで割った余りが0でない限り ●iを2増やす（次の奇数） ▼i > n/3ならば ●素数であると判断する そうでなければ ●素数ではないと判断する
ここまで細かくアルゴリズムを分解すればたいていのプログラミング言語にすぐに書き出すことができる。
第２章 -->
2004年5月14日作成、2004年8月24日更新
國分 尚