プログラマの仕事はツールを使うことじゃない，
プログラミングの本当の楽しさを味わおう

講師　矢沢　久雄

よいアルゴリズムの条件

　一つの問題を解くアルゴリズムは，決して一つだけではなく，複数存在する。そうなると，同じ答えを得られるアルゴリズムなら「よいもの」と「そうでないもの」があることになる。

図4●ダイエットのためのプログラム
　「鶴亀算」という問題を解くなら小学校のアルゴリズムで十分であるといえそうだ。連立方程式を使うアルゴリズムは，小学校の問題を中学校の問題に無駄に複雑化していることになり，よいアルゴリズムではなさそうである。一般的に，よいアルゴリズムと言える条件を以下にまとめておこう。

・必ず正しい答えが得られること
・プログラムの実行速度が速いこと
・手順がわかりやすいこと
・再利用できること

　4点，よいアルゴリズムの条件をあげたが，「再利用できること」に注目してほしい。再利用できるということは，類似した他の問題を解く場合にも同様のアルゴリズムが利用できるということである。

写真4●図4の実行結果
　鶴亀算のアルゴリズムは，例えば簡単な例を挙げると，「自動車と自転車が合わせて20台ある。タイヤの数の合計は56本である。自動車と自転車はそれぞれ何台ずつあるか？」という問題を解く場合に再利用できる。

　この場合は，自動車のタイヤを2つはずし，それをトランクの中にしまうのだ。そうすれば，すべてタイヤが2つの乗り物となり，鶴亀算と同様のアルゴリズムが利用できる。これで，問題を解くことができる。

アルゴリズムにも定石あり

図5●エラトステネスのふるい
　単純な鶴亀算に限らず，多くのプログラマや数学者によって，さまざまな問題を解くためのアルゴリズムが，現在も考案され続けている。同じ問題を解くアルゴリズムにもいくつかの種類があり，あるものはわかりやすいが実行速度が遅く，またあるものは難解だが実行速度が速くなっている。実行速度が遅くても，わかりやすいアルゴリズムの方が再利用しやすいことも事実である。

　これらのアルゴリズムには，このあとで紹介する「エラトステネスのふるい」や「ユークリッドの互除法」などのように発案者の名前が付けられ，特定の問題を解決する「アルゴリズムの定石」として広く知られている。実際のシステム開発においては，これらのアルゴリズムをそのまま使う場合と，プログラムの要件に合わせて，若干変更を加えてから使う場合がある。

　名前を付けられるほど素晴らしいアイディアでなくても，与えられた問題を解く手順はすべてアルゴリズムである。例えば，「ダイエットのために昼食を抜くべきかどうか？」という問題である。

　解く手順を「そのときの体重が60Kg以上なら昼食を抜く。そうでない場合は昼食を食べる」とする。これでもう立派なアルゴリズムである。その証拠に，問題を解く手順を明解に書き表すことができるし，それをプログラム・コードとして表すことも可能である。（図4[拡大表示]，写真4[拡大表示]）。

写真5●図5の実行結果
　逆に言えば，どんなに小さな問題であっても，それを解くためにはアルゴリズムが必要になる。プログラマの役目は，プログラム・コードをキーやマウスで入力することではない。与えられた問題を解くためのアルゴリズムを考えつき，動作するプログラムとして実現することである。

　アルゴリズムさえ考え付き，手順が明解になれば，それをプログラム・コードに置き換えることはとても容易な作業となる。なぜなら，アルゴリズムを特定のプログラム言語に置き換えることは，単語も構文も慣用句もわかった上で日本語を英語に翻訳するような単純作業となるからである。この作業に必要なのはプログラミング言語の知識だけである。

コンピュータのパワーを活用したアルゴリズム

図6●素数でない整数をふるい落とす
エラトステネスのふるいは，調べたい整数を，その整数より小さい整数で割ってみることで，素数かどうかを判定する。ふるいの目は割ることができるかどうかである。割れてしまえば素数ではなく，ふるいの目から落ちることになる
　それでは，鶴亀算よりちょっと難易度が高い，2つめの問題を出題しよう。素数であるかどうかを判定するアルゴリズムを考えていただきたい。素数とは，1とその数以外に約数を持たない整数のことである。1は素数でないという決まりになっているので，2，3，5，7，11，… などが素数であることになる。

【問題2】100以下のすべての素数を求めよ。

　素数を判定する手順には「エラトステネスのふるい」という名前が付けられた有名なアルゴリズムがある＊4。アルゴリズムの名前だけを聞くと，難しい数式や，常人には思いも付かないようなアイディアが使われているのではないかと思われるかもしれない。ここでまず皆さんなら，どうやって素数の判定を行うかを考えてみてほしい。

　「その整数より小さいすべての整数で割ってみればよい。しかし，そんな面倒な手順ではなく，もっとスマートな方法があるのではないか？」と思われるのではないだろうか。

　ところがなんと，これがエラトステネスのふるいのアルゴリズムなのである。ただし，与えられた整数は，その2分の1より大きい整数で割れることはないので，実際には「その整数の2分の1の整数から2までのすべての整数で割ってみて，割り切れるものがなかったら素数である」と判定するのである（図5[拡大表示]，写真5[拡大表示]）

図7●コンピュータのパワーで連立方程式を解く
　エラトステネスのふるいが「ふるい」と呼ばれる理由は，2から100までの整数をふるいに入れ，その中から素数でない整数をふるい落としていくイメージがあるからである（図6[拡大表示]）。

　人間とコンピュータは違うもので，コンピュータは繰り返しの単純作業に強い。エラトステネスのふるいは，同じ手順でも人間とは実行速度が違うコンピュータを使ってこそ，実用的となるアルゴリズムである。このように，決してスマートには見えないが，コンピュータのパワーを活用して問題を解くアルゴリズムも多く存在する。

　例えば，問題1の鶴亀算で示した連立方程式を解く場合，変数xと変数yの取り得る値が0～16（鶴と亀の合計）の範囲にあることに注目して，「変数xおよび変数yに0～16の範囲のすべての整数を代入し，連立方程式の2式が成り立つ整数の組み合わせを求める」というアルゴリズムを利用することもできる（図7[拡大表示]）。変数が取りうる値の範囲などにもよるが，コンピュータによってはこの方が高速なプログラムとなる可能性がある。