アルゴリズム作成のガイドライン
プログラミング言語に依存しないアルゴリズムを記述することで、
- プログラムの本質的な処理手順を簡潔に表現できる。
- プログラミングをより系統的なものにできる。
- デバッグ作業や保守作業をより容易なものにできる。
といった利点を得ることができます。
そのため、プログラミングの際には、アルゴリズムを記述してからプログラムに変換する手順を
推奨します。
本ガイドラインでは、分かりやすく、保守しやすいアルゴリズムを系統的に記述
するための指針を示します。
ソフトウエアのモジュール設計やアルゴリズム構築を系統的に行なうための教育用ツールとして、
掛下研究室ではPerseusを開発しています。本ガイドラインに従ったアルゴリズム作成を系統的に
行なうために活用してください。
■ アルゴリズムの記述例 ■
- 有限性
- アルゴリズムは、仕様で定義されたどのような(有限の)入力に対しても、
有限回の操作で終了しなければならない。
- 確定性
- アルゴリズムの各操作は、明確に定義されており、誰が実行しても同一
の結果が得られなければならない。ただし、メッセージの内容など、処理の
流れと無関係な操作の記述は大まかなものでよい。
- アルゴリズムの各ステップは、仕様の中で使われている概念や用語を
使って記述する必要がある。プログラミング言語の用語(変数、整数、ポインタ等)
を使って記述することを避けること。これにより、プログラミング言語に
依存しない形式で手順の本質を記述できる。
- アルゴリズムの記法は、本ガイドラインに示したものを基本として使用
する。ただし、言葉の意味を変えない範囲で、必要に応じて細かい言い回しを
変更しても問題ない。
- アルゴリズムは、記述の洩れや余分な記述を含んではならない。
- アルゴリズムの各ステップは10行以下の単純なプログラムで記述でき
なければならない。
- アルゴリズム中で使用する変数は全てデータ構造として定義しなければ
ならない。データ構造の定義の際には、以下に示す標準的なデータ構造の用語を
用いて行い、プログラミング言語に依存しないように記述すること。
- アルゴリズム中で変数を指定する際にはデータ構造で定義した変数名を
用いること。
- 変数は変数名とデータ型を持つ。
- データ構造を定義する際には、アルゴリズムが必要とする全ての変数に
ついて変数名とデータ型を明示しなければならない。
- データ型は、単純データ型、配列、レコード、これらの組合せのいずれ
かによって定義する。
- 変数名について
- 変数名は当該変数が保持する情報を説明する具体的な名詞を用いなけれ
ばならない。(例:誕生日、身長、要素数)
- 変数名を考える際には、「この変数には●●●の情報が格納されていま
す。」という文を考えること。「●●●」に該当するできるだけ具体的な名詞
を用いると良い。
- レコードのフィールド名についても、同様に命名すること。
- 単純データ型
- 整数型、実数型、文字型、文字列型、論理型(真または偽のいずれかをと
る)、列挙型(あらかじめ定義された値のいずれかをとる)のいずれか。
- 配列
- 要素数と要素のデータ型を明示すること。
- レコード
- 各フィールドについて、フィールド名とフィールドのデータ型を明示す
ること。
- 基本制御構造
- アルゴリズムは、以下に列挙する基本制御構造(ブロック構造、条件判定、
繰り返し、ルーチン)だけを使用して記述する。
- ブロック構造
- ブロック構造は、順番に実行される操作の系列を記述するために使用する。
ブロック構造は、以下のように記述する。
(1) 操作1
(2) 操作2
(3) 操作3
:
(n) 操作n
- ブロック構造は、複雑な条件判定や繰り返し処理を記述するためにも使用する。
この場合には、ステップ(x)は、「○○の場合には以下の処理を実行する。」(条件判定)や、
「○○である限り以下の処理を繰り返す。」(繰り返し)などのように、
「以下の処理」というフレーズを含まなければならない。ステップ(x-1)〜(x-n)は「以下の処理」
の内容を具体的に示すためのものである。インデントを利用して以下のように記述する。
(x) 選択条件(または繰り返し条件)
(x-1) 操作1
(x-2) 操作2
:
(x-n) 操作n
- 条件判定
- 条件判定は、各種の条件を用いて場合分けを行なう場合に使用する。な
お、各条件が成立した時の処理を記述するために、ブロック構造を用いても良い。
(x) 条件1が成立するならば、以下の処理を実行する。
(x-1) 操作1
:
(y) 条件2が成立するならば、以下の処理を実行する。
(y-1) 操作2
:
:
(z) 条件nが成立するならば、以下の処理を実行する。
(z-1) 操作n
:
(w) 以上の条件が成立しないならば、以下の処理を実行する。
(w-1) 操作
:
- 「以下の処理」の内容が1ステップで記述できる場合には、単純な条件判定になる。
この場合には、以下の例のように単純化して記述するのが望ましい。
(x) ○○の場合には処理成功メッセージを表示する。
(x+1) そうでなければプログラムを終了する。
- 繰り返し
- 繰り返しは、指定された繰り返し条件が成立するまで、ある処理を繰り
返す場合に使用する。なお、反復対象の処理を記述するために、ブロック構造
を用いても良い。
- パターン1 (while反復)
(x) 条件○が成立している限り、以下の処理を繰り返す。
(x-1) 操作
:
- パターン2 (for反復)
(x) 以下の処理を△回繰り返す。
(x-1) 操作
:
- パターン3 (for反復)
(x) 集合○の各要素について、以下の処理を繰り返す。
(x-1) 操作
:
- 「以下の処理」の内容が1ステップで記述できる場合には、単純な繰り返し処理になる。
この場合には、以下の例のように単純化して記述するのが望ましい。
(x) ○○である限り次の文字を入力する。
- 繰り返し処理を記述する場合には、各回の繰り返しで処理されるデータ(または処理の内容)
ができるだけ明確になるように工夫する。
良い例 |
望ましくない例 |
・入力ファイルの各行について以下の処理を繰り返す。
・入力ファイルの各文字について以下の処理を繰り返す。
|
入力ファイルを読み終わるまで以下の処理を繰り返す。
|
テーブルに登録されている各学生について以下の処理を繰り返す。
|
テーブルの先頭から末尾まで以下の処理を繰り返す。
|
- ルーチン
- ひとまとまりで意味のある処理を記述するために、ルーチンを使用する。
- ルーチンを定義する際には、上述のブロック構造、条件判定、繰り返し
だけを使って記述しなければならない。
- 定義したルーチンを他のルーチンから呼び出すことができる。その際に
は、ルーチンの機能を用いてルーチンを指定する。
- 各ルーチンのアルゴリズムは20ステップ程度以下にまとめる。それ以上
の長さのものはルーチンを使用して分割すること。
- 各ルーチンの機能は明確かつ単純に表現できること。従って、複数の機
能を持つルーチンを定義してはならない。また、数ステップ程度の長さであっ
ても、独立した機能を持つものであればルーチンとして定義すること。
- 各ルーチンに対してその機能を説明したヘッダをつけること。なお、ア
ルゴリズムの本体に対応するルーチンには、「主プログラム」とすればよい。
- 各種のライブラリ関数をルーチンとして使用してよい。その場合、対応
するライブラリ関数名を明記すること。ステップの記述は不要。
Any questions and comments are welcome. Please contact to:
掛下 哲郎 (Tetsuro KAKESHITA) (kake@is.saga-u.ac.jp)