アルゴリズムと流れ図

アルゴリズムと流れ図

アルゴリズムは日本語で「算法」です.JISでは「明確に定義された有限個の規則の集まりであって,有限回適用することにより問題を解くもの」と定義しています.つまり,ある問題をコンピューターに解決させる際の計算や処理の順序のことです.

アルゴリズムを表現する方法に流れ図(フローチャート)があります.流れ図に使われる記号で代表的なものを以下に示します.記号を線と矢印で結んだものが流れ図です.

端子 流れ図の最初と最後を示すための記号です.「開始」や「終了」等と書きます.また,サブルーチンの場合は開始のところにサブルーチン名を,終了のところに「出口」等と書きます.なお,1つの流れ図に「終了」や「出口」が2つ以上あってはいけません.
処理 処理を示す記号で,記号の中には処理の内容を記述します.また,変数に値を代入する場合は「変数名 ← 値」のように記述します.
判断 条件によって異なる処理をする場合の判断条件を記述する記号です.よって,この記号からでる線は2つ以上になります.
ループ(始端) ループ(繰り返し)の始端を示す記号で,ループの名前を書きます.ループの終了条件判定をループ開始前に行う場合は,終了条件も書きます.
ループ(終端) ループ(繰り返し)の終端を示す記号で,ループの始端と対応する名前を書きます.ループの終了条件判定をループを終了前に行う場合は,終了条件も書きます.
入力 キーボードからの入力を示す記号です.例えば,変数xの値を入力するときは「xを入力」と書きます.
出力 画面への出力を示す記号です.例えば,変数xの値を出力させるときは「xを表示」と書きます.
定義済み処理 定義済み処理(サブルーチン)を示す記号です.
帳票 帳票を示す記号で,印字をする場合にも使われます.
磁気ディスク 磁気ディスクを示す記号で,中にあるファイルを参照する場合に使います.ファイルの名前を書きます.
磁気テープ 磁気テープを示す記号で,上の記号と基本的に同じです.
入出力 媒体を特に指定しない入出力を示す記号です.

これらの記号を全部覚える必要はありませんし,本来の記号とは別の記号で書くときもあります.見る人にきちんと伝われば良いので,そこまで厳密に記号を使い分ける必要はありません(規格からはずれた書き方をするのはダメです).

Column

処理の流れは時計回りの方向へ読んでいくことになります.下から上へ,または右から左へ線が引かれている場合は,線を矢印にすると定められています.なお,線や矢印が交差してはいけません.

また,記号の中に書ききれない長い文を書く場合は,記号の中に「注1)」と書き,欄外に「注1)「~」を表示」とする方法もあります.ただし,この方法を乱用して長い文章を欄外にたくさん書くと,分かりにくいものになってしまいます.なるべく,処理の特徴を示すキーワードを図形の中に書き,補足を注として欄外に記述すべきです.

基本制御構造

アルゴリズムの3つの基本制御構造を説明します.

順次 順次(SEQUENCE)のアルゴリズムで,連続とも言います.命令文や機能のまとまりを上から下へと順に実行する構造です.命令の個数は問いません.
選択 選択(IF THEN ELSE)のアルゴリズムです.条件を判断して,その真偽により処理を選びます.この流れ図では条件が真のときのみ処理を実行しますが,両方に処理があっても,偽のときだけ処理があっても構いません.2つ以上の処理を実行させることもできます.
繰り返し(前判定) 繰り返し(DO-WHILE)のアルゴリズムです.終了条件が成立するまで処理を繰り返し実行します.終了条件の判定は処理を実行する前に行うので,処理が1回も実行されないことがあります.処理は2つ以上あっても構いません.

これらの基本制御構造を組み合わせれば,どのようなプログラムも記述できますが,実務上よく使われる制御構造として,拡張された制御構造(追加制御構造)があります.

選択 選択(CASE)のアルゴリズムです.この例では,A>Bのときに処理1,A=Bのときに処理2,A<Bのときに処理3を行います.分岐は3つ以上あっても構いません.
繰り返し(後判定) 繰り返し(DO-UNTILまたはREPEAT-UNTIL)のアルゴリズムで,終了条件が成立するまで処理を繰り返し実行します.終了条件の判定は処理を実行した後に行うので,必ず1回以上の処理を行います.処理は2つ以上あっても構いません.

上記の例で見たように,判断の記号における条件の書き方は複数あります.また,ループの終了条件の書き方も同様です.例えば,「A=8」と書くと,変数Aが8になったときにループが終了します.

その他に,列挙型の繰り返しという指定方法があります.変数に初期値を与え,ループするごとに変数の値を増加させる繰り返しです.この場合,終了条件はループの始端に書きます.

書き方は色々ありますが,「変数名:初期値,終了値,増分」と定めて「A:1,8,1」とすれば,A=1としてAを1ずつ増やして8になるまで繰り返すので,8回の繰り返しになります.

Column

繰り返しは判断の記号でも記述できますが,ループであることを分かりやすくするためには,ループの記号を用いた方が良いです.

goto文について簡単に説明します.ある場所からgoto文を使って,分岐を自由に作ることができます.しかし,goto文を乱用するとプログラムの流れを追うことが難しくなり,とこで何をしているのか分からない(スパゲッティのような)プログラムになってしまいます.

どんなアルゴリズムでも基本制御構造を使えば,goto文を使わずに表せます.

アルゴリズム設計

決定表(デシジョンテーブル)

アルゴリズムの表現には流れ図の他に決定表があります.問題を記述するときに起きる条件と,それに対して実行する動作を表の形で書くもので,JISで定められています.

表の構造を示します.

決定表の構造

条件指定部には条件記述部で書いた条件を満たしていればY,満たしてなければNと書きます.動作記述部に条件によって行う動作を書き,その動作を行うときは動作指定部にXを書きます.特に書く必要がない部分は-を書きます.

なお,条件指定部と条件記述部を合わせて条件部,動作記述部と動作指定部を合わせて動作部と言います.また,条件記述部と動作記述部を合わせて記述部,条件指定部と動作指定部を合わせて指定部と言います.

それでは,具体例を見てみましょう.

決定表の例

この例では,まず男性かどうかチェックします.男性なら「Mr.をつける」を実行します.男性でない場合(女性)で既婚女性なら「Mrs.をつける」を実行します.未婚女性であれば「Missをつける」を実行します.

条件が複雑な場合,流れ図より決定表を用いた方が良いこともあります.

再帰的アルゴリズム

再帰とは,あるサブルーチンの中で自分自身を呼びだすものです.例えば,0からn(n>0)までの整数の和Snを求めるとき,Sn=n+Sn-1(n≧1)であり,Sn=0(n=0)です.これを処理するアルゴリズムは次のように実現できます.

再帰的アルゴリズムの流れ図

この問題では,ループを使って単純にSnを求める方が分かりやすいですが,複雑な漸化式で定義される数列の,任意の項の値を求めるときに威力を発揮します.

ただし,何でもかんでも再帰を使えば良いわけではありません.この例では,nにどんな値が与えられても大丈夫にしなければいけません.もし,n>0ではなくn=0としてしまうと,間違って-8等の値が与えられてしまうと,半永久的に再帰が続きます.よって,再帰を使うときは入力チェックを厳密にしないといけません.

Topic

私の父の職場での話です.あるプログラマが書いたソースは,サブルーチン1がサブルーチン2を呼びだし,サブルーチン2がサブルーチン1を呼びだしていました.その結果,永久ループが発生し,アプリケーションが異常終了してしまいました(別の意味で再帰関数ですね).

漸化式がでたからすぐに再帰を用いるのは問題です.計算は正しく早くできますが,サブルーチンを次々と呼びだしていくため,ループを使って求めるよりもメモリを消費します.

Point

ある問題に対して,お互いに重なり合わないように問題を分割し,部分ごとに解を求め,全体としての解を作る問題解決の手法を分割統治法と言います.