ログイン
kid's world

アルゴリズムとは

演算子や制御文などのC言語のパーツだけを知っていても知識としては十分ではない。目的を達成することができるかどうかは,優秀なアルゴリズムにかかっているのだ。


はじめに

前回は関数の作り方について解説した。関数にはいろいろな種類がある。引数もとらず戻り値も返さないような関数もあれば,引数を使って複数の値を一度に返す関数もある。

もちろん,複数の関数は使わずにmain関数1つだけでもプログラムは作れる。それなのになぜ関数を使うかといえば,プログラムのサイズを縮小でき,プログラマに対する負担を軽減することができるからである。関数は難しいことを簡単にしてしまう,ツールの1つである。どんなに複雑なプログラムも,実は簡単なことの集まりである場合がほとんどである。その簡単なものを1つ1つの関数として作っておいて,あとから積み木を重ねていくように組み合わせていけば,プログラマの負担はかなり軽減できる。つまり,「どの部分を関数にするのかがプログラム作成でもっとも重要である」といえるだろう。

今回のお話

今回は,「アルゴリズム」について解説する。プログラムは,アルゴリズムなしでは動かない。何らかの目的を達成しようとしたとき,その目的を達成するための手順を考えなければならない。その手順がアルゴリズムである。例として最大値を求めるアルゴリズムと,大きい順に並び換えるアルゴリズムについて解説する。

アルゴリズム

いきなり「アルゴリズム」といわれても,ピンとこないだろう。そこで,なぜプログラミングをするときにアルゴリズムを考えなければならないのかを解説しながら,同時にアルゴリズムの意味について理解してみよう。

日常生活で理解する

アルゴリズムといっても,難しく考えることではない。いつも人間はふだんの生活のなかで無意識にアルゴリズムを考えて,行動しているのだ。

たとえば,昼の12時から4チャンネルで放送されている番組をいつも見ているとする。今日もそろそろ昼の12時にさしかかってきた。そのときのあなたの行動を,Fig.1に1つ1つ細かく追ってみた。あたりまえの風景に見えるのだが,今の行動をプログラムで記述するとどうなるのかについて考えてみよう。

Fig. 1: 12時になると4チャンネルにセットする手順

1. 時計の針が12時にさしかかってきた
2. いつもの番組を見逃すわけにはいかない
3. あなたはテレビに目をやるが,電源が入っていなかった
4. そこで,あなたはリモコンを手にとり,電源ボタンを押した
5. しかし電源が入らない
6. 「そうか,主電源が入っていないのか」
7. そしておもむろにテレビの主電源を入れる
8. するとテレビには「1」という緑の文字とともに,天気予報の映像が流れた
9. あなたはとっさにリモコンをテレビに向け,「4」のボタンを押す
10. テレビに「4」の文字が大きく出たその次の瞬間,あなたの楽しみにしていた番組のタイトルコールが流れた

まずテレビの4チャンネルを見るという行動は,時計の針が12時を回りそうになるときに始まる。つまりプログラムの先頭では,while文などを使って,12時の少し前になるまで,次の文へ実行を移さないようにするのである。これをC言語ふうに書くとこんな感じになるだろうか。

while(現在時刻<11:55){
}

while文の中にはこのように何も書かずに,条件には「現在時刻が11:55未満のとき」と書いて,11:55になるまでは,while文でぐるぐると何もせずに回るようにするのだ。次に,テレビに目をやる。テレビには電源が入っているかもしれないし,入っていないかもしれない。したがって,if文を使って電源が入っていないときに電源を入れるようにしなければならない。イメージとしては次のようになる。

if(テレビの電源==OFF) {
  テレビの電源を入れる;
}

しかし,リモコンの使えるテレビには主電源もあるので,上のif文は次のように書き換えなければならない。

if(主電源==OFF) {
  本体の主電源を入れる;
}
if(電源が入っていない) {
  リモコンで電源ボタンを押す;
}

こうすれば,最初に主電源が入っていても/いなくても,主電源は入っているが電源が入っていないという場合でも,最終的にテレビのスイッチが入って映像が映ることになる。主電源を入れるだけでは電源が入らないという型のテレビにも対応できている。

4チャンネルを見ることが目的なので,次はチャンネルを4に切り替えなければならない。

しかし,最初から4チャンネルが映っているのならば何もする必要はないわけで,やはりif文を使ってそのような条件判断を行う。

if(チャンネル!=4) {
  リモコンの4のボタンを押す;
}

これで12時から4チャンネルの番組が鑑賞できるわけである。

実は,この手順が「12時から4チャンネルを見る」という目的を達成するためのアルゴリズムなのである。すなわち,アルゴリズムとは目的を達成するための手順である。目的を「問題」と置き換えるなら,その「解法」ともいえるだろう。

フローチャートを描く

このようなアルゴリズムの流れはフローチャート(流れ図)と呼ばれる図を使って表現することがある。フローチャートはJIS規格で定められており,これを使うことでアルゴリズムを視覚的に理解することができる。いい換えれば,フローチャートを使えば「自分の考えたアルゴリズムが正しいのかどうかを確認することができる」というわけだ。

そこで,先ほどのテレビの例をフローチャートで記述してみよう。

フローチャートに用いる記号はたくさんあるが,Table 1の基本的な4つの記号を覚えていればほとんどのアルゴリズムは記述できる。

Table 1: 代表的なフローチャート記号

/c/algorithm-table1.png

アルゴリズムの開始や終了は端子記号で記述する。すなわち,フローチャートの先頭と末尾は端子記号になっていると考えてよいだろう。処理は処理記号を使って記述する。

たとえば「リモコンの電源ボタンを押す」というのも,この処理記号で記述する。それぞれの記号の中には文字を書くことができ,具体的な処理の内容を内部に文字で記述することになっている。

アルゴリズムには必ず処理する順序,すなわち「流れ」があるわけだが,これは線記号で表すことができる。線記号は端子記号や処理記号を結び付ける記号で,通常は線記号で結ばれたそれらの記号は上から下へ順番に実行されていくこととなる。つまり,フローチャートは基本的に縦長の図になり,上から下へ読んでいくことになる。たとえば,Fig. 2は「開始→処理1→処理2→終了」の順番で実行されるアルゴリズムを記述したフローチャートである。もし上から下へ向かう線以外を描くときは,矢印で明示的に方向を指定する。

Fig.2: フローチャートは上から下へ読む

/c/algorithm-fig2.png

さらに,C言語の制御文であるif文/switch文/while文/for文を表現する記号として,判断記号がある。

判断記号は1つの入口と複数の出口を持つ記号で,内部に書かれた条件に合致している線へ処理を進めていくこととなる。たとえばFig. 3は,「こんにちは」を10回表示するアルゴリズムの例だ。

Fig.3: 判断記号の例

/c/algorithm-fig3.png

それでは,先ほど説明した12時から4チャンネルを見るアルゴリズムをフローチャートで記述してみよう。まずは読者自身でフローチャートを描いてみていただきたい。答えは1つとは限らない。私の場合はFig. 4のようなフローチャートを描いてみた。これを自分の描いたフローチャートと比べてみよう。

Fig.4: 12時から4チャンネルを見る

/c/algorithm-fig4.png


最大値を求める」へ進む

広告


©Toshio Koide 1996-2007.

目次

リンクについて

リンクは御自由にどうぞ。

メール

mail.gif

広告