アルゴリズムとは

プログラムを作るときの手順を大きな流れで示すと以下のようになる。

  1. 作りたいプログラムを考える
  2. それを作るためにどういう変数が必要か考える
  3. データを入力してなんらかの処理をして出力する方法を考え
  4. それぞれの流れをプログラムにする

実際にはプログラムを作りながらもっと別のやり方の方が良いなどと 考えながらプログラミングをしている。

たとえばごく簡単に、いくつかの数の平均値を求める場合を考えよう。 まず、「いくつかの数」というデータをどう保持するかについての知識がなけれ ばならない。既に我々は配列変数について知っているので、計算対象となる 数値は配列変数に入れておけば良いと理解することができる。

また、「平均値」を求める場合、

  1. 全部の数値を足して
  2. それを個数で割れば良い

ということを知っているので、実際に「全部足して個数で割る」ための 手順をC言語で書けば良いのだと分かる。配列変数に入っている数値を すべて足すときは、要素を一個一個足すのではなく、forによる ループを使えば一括処理できることを覚えたので、

 float average;
 int i, sum=0, point[50];
 char buf[100];
 for (i=0; i<100; i++) {
   if (NULL == fgets(buf, 100, stdin))
     break;
   point[i] = atoi(buf);
   sum += point[i];
 }
 /* iに人数が残る */
 average = (float)sum/i;

と書くことで見事平均値を計算できることになる。

ごく単純なプログラムだが、ここに到達するまでには、

ということについて考える必要があった。上記の二つは、互いに 深く結び付いていて、片方が決まると必然的にもう片方も決まる。 たとえば、forループを用いて合計値を計算するという部分は、 配列変数を利用するという決定がなければ利用し得なかった手順であろう。

このように、プログラムの中心となる問題解決部分を作成するために重要な ポイントは二つある。一つ目の、「現実世界のデータをプログラミング言語で表 現する形」のことをデータ構造、二つ目の「どういう 手順で処理するか」ことをアルゴリズムという。

どのような構造でデータを格納するかによって、それを処理するために必要 なアルゴリズムの難しさ複雑さが決まってしまう。とくに複雑な問題を処理する 場合には、あらかじめどのようなアルゴリズムで問題を解くかを考えてからデー タ構造を決めないとものすごい手間になってしまうので注意が必要である。

今回は、これまでに覚えたC言語の知識で表現することのできる 事象を解くアルゴリズムに関して考えることにする。アルゴリズムとは、 問題を解く「解法」を表す広い概念であるから、世の中に存在する すべてのアルゴリズムに触れることはもちろんできない。それらのうち、 プログラミングの初期の段階で有用なものをいくつか紹介する。

目次