講義第10回：Pascal の基礎 --- 配列

配列

program calculate_sum(input, output);
var n : integer;
  data: array[1..100] of integer;
 i,sum: integer;
begin
    write('How many numbers you want to input?');
    readln(n);
    for i := 1 to n do readln(data[i]);
    sum := 0;
    for i := 1 to n do begin
        sum := sum + data[i];
        writeln('data[', i:2, ']=', data[i]:5, ', sum = ', sum);
    end;
    readln;
end.

var  data: array[1..100] of integer;

配列の便利なところは、まず、変数宣言で var data1,data2,data3, .... data100:integer と書くよりずっと短くて済む（100万個変数が欲しかったら 大きな違いである）ということ、それから実行部も簡潔な繰り返しで書けると いうことである。特に大事なのは、番号（添字）に変数が使えるということで ある。このことのために、上のように、ループの中で配列の要素を順番に見る とか値をいれるとかいったことができる。

実行例

How many numbers you want to input?5
2
3
4
5
6
data[ 1]=    2, sum =          2
data[ 2]=    3, sum =          5
data[ 3]=    4, sum =          9
data[ 4]=    5, sum =         14
data[ 5]=    6, sum =         20

ソート

program sort_data_from_file(input, output);
var n : integer;
  data: array[1..100] of real;
  i,j : integer;
  work: real;
begin
    n := 0;
    while not eof(input) do begin
        n := n +1;
         readln(input, data[n]);
    end;
    writeln('Input data');
    for i := 1 to n do write(' ',data[i]:5:2); writeln;
    for i := 1 to n - 1 do begin
        for j := i + 1 to n do begin
            if data[i] > data[j] then begin
                work := data[i];
                data[i]:= data[j];
                data[j]:= work;
            end;
        end;
    end;
    writeln('Sorted data');
    for i := 1 to n do write(' ',data[i]:5:2); writeln;
end.

1. まず、一番小さい数を先頭に持ってくる。そのために、配列の2番 目の要素から最後の要素までを順に見て、それが先頭の値よりも小さければ2 つを入れ換える。

2. これで先頭にもっとも小さい数が来た。次に、2番目の位置に残りの 数の中で最小のものを持ってくる。これには、配列の3番 目の要素から最後の要素までを順に見て、それが2番目の値よりも小さければ2 つを入れ換える。

3. 以下、同様に、 N-1 番目まで順にやっていく。

simple_sort < sample.dat

注意 コンパイルして作るプログラムの名前には sort は使わな いこと。これは、この名前の別のプログラムがあらかじめ準備されていて、そ ちらが実行されてしまうからである。

ソート（２）

こういうとむつかしげに聞こえるが、実際にやっていることは大したことでは ない。例えば、上にあげたソーティングについて考えてみる。

上の方法では、人間がやるとしたらとてもばかばかしくてできないような、手 際の悪い方法をつかっている。このために、手間がデータの数の2乗に比例し て増える。これを、もう少しなんとかできないものだろうか。

例えばトランプのカードを人が揃えるとすれば、一つの方法は、まずハート、 スペードといった種類ごとに分け、それからその中を揃えることである。こう すれば、枚数が減って扱いやすい。

もう一つの考え方は、まず揃ってない山を2つに分け、それぞれを揃える。そ れからその2つを合体させるというものである。合体させるのは、両方の山を みて順番が先なものをとっていけばいい。

どちらの方法でも、カードの山をいくつかに分けることで、手間を減らしてい ることがわかる。ここで、よく考えてみると、例えば下の方法では、初めに2 つに分けた山のそれぞれを揃えるのに、さらにそれらを2つに分けるという方 法が使えることが分かる。上の方法でもおなじようなことができる。

この、同じ方法を繰り返し使うというのが、「再帰」の考え方である。具体例 を見てみよう。

program mergesort(input, output);
var n   : integer;
    data: array[1..100] of real;
    wa  : array[1..100] of real;
    i,j : integer;
    infile:text;
    procedure merge(if1, ie1, if2, ie2:integer);
    var i, j, k : integer;
    begin
        i := if1;
        j := if1;
        k := if2;
        while (j <= ie1) or ( k <= ie2) do begin
            if (j > ie1) or ((k <= ie2) and (data[k] < data[j])) then begin
               wa[i] := data[k];
               k := k + 1;
            end else begin
               wa[i] := data[j];
               j := j + 1;
            end;
            i := i + 1;
        end;
        for i := if1 to ie2 do data[i] := wa[i];
    end;
    procedure msort(ifirst, iend:integer);
    var i : integer;
    begin
        i := (ifirst + iend) div 2;
        if ifirst < i then msort(ifirst, i);
        if i+1 < iend then msort(i+1, iend);
        merge(ifirst, i, i+1, iend);
    end;
procedure print(n:integer);
    var i : integer;
    begin
        for i:= 1 to n do begin
            write(' ', data[i]:9:2);
            if i mod 8 = 0 then writeln;
        end;
        if n mod 8 <> 0 then writeln;
    end;
begin
    n := 0;
    while not eof(input) do begin
        n := n +1;
         readln(input, data[n]);
    end;
    writeln('Input data'); print(n);
    msort(1,n);
    writeln('Sorted data');print(n);
    readln;
end.

1. まず、データを前半分と後ろ半分にわけ、それぞれソートしておく。

2. その2つを、それぞれ先頭からみて小さい方をとって並べていく。

1. のところを行なうのが、手続き msort の前半部である。これは、 前半分と後ろ半分について、それぞれ msort 自身を呼ぶ。

2. のところは、手続き merge で行なわれる。ここでは、 dataの if1 から ie1 までと、 if2 か ら ie2 までに入っている２つの部分列を、１つの列にまとめる。 この時、いったん wa という配列に書いておいて、終ったところで 書き戻す。

merge の動く様子

列a 1 3 4 8 9 列b 2 4 6 7 8 合併列 （空）
列a 3 4 8 9   列b 2 4 6 7 8 合併列 1
列a 3 4 8 9   列b 4 6 7 8   合併列 1 2
列a 4 8 9     列b 4 6 7 8   合併列 1 2 3

再帰という形に書くことで、高度な処理を単純な形に表現することがで きる。これについては次週にもう少し詳しく学ぶことにする。

練習

1. 最初の、合計を求めるプログラムを配列を使わないで書き直して みよ。また、合計だけでなく平均と標準偏差をもとめるように拡 張せよ。配列を使わないで標準偏差を求めることはできるだろう か。

2. 単純ソートのプログラムを手続きを使う形に書き直してみよ。メ インプログラムはマージソートの場合と同じように、手続きを呼 ぶだけの形になるようにすること。

3. 教科書のクイックソートのプログラムを実行してみて、うまく動くこ とを確認してみよ。また、なぜこれでうまくいくかを考えよ。

4. データの数を非常に大きくした時、実行時間がどうなるかを単純ソート プログラムと再帰を使うものの両方について測定せよ。配列宣言の数字を大き くするのを忘れないこと。また理論上どうなるはずか考えてみよ。

time simple_sort < sample.dat

0.040u 0.080s 0:00.56 21.4% 0+135k 2+0io 21pf+0w

レポート

• プログラム
• 実行結果
• 考察

makino-1@chianti.c.u-tokyo.ac.jp

1. 出力結果が画面に出たところで、 ~makino/bin/gfile というコマンド を実行する。これは、実行したウインドウとはべつのところで行 なうこと。
2. Enter file name: と聞いてくるので、名前をいれる。これは別にどん な名前でもいいが、例えば課題3の1 枚目ならkadai3-1 というように つけるのがいい。
3. しばらくすると、上の場合なら kadai3-1.uu というファイルができる ので、この中身をメイルにして送る。ただし、上に書いたように、こ れとプログラム、考察はまとめて1つのメイルで送ること。絵が何枚か ある場合も同じで、全体を1つのメイルでおくること。このためには mule の Insert-file (Ctrl-x i) などの機能を使う。

次回予告