一週間で身につくアルゴリズムとデータ構造|入門編2日目：アルゴリズムの基本

アルゴリズムについて説明する前に、フローチャートについての説明をしたいと思います。フローチャートとは、フロー（流れ）の図（チャート）という意味で、アルゴリズムを記述するための図として、長い間愛用されてきました。

複数のダイアグラムを矢印によって結びつけ、それによってアルゴリズムの処理の流れを記述します。フローチャートのダイアグラムには、以下のようなものがあります。（図2-1.)

図2-1.フローチャートで使われる主なダイアグラム

例えば、これを用いて、「1～10の乱数を発生させ、その値が5以上ならその値の数だけ、"HelloWorld"という文字列を表示する」というプログラムのアルゴリズムを記述すると、以下のようになります。（図2-2.）

図2-2.フローチャートの例

この図を見てもわかる通り、入力された値が5以上であれば、その数だけ文字列を表示し、そうでなければプログラムが終了することがわかります。このように、フローチャートとは、プログラムを記述するうえで非常に便利なツールなのです。

アルゴリズムには、最も基本となる処理である、3つの処理があります。それは、以下の表のものです。（表2-1.)

表2-1.アルゴリズムの三大処理

名前	順次処理	分岐処理	繰り返し処理
読み方	じゅんじしょり	ぶんきしょり	くりかえししょり
内容	処理を記述した順番に実行する	条件により処理の流れを変える	条件が成立する間処理を繰り返す
流れ	図2-3.順次処理	図2-4.分岐処理	図2-5.繰り返し処理

全てのアルゴリズムは、必ずこの3つの処理の組み合わせから構成されています。このように、この3つの処理を組み合わせてプログラムを設計する方法論のことを、構造化プログラミングと呼びます。

とはいえ、この3大基本処理があるからと言って、それをすべてアルゴリズムと呼ぶことはできません。実は、ある処理がアルゴリズムとなるためには、2つの重要な条件をクリアしなくてはなりません。それが、正当性と停止性と呼ばれるものです。

アルゴリズムは、与えられた課題に対して正しい結果をもたらさなければなりません。これを、アルゴリズムの正当性と言います。アルゴリズムの正当性とは、指定された条件を満たす入力値が与えられたとき、必ず正しく動作する（正しい出力結果を得る）ことを保証することで示されるのです。

アルゴリズムの正当性を示す方法として、アサーションを用いる方法があります。アサーションとは、アルゴリズム（プログラム）の任意の位置で、その時点において、満たさなければならない条件が成立しているかどうかを判定することを言います。

アルゴリズムの正当性の上で、大事なのは、必ずアサーションが成立していることです。これを、部分正当性と言います。これは、「プログラムがその位置で停止すれば、その時点での答えは正しい」ということを保証します。

正当性と同じく、アルゴリズムにおいて重要な概念が、停止性と呼ばれるものです。アルゴリズムは、最終的には必ず停止しなくてはなりません。アルゴリズムの停止性とは、いかなる条件の入力値が与えられても、有限時間内に必ず正しく停止することを保証することで示されます。

アルゴリズムの停止性の証明には、反復処理の終了条件の判定に使用される変数などを見て、必ず有限回数の繰り返しで終了条件が成立するいことを証明する方法があります。永遠に繰り返され、処理が終わらない手順のことは、無限ループと呼ばれ、アルゴリズムとはなりえません。

以上の2つがアルゴリズムがクリアしなくてはならない条件です。

一週間で身につくアルゴリズムとデータ構造