(24.1) 「乱数」が数学でどう定義されるかは、ここでは考えない。 計算機でいう乱数とは、 種（たね）と呼ばれる整数を元に漸化式を使って発生させる、 乱数のように見える数列のことである。
(24.2) 関数 rand() は、小カッコの中には何も書かずに呼び出す。 呼び出されるたびに、 0 以上 RAND_MAX 以下の整数（int 型）に値をとる乱数の項を、 一つずつ返す。 次のプログラムは、 一行に一つずつ、全部で 10 個の整数を出力するが、 これらの並びが乱数、というわけである。
#include <stdio.h>
#include <stdlib.h> /* rand() */
main() {
int i;
for (i = 0; i < 10; i++) { /* 10 項からなる乱数列を発生 */
printf("%d\n", rand());
}
}
※ ２行目。関数 rand() を使うには stdlib.h を #include することが必要である。 どの関数を使う際にどの .h ファイルが必要になるのかは、 この授業ではそのつど教える。また、K&R2 の付録に書いてある。 「/* rand() */」は、 「rand() を使うためにこの行を書いた」という覚え書きである。
(24.3) RAND_MAX はコンパイラごとに違う値を取り得る定数なので、 次のプログラムで調べておこう。
#include <stdio.h>
#include <stdlib.h> /* RAND_MAX */
main() {
printf("%d\n", RAND_MAX);
}
興味のある人は値をメモしておこう。
(24.4) 上の (24.2) のプログラムは、毎回同じ乱数列を出力する。 それでは困るので、現在時刻を乱数の種（たね）にすることを考える。
#include <stdio.h>
#include <stdlib.h> /* rand(), srand() */
#include <time.h> /* time() */
main() {
int i;
{ /* この中カッコの中（乱数の種の設定）はわからなくてもよい */
unsigned seed = (unsigned)time(NULL); /* 現在時刻を取得して */
printf("乱数の種は %u です.\n", seed);
srand(seed); /* それを乱数の種に */
}
for (i = 0; i < 10; i++) {
printf("%d\n", rand());
}
}
センターの Linux でこのプログラムを動かすと、 現在時刻の秒未満は無視されるようである。
(24.5) ※ 種の値を出力させるのは、再現性のためである。 上のプログラムが出力した種を次のプログラム （乱数の種の設定の部分以外は省略）に入力すれば、 全く同じ乱数列が得られる。
{ /* この中カッコの中（乱数の種の設定）はわからなくてもよい */
unsigned seed;
printf("乱数の種を入力してください.\n");
scanf("%u", &seed);
srand(seed); /* それを乱数の種に */
}
(24.6) rand() % 100 とすると、 0 以上 100 未満の整数に値をとる乱数が得られる。 厳密に言えば、RAND_MAX の値によっては、 0 の出現率と 99 の出現率はわずかながら異なるが、 この授業ではそこまでは気にしないことにしよう。
(24.7) 練習問題：(24.4) のプログラムを、(24.6) のように改造し、 0 以上 100 未満の整数に値をとる乱数が得られること、 および、実行するごとにその乱数列が異なることを確認せよ。
(24.8) 乱数を使うと、 ユーザにランダムな数を与えて計算問題をさせるプログラムも書ける。 例えばこんな感じ。
33 + 14 = 47 正解です! 44 + 29 = 63 ブー!
(24.9) 自分で書いた関数のテストにも使える。 二つの自然数の最大公約数を求める関数 int gcd(int x, int y) を書いたとしよう。 自分でいくつかの値を入れることで、正しく書けていることを確かめるのはもちろんだが、 それだけでは入力する値が個人の癖によって偏ることがありえる。 かといって、すべての自然数の組で実験することは（事実上）不可能である。 このような場合、 乱数を使って得られた二つの自然数の最大公約数を求めてみる、 というテストが有効である。
(25.1) 以上で準備を終わり、この授業のテーマである「整列」にはいる。
88 98 20 82 31 53 22 10 12 91 92 79 95 50 19 58
上のような有限数列が与えられたとき、 これを小さい順に並べかえるプログラムのことである。 整列は「ソート (sort)」とも言う。 ただし、 「整列」「sort」の日常用語としての意味はこれとは少し違う。
(25.2) 次のプログラムを元に、 順次、書き足したり改良したりしてゆくが、 ソースファイル名は指定しないので、適当に決めよ。 ファイル名をプリントにメモしておくと、 あとで探すときに楽かも知れない。
(25.3) ※ 実際の仕事でコンピュータを使う際には、 数だけを並べかえたのでは意味がないのが普通である。 たとえば、 受験者一人一人に対応するデータ 「受験番号、国語の得点、数学の得点、英語の得点、合計点」 の組が受験者の数だけあり、それらを合計点の順に並べかえる、 というような操作をすることが多いであろう。 これから考えるのは、（いわば）合計点だけを並べかえるもので、 実地にはあまり役立たない。 また、Excel （エクセル）などの表計算ソフトはソート機能を持っているので、 応用上はそれらを使えばよい。
(25.4) ※ 同じ値があった場合にどちらを先にもってくるかは、 この授業では「どちらでもよい」としておく。
(25.5) 実用上は、それも問題になることがある。 たとえば、昔は、試験のあと、 成績優秀者の氏名と得点を掲示したことがあった。 それには、 元々は名簿の順に並んでいるデータを得点順に並べかえて上から何人かを選べばよいのだが、 もしも同点の学生がいた場合は次のように名簿の順にしておくのが普通である。
100 点 伊藤＊、田中＊＊、藤村＊＊
95 点 ...
そうではなく、次のように書いたとしよう。
100 点 藤村＊＊、伊藤＊、田中＊＊
95 点 ...
とすると 「同じ 100 点だけど藤村君が先頭にきているのは何か理由があるのかな」 と思われるのでうまくないかもしれない。
(26.1) 次のプログラム例を見ながら、 以下の説明を読むこと。 また、このプログラムは完全ではないので、 指示に従って自分で書き加える必要がある。
#include <stdio.h>
#include <stdlib.h> /* rand(), srand() */
#include <time.h> /* time() */
#define N 10
void init(void);
void print(void);
int a[N+1]; /* これで a[1] ... a[N] が使える。a[0] は使わない */
main() {
printf("配列の大きさは %d です.\n", N); /* 配列の大きさを出力 */
init(); /* 初期化 */
print(); /* 画面表示 */
}
void init(void) {
int i;
{ /* この中カッコの中（乱数の種の設定）はわからなくてもよい */
unsigned seed = (unsigned)time(NULL); /* 現在時刻を取得して */
printf("乱数の種は %u です.\n", seed);
srand(seed); /* それを乱数の種に */
}
a[0] = 0; /* 念のためこうしておく */
for (i = 1; i <= N; i++) {
a[i] = rand() % 99 + 1; /* N が小さいとき */
/* a[i] = rand(); /* N を大きくして実験するとき */
}
return; /* この return は普通は書かない */
}
void print(void) {
/* このコメントは消して、ここに関数 print() の本体を書く */
}
(26.2) 数列は、int 型の配列 a[ ] に入れることにした。 その大きさ N は、 容易に変えられるよう、 #define を使って書いた。
(26.3) Ｃ言語の配列は添え字が 0 から始まるので、普通は a[0] から a[N-1] までを使うことになるが、 ここではわかりやすくするため a[1] から a[N] までを使いたい。 それには、 「int a[N+1];」と宣言することで a[0] から a[N] までを用意し、 最初の一つ、a[0] は使わなければよい。
(26.4) 初めに、この配列を「初期化」する。 「初期化」とは、一般には初めのデータを代入することである。 ここでは乱数で初期化する。 この部分は関数 init() として独立させた。
(26.5) 「void init(void) {」で始まっているが、 最初の void はこの関数が値を返さないことを示す。 値は返さないが、ある働きをする、というタイプの関数である。 小カッコの中の void は、引数がないことを示す。 使うときは「init();」のように使う。 小カッコの中には何も書かない。 すでに出てきた、rand()がそうだった。
(26.6) 「a[i] = ...」という行が二つ並んでいる理由について、 以下で説明する。
(26.7) 考えながらプログラムを書いている間は、N の値を小さくとり、 ソートの過程で何度か配列の値を全て出力して、 ソートが進んでいることを確認する。 この段階では、 配列を初期化する際に代入する値は 100 未満で十分だし、 そのほうが大小の比較が容易である。 また、あとで説明するが、 これらの値は 1 以上としておくほうが、 プログラムの間違いを見つけやすい。 以上から、値の範囲は 1 以上 99 以下としよう。
(26.8) プログラムが完成したら、 N の値を何百万、何千万と大きくしての実験も行なう。 その際には、 同じ値が代入されている項がたくさんあるとうまくないので、 値の範囲は広ければ広いほどよい。 よって、配列には乱数の値をそのまま代入する。 すると、値の範囲は 0 以上 RAND_MAX 以下となる。
(26.9) そのため、init() の中には「a[i] = ...」 となっている行が二つあるのであった。 いまどの段階の作業をしているかに応じて、 一方を選び、他方はコメントとする。 すなわち、/* と */ とで囲む。 （コメントの中に /* があっても、それはコメントの一部とみなされる。 一方、コメントを入れ子にすることは許されない。 「/* 記号「/*」と「*/」とで囲まれた部分はコメント */」 と書くと、このコメントは最初の「*/」で終わることになり、 そのあとの（いわゆる）日本語はプログラムの一部とみなされて、 コンパイル時にエラーとなる。
(26.10) プログラムの末尾にある関数 void print(void) の本体を書け。 この関数は、配列に格納されている値を (25.1) に示したようなスタイルで、 すなわち、スペースで区切って一行に出力し、最後に改行するものとする。 数が一桁のときも二桁分の幅に出力されるようにせよ。 そのとき、十の位を 0 とするかスペースにするかは各自の趣味にまかせる。 （printf() の中で、 %d の代わりに %02d または %2d と書けばよい。）
(26.11) main() では init() と print() を続けて呼んでいるだけなので、 起動するたびに異なる乱数列が表示されるプログラムができたはずである。 （非常に短い間隔で起動すると、同じ乱数列になることもある。）
(26.12) ※ init() の 「a[i] = ...」 のもう一方を使うと出力はどうなるか？
(27.1) ソートプログラムの多くは、 互換、 すなわち配列の二つの要素の交換からできている。 そこで、まず、互換を行なう関数を書こう。
(27.2) §26 で完成させたプログラムに、 関数 void swap(int i, int j) を書き加えよ。 この関数は、 要素 a[i] と a[j] の値を入れかえるものとする。 i と j が正しい範囲にあるかどうかはチェックしなくてよろしい。 そのことは、この関数を呼び出す際に注意するものとする。 プロトタイプ宣言もつけ加えること。
(27.3) 次はダメな例である。
a[i] = a[j];
a[j] = a[i];
最初は i と j とは等しくないと仮定して書いてみて、 書けたものが i と j が等しいときも正しく動くかどうか考えよ。
(27.4) もちろん、 この関数を呼び出してみなければ、正しく書けたかどうかはわからない。 それには、main() の最後に次のように付け加えればよいだろう。
swap(3, 8);
print();
これで a[3] と a[8] が入れかわっていれば OK である。 ほかに swap(8, 3) や swap(3, 3) も試すこと。
(27.5) ※ swap(-1, 8) や swap(3, N+1) を実行させるプログラムは、 配列の添え字が範囲外になるので誤ったプログラムである。 そのことを理解したうえで、そういうプログラムを書いて実行してみよ。 ここのコンピュータでは、エラーメッセージなどは出ないであろう。 前者では a[8] に、後者では a[3] に、 配列の“外”にあった値がはいってくることになるが、 それは 0 であることが多い。確かめよ。
(27.6) ※ これから書くプログラムは、少しずつ複雑になってゆく。 その際、間違って swap(-1, 8) や swap(3, N+1) を実行するようなプログラムを書いてしまうことはよくある。 配列を初期化する際、値の範囲を 1 から 99 までとしておいたのは、 print() が 0 を出力したら間違いだとすぐにわかるためであった。 a[0] に 0 を代入しておいたのも同様の理由からである。
(28.1) 配列の要素 a[i] と a[j] を比較するには if (a[i] > a[j]) のように書けばよいわけだが、 あとの都合で、次のような関数にしておこう。
int comp(int i, int j) {
return a[i] - a[j];
}
こう定義したうえで if (comp(i, j) > 0) と書けば、 スピードの点で若干劣るが、同じことである。 プロトタイプ宣言も付け足しておくこと。
(28.2) main() の最後に（swap() のテスト用に書いた部分は消してから） 次のように書き足して実験してみよう。
if (comp(1, 2) > 0) {
swap(1, 2);
}
print();
どうなれば実験成功かは各自で考えること。