このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
この講義ではアルゴリズムとデータ構造を学びます。 主に、触れる理論はグラフ理論とオートマトン理論です。 使用するプログラミング言語は C 、 C++ 、 Java です。 目標は大きなデータを処理するための手法を学ぶことと、 データファイルの解釈の基礎を学ぶことです。 但し、いきなりデータ処理に入るのではなく、 50 行から 200 行程度の規 模のプログラムを作る際の手法をまず学びます。
期末試験は行わず、評価はレポート二通で行います。
プログラミングの業界では「車輪を発明するな」という言葉があります。 これは、既知のさまざまな基本的なテクニックは自分で開発せずに、先人の残 したプログラムを利用すべきだということです。 しかし、この授業ではその車輪(つまり基本的なテクニック)について学びます。 そのため、 C 言語を使って車輪(基本的なテクニック)を発明するようなこ とをします。
一方、 C++ 言語には、基本的なテクニックがすぐに使えるように、それらを集めた STL(Standard Template Library)が使えます。 また、 Java には java.util というクラスライブラリがあります。 そこで、C 言語を使用して原理やテクニックを紹介しながら、 一方で、そのテクニックに対応する C++ や Java のライブラリの使用 法を説明します。
この講義はプログラミングの本当の基礎を学びます。 一年生の科目が算数でいう数字の読み書きに対応すれば、この科目は九九に対 応します。 易しいと言いませんが、基礎として非常に重要です。誤魔化さず完全に理解す るようにして下さい。 そのため、講義の予習、復習を十分に行うことが重要です。演習のプログラム は必ずコンパイルして実行して下さい。
この講義はいわゆる情報工学科で教わる内容の半分しか取り上げません。 特に、コンパイラを作ったり、思考型ゲームを作ったりはしません。 つまり、プログラミング能力をさらに高めるにはさらに色々なことを学ぶ必要 があります。
また、C, C++, Java はかなり似ていますが、世の中にあるプログラミング言 語には様々なものがあります。 講義で取り扱わない様々なプログラミング言語を学び、同様のプログラミング ができるようにすることは有益だと思います。 お勧めのプログラミング言語を下に記します。
これらは C と C++, Java の関係ほど近くありません。 したがって、学んでそれぞれ対比することにより、プログラミング言語の機能 とアルゴリズムがはっきり区別できるようになります。
この講義ではやや複雑なプログラム(50行から 200行くらい)を作成します。 これらを正しく作成するには多少の工夫が必要です。 ここでは、プログラムの開発上の手法を学びます。
プログラムを作成する上で重要なことは、いかに正常に動作することを保証す るかです。 そのために利用するのは、多くのプログラミング言語で実現されている プログラムの分割です。 しかし、どのように分割するかで、プログラミングの効率が変わります。 分割する上でもっとも重要なことは、分割する断面が単純で小さいことです。 そうでないと分割されたプログラムを組み合わせる際に困難が生じます。 例えば、単純にプログラムを前半と後半などに分割すると、前半と後半の関係 を全て考えなければなりませんし、後半部分だけをテストするのは非常に難しいで す。
そこで、良く使われている手法は「入力(必要な情報)と出力(得られる情報)が 単純ではっきりしている部分」を取り出すことです。このような部分が取り出 せれば、単純にその入力と出力の条件を満たすように自由にプログラムを作る ことができますし、その部分だけをテストすることも容易です。 入力が決まれば出力が決まるようなものを、数学では関数と言い ますが、C 言語や C++ 言語でも関数と言います。
例えば、 n 個のものから m 個のものを取り出す組合 せの数を考えます。この組合せの数は次の式で表せます。
これを素朴に定義通り計算することを考えます。
C 言語では関数という仕組みでプログラムを分割できます。 そこで、この計算をするのに階乗を計算してから最終的な値を求めることを考 えます。 つまり、階乗を計算する関数を作り、そして、その関数を元に組合せの数を求 めます。 さらに組合せの数を求める部分も関数として考えることができます。 つまり、 ある値の組合せの数を求めるプログラムは次の 3 つの部分に分割できます。
ここでは階乗を表す関数を factorial(n) と表すことにしましょう。 この関数は整数 n 与えられると、 n! の値となる整数を一つ返します。 C 言語で関数を使用するには、このように入力する値を丸カッコの中に入れます。 そして、得られた値は sin(x) などの数学の関数と同じように数式内で使うこと ができます。
factorial(n) の定義は、次のように行います。
int factorial(int n){
n から factorial の値を計算する仕方
return 求めた値;
}
最初の int は出力される値の型を表し、カッコの中の int は入力され る値の型を表しています。 factorial の計算法の中では入力された値は n を使っ て計算します。
さらに、組合せの数の計算も関数で書くと次のようになります。
int combination(int n, int m){
n と m と factorial 関数を使った組合せの数の計算の仕方
return 求めた値;
}
プログラムをまとめて書くと次のようになります。
#include <stdio.h>
int factorial(int n){
factorial の計算法
return 求めた値;
}
int combination(int n, int m){
factorial 関数を使った組合せの数の計算
return 求めた値;
}
main(){
int n,m;
printf("Input n and m: ");
scanf("%d%d",&n,&m);
printf("%dC%d = %d\n",n,m,combination(n,m));
}
このようにプログラムを 3 分割できました。 main() は combination(n,m) を呼び出し、 combination(n,m) は factorial(n) を呼び出します。 このようにすると、factorial や combination や main をそれぞれ別々 に作ることができますし、場合によっては複数の人間で作ることもできます。 また、それぞれの関数をテストすることも可能になります。
なお、今までプログラムを実行させるためにおまじないとして
main()
というものを書いて来ました。C 言語ではプログラムは
全て関数の形で書きます。つまり main()
も実は関数の一種で
す。
main という名前の関数はプログラム実行時に呼び出されると言う特別な関数
です。
なぜこの記述で main 関数が定義されるかですが、次の二つの省略のルールが
あるからです。
但し、出力の型を省略してしまうと、本来は値を返すべき定義であることを隠 してしまうので良い記述法ではありません(が、記述がシンプルになるという 利点はあります)。 さて、main 関数は int 型であると決まっているので、本来は値を返す必要がありま す。つまり return 文を書く必要があります。 返す値は stdlib.h に登録されていて、正常に main 関数を終了するには EXIT_SUCCESS, 異常終了するには EXIT_FAILURE を返します。但し、 EXIT_SUCCESS の代わりに 0 も使って良いので、 stdlib.h を読み込む代わり に 0 を返しても良いです。 なお、この返した値は OS から参照できます。 Windows の場合 ERROR_LEVEL 環境変数に値が渡されます。 ここで、もし、 return を記述しないと値は不定になります。 次に、 2 の省略を行った場合、後で説明するプロトタイプ宣言と互換性がな くなります。 そのため、通常の関数で引数なしを示すには void を記述すべきです。 main 関数にプロトタイプ宣言は要りませんが、記述を統一するためにも C 言 語 では main 関数でも void を記述した方が良いです。
一方、 C++ では出力の型を省略するとエラーになります。 また、引数が無いときは void を書かず、空の括弧が推奨されています。 さらに C++ では main 関数で return を省略すると、 return 0 が書かれた のと同じ処理になります。
以上をまとめると、以下の 1 のように記述していた main 関数は、今後、 2 のように記述するよう改めるべきです。
main(){
/* プログラム */
}
int main(void){
/* プログラム */
return 0;
}
int main(){
/* プログラム */
}
なお、C や C++ で作ったプログラムを起動する際に、引数を与えることがで きます。 その場合、main 関数は次のように記述します。但し、この講義では扱いませ んので、詳細は他の文献に譲ります。
int main(int argc, char *argv[]){
/* プログラム */
return 0;
}
main関数の引数にはこのように二種類の宣言の仕方があります。
さて、ここでプログラムのテストを考えます。 一つ一つの関数が正常な状態になるように、それぞれ別々にテストすることを 考えます。 では、まず factorial(n) をテストするにはどうすれば良いでしょうか?
C 言語で作ったプログラムを実行すると main 関数が呼び出されます。 他の関数は main 関数から呼び出すか、 main 関数から呼び出された関数から呼び出すなどしなければなりません。 従って、本来の完成したプログラムとは別にテストを行いたい場合は、本来の main 関数と別のテスト用の main 関数が必要になります。 しかし、異なる main 関数は同時に二つ以上存在できません。
C 言語では分割コンパイルという手法により二つの main 関数を 利用することができます。 分割コンパイルとは、プログラムのファイルを分割し、それぞれを別々にコン パイルし、最後に結合する手法です。 例えば、 factorial.c という factorial() 関数だけを含んだファイルを factorial.o という中間ファイルにコンパイルできます(これをオブジェクトファイル と呼びます)。別に combination.o と main.o というオブジェクトファイルを 作り、最後に factorial.o, combination.o main.o を結合して一つの実行 ファイルを作ることができます。このオブジェクトファイルを結合する ことをリンクと呼びます。
この手法を使うと、これとは別に、 factorial() をテストする main 関数を含む ファイル testf.c から testf.o を作り factorial.o と testf.o をリンクすれば factorial() をテストする実行ファイルを作ることができます。
gcc を使って factorial.c から factorial.o を作るには次のようにします。
gcc -c factorial.c
一方 factorial.o と combination.o と main.o から実行ファイル combination.exe を作るには次のようにします。
gcc -o combination.exe factorial.o combination.o main.o
ところが、combination.c は単純にはコンパイルできません。combination() は factorial() を呼び出しますが、factorial() の入出力の情報がないとコンパイ ラは呼び出しを処理できません。 そのため、入出力の情報を与える文を書く必要があります。関数の入出力の情 報だけの記述をプロトタイプと呼びます。 factorial() のプロトタイプは次のようになります。
int factorial(int n);
このようにプロトタイプは関数定義において実際の手続きの代わりに ;(セミ コロン)のみで終らせた形になります。 combination.c の最初にこれを書いておけば factorial() の計算法などは書かな くても combination.c をコンパイルすることができます。
なお、プロトタイプ宣言において、引数のない関数は必ず void を指定する必 要があります。省略するとエラーになりますので注意して下さい。
次の 3 つのファイルをそれぞれコンパイルし、一つの実行ファイルにリンク しなさい。
/* factorial.c */
int factorial(int n){
int i,result;
result = 1;
for(i=2;i<=n;i++){
result *= i;
}
return result;
}
/* combination.c */
int factorial(int n);
int combination(int n, int m){
return factorial(n)/factorial(m)/factorial(n-m);
}
/* main.c */
#include <stdio.h>
int combination(int n, int m);
int main(void){
int n,m;
printf("Input n and m: ");
scanf("%d%d",&n,&m);
printf("%dC%d = %d\n",n,m,combination(n,m));
return 0;
}
以下の手順を行います。
パーソナルコンピュータが普及するまではコンピュータが高額だったため、プ ログラム開発になるべくコンピュータを使用しない工夫がされてました。 まず、ウォーターフォールモデルという手順が用いられていました。 これは設計、コーディング、テストの工程を分割します。 そして、水が高いところが低いと ころへ流れるように設計を終えてから、プログラムを書き、プログラムを書い てからテストを行うという手法です。 このようにするとコンピュータを実際に必要とするのがテストの期間だけにな るので、コンピュータの使用料を減らすことが出来ます。 しかし、このような設計法では各工程が完璧に終らなければならないという、 まず不可能な仮定を前提としています。 実際は、テスト段階で重大な誤りが見つかることがあります。 そして、さらにその時にはプログラム作成が終了していますので、修正のため にほとんどが書き直しになったりします。
また、誤りが発見された時、それを人間がチェックしやすくなるよう にさまざまな書類が作られていました。 その中には、フローチャート、変数表、関数(サブルーチン)名表などがありま した。 問題が発生した時にはこれらを活用してコンピュータを使用せずに間違いを発 見していました。
しかし、パーソナルコンピュータなどでプログラムを開発する場合、このよう な手法や書類によりコンピュータの利用を節約する必要はありません。 したがって、プログラムのチェックやテストをコンピュータに自由に行わせた 方が良いです。
XP(エクストリームプログラミング)は、多くのプロ グラミングの効率的な手法を組み合わせたものです。 設計もプログラム作成もテストも同時進行させ、小さいプログラムを徐々に大 きくしていくような開発モデルです。 この中に「テストファースト」という手法があります。 これは、出来上がるプログラムより先に、それを自動的にテストするプログラ ムを先に作るというプログラミングスタイルです。 テストファーストにより、次のような利点が生じます。
テストは、エラーが生じそうな部分に対して書き、正常に動作することが明ら かな部分については省略します。
factorial() のテストの例を次に示します。
/* testf.c */
#include <stdio.h>
int factorial(int n);
int main(void){
int in[]={0,1,5,-1};
int out[]={1,1,120,-1};
int i,result;
for(i=0;in[i]!=-1;i++){
result=factorial(in[i]);
printf("factorial(%d)=%d: ",in[i],result);
if(out[i]==result){
printf("Ok\n");
}else{
printf("NG\n");
}
}
return 0;
}
この testf.c をコンパイルし、 factorial.o とリンクし、テストを実行しなさ い。
combination()をテストするプログラムを書き、実際にテストしなさい。 以後ここでできたプログラムを testc.c と呼ぶことにします。
main 関数をテストするプログラムはどのように書けば良いでしょうか? main 関数は、出来上がったプログラムを実行すると最初に呼び出される関数 ですから、main()を呼び出す関数を作ってもそれを実行することはできません。 そこで、main() をテストすには別の方法を考えます。 それは、main() 自身が呼び出す関数の単純なダミーを作っておき、 main() とリンクして、 特定の動作を main() にさせると言うものです。 組み合わせの数を求めるプログラムでは main() は combination() しか呼び 出しませんので、 次のように 5 と 2 を入れた時にだけ正常に動作するニセの combination 関 数を作ることで、 combination の計算に関わるところ以外の main 関数のチェッ クをすることができます。 このように呼び出し側をだますためのテスト用のダミーのプログラムを スタブと呼びます。
/* combination.c */
int combination(int n, int m){
if((n==5)&&(m==2)){
return(10);
}else{
return(0);
}
}
このプログラムを main() にリンクすることで、 main() が combination(5,2)を呼び出す時だけ main() をテストすることができます。
オブジェクト指向とは、プログラムの中で一つの独立した機能を、内部的に一 つのアプリケーションソフトのように扱うようにして、プログラムを分割する 技術です。 その独立した機能を持つものを オブジェクトと呼びます。 オブジェクトを操作するには、メッセージを利用します。 メッセージの多くは「動詞 + 目的語」の形をしていますが、この動詞のこと をメソッドと呼びます。 そして、オブジェクトは内部に記憶領域を持ち、メッセージを解釈しながら計 算を行います。
オブジェクト指向プログラミングでは作成すべきプログラムをオブジェクトに 分割します。 そして、それぞれのオブジェクトの必要な機能をメソッドとして登録し、メソッ ドの操作をプログラムとして書きます。 そして、それぞれのオブジェクトのテストを行った後、主たるプログラムでオ ブジェクトを操作するプログラムを書きます。
なお、本講義はオブジェクト指向を教えるのが目的ではないので、詳しい説明 は他の講義に譲ります。