2006 年度「計算機基礎論3B」 2006-11-24

§25 配列

(25.1) 変数名には、a, b, x, y のような一文字はもちろん、sum, total のように二文字以上からなる文字列も使える。 英語の単語でなくてももちろん可。 x11 のように数字がはいっても構わないが、 数字で始まる 1x などは不可。 (使おうとしたらどうなるか?)

(25.2) x1, x2, x3 とあったら人間は関連のある変数だろうと想像するが、 コンパイラにとっては全く無関係な、ただの三つの変数である。

(25.3) 「配列」とは、 0 からある自然数までの整数で添字づけられた有限個の変数 x[0], x[1], x[2], ..., x[N-1] を一斉に定義し、一括して扱うものである。 K&R2 では §1.6 を参照。

(25.4) 配列を使った自明なプログラムの例を示す。

#include <stdio.h>

int a[10];      /* 配列の宣言。これで a[0], ..., a[9] が使える */

main() {
    int i, n;

    for (i = 0; i < 10; i++) {      /* 配列の要素に代入 */
        a[i] = i * i;
    }
    for (i = 0; i < 10; i++) {      /* 配列の要素を印字(=出力) */
        printf("%d\n", a[i]);
    }
}

(25.5) 「配列の宣言」の行。 こう書くと a[0] から始まる十個の int 型変数が使える。 すなわち、a[0], a[1], a[2], ..., a[9] が使える。 a[10] は使えない。うっかり使ってしまいやすいので注意。

(25.6) 「配列の宣言は main() の中カッコの外で行ない、 ほかの変数の宣言は main() の中カッコの中で行なう」 という規則があるわけではないが、 とある事情により、結果として、この授業ではこうすることが多い。 だからこれが規則だと思っておけばよい。 正確なところは K&R2 §1.10, §4.3 参照。

(25.7) 上のプログラムは、配列の大きさを N として、 次のように書くほうがよい。 配列の大きさを変えることが容易になるからである。 実際に変えて実行してみよ。

#include <stdio.h>

#define N 10

int a[N];       /* 配列の宣言。これで a[0], ..., a[N-1] が使える */

main() {
    int i, n;

    for (i = 0; i < N; i++) {       /* 配列の要素に代入 */
        a[i] = i * i;
    }
    for (i = 0; i < N; i++) {       /* 配列の要素を印字(=出力) */
        printf("%d\n", a[i]);
    }
}

(25.8) 前に (20.4) で書いたプログラムを配列を使って書き直してみた。 今回は「階乗の計算」「各項の計算」「部分和の計算」 に分けて計算・出力している。 前のプログラムで見せたように配列を用いなくても書けるのだが、 このほうが書きやすいなら、いまはこれでもよい。 (階乗を double 型に入れているのは、 あとの計算が double 型であることと、 int 型よりも double 型のほうが格納できる整数の範囲が広いからである。 このような判断は、いまは自分でできなくても構わない。)

#include <stdio.h>  /* 自然対数の底 e の計算、配列版 */

#define N 23

double f[N];    /* 階乗の値を入れる配列 */
double a[N];    /* 各項の値を入れる配列 */
double s[N];    /* 部分和の値を入れる配列 */

main() {
    int n;

    f[0] = 1;                       /* 階乗の計算 */
    for (n = 1; n < N; n++) {
        f[n] = f[n-1] * n;
    }
    for (n = 1; n < N; n++) {
        printf("%2d の階乗は %.0f です.\n", n, f[n]);
    }
    for (n = 1; n < N; n++) {       /* 各項の計算 */
        a[n] = 1 / f[n];
    }
    for (n = 1; n < N; n++) {
        printf("第 %2d 項は %.53f です.\n", n, a[n]);
    }
    s[0] = 1;                       /* 部分和の計算 */
    for (n = 1; n < N; n++) {
        s[n] = s[n-1] + a[n];
        printf("第 %2d 項までの和は %.53f です.\n", n, s[n]);
    }
}

(25.9) 次のプログラムは、 いままでのと比べると意味のあるプログラムである。

#include <stdio.h>  /* エラトステネスのふるいで 10000 以下の素数を全て求める */

#define KESITENAI 0                     /* 消してない */
#define KESITA 1                        /* 消した */

int a[10000+1];                         /* 配列 a[0], ... , a[10000] を宣言 */

main() {
    int n, i;

    for (n = 2; n <= 10000; n++) {      /* 配列の初期化 */
        a[n] = KESITENAI;
    }

    for (n = 2; n <= 100; n++) {        /* ふるいにかける */
        for (i = 2; n * i <= 10000; i++) {  /* n の倍数のうち */
            a[n*i] = KESITA;                /* 10000 以下のものを消す */
        }
    }

    for (n = 2; n <= 10000; n++) {      /* 結果の出力 */
        if (a[n] == KESITENAI) {
            printf("%d は素数.\n", n);
        } else {
            printf("%d は合成数.\n", n);
        }
    }
}

(25.10) ※ C言語では、配列の要素 a[i] の値を調べたり a[i] に代入したりするとき、 添字 i が正しい範囲にあるかどうかチェックしない。 もしも上のプログラムで誤って a[10001] に代入したとしても、 コンパイル時や実行時にエラーメッセージが出るとは限らない。 しかし、 プログラムが暴走したりおかしな結果が出たりすることは起こり得るので、 絶対にそのようなプログラムを書いてはならない。

(25.11) ※ 出力が大量になり、最初の部分がよく見えない場合などは、 「./a.out」の代わりに「./a.out | more」とする。 一画面分だけ出力されると「--続ける--」が出て止まるので、 スペースバーを押せば次の一画面分に進む。 Enter なら一行分だけ進む。 次に進まないでプロンプトに戻りたい場合は「q」を押す。

(25.12) ※ 上のプログラムは、第二のループで合成数の倍数も消しているので、 まだまだ効率をあげる余地がある。 しかし、出力が始まったときには第二のループは終わっているわけで、 このくらいの計算はコンピュータにとってはあっという間である。

(25.13) 自然数 a, b の最大公約数 d = gcd(a, b) の求め方や、 ax + by = d を満たす整数 x, y の求め方は代数学で習ったと思う。 a が 19, b が 5 の場合、次のように上から表を埋めてゆく。

 i      a[i]     b[i]     r[i]     q[i]     x[i]     y[i]
 0:      19        5        4        3
 1:       5        4        1        1
 2:       4        1        0        4
 3:       1        0        0        0        1        0
ここで r は余り、q は商である。 x, y は、一番下はすぐわかるので、埋めておいた。 ここを、下から上へと埋めてゆきたい。

ai+1 = bi, bi+1 = ri = ai - biqi を ai+1xi+1 + bi+1yi+1 = d に代入すると bixi+1 + (ai - biqi)yi+1 = d となる。 これを ai , bi で整理して aiyi+1 + bi(xi+1 - qiyi+1) = d を得る。 よって xi = yi+1, yi = xi+1 - qiyi+1 である。

これに従って、x[i], y[i] を下から埋めてゆく。

 i      a[i]     b[i]     r[i]     q[i]     x[i]     y[i]
 0:      19        5        4        3       -1        4
 1:       5        4        1        1        1       -1
 2:       4        1        0        4        0        1
 3:       1        0        0        0        1        0
のようになる。x = -1, y = 4 が答えである。

#include <stdio.h>

#define N 50

int a[N];
int b[N];
int q[N];
int r[N];
int x[N];
int y[N];

main() {
    int i;

    scanf("%d", &a[0]);
    scanf("%d", &b[0]);

    for (i = 0; b[i] != 0; i++) {
        q[i] = a[i] / b[i];
        r[i] = a[i] % b[i];
        a[i+1] = b[i];
        b[i+1] = r[i];
    }
    a[i+1] = 0;

    x[i] = 1; y[i] = 0;
    for (i-- ; i >= 0; i--) {
        x[i] = y[i+1];
        y[i] = x[i+1] - q[i] * y[i+1];
    }

    printf(" i      a[i]     b[i]     r[i]     q[i]     x[i]     y[i]\n");
    for (i = 0; a[i] != 0; i++) {
        printf("%2d:%8d %8d ", i, a[i], b[i]);
        printf("%8d %8d ", r[i], q[i]);
        printf("%8d %8d\n", x[i], y[i]);
    }
}

(25.14) ※ N を 50 にしたのは、 このコンパイラが扱える int 型の範囲ではこれで(たぶん)十分であることを別に確かめたからである。

(25.15) ※ C言語の規格では、負の数を含む割り算の余りは一通りに決まってはいない。 -10 % 3 は -1 かも知れないし、2 かも知れないのである。 よって、上のプログラムを負の数も扱えるように改良することは (ここでは)やめておいた。

§26 練習問題

(26.1) 思いつくままに書いたので、難易度はまちまちである。 いままでの知識で書けるかどうかよく確かめていないものもあるが、 とりあえずは最初の Fibonacci 数列に取り組んでみよ。 なお、配列が出てくるものは、 大きさを N とし、N#define を利用して簡単に変更できるようにするとよい。

(26.2)

  1. 第一項、第二項が 1 である Fibonacci 数列 (漸化式 an+2 = an+1 + an を満たす数列) の最初の十数項を出力するプログラムを書け。 配列を使っても、使わなくても書ける。 隣り合った項の比も出力するようにできるとさらによい。 (その場合は全て double 型変数にするのが簡単である。 この比は (-1 + 51/2)/2 = 0.618033... に収束する。)
  2. 配列を適当な数列で初期化し、 次にユーザに数を入力させる。 すると、それが「何番目の項に一致する」 「どれにも一致しない」などの結果を出力するプログラムを書け。
  3. 配列を適当な狭義単調増加数列で初期化し、 次にユーザに数を入力させる。 すると、それが「何番目の項に一致する」 「何番目の項と何番目の項の間にある」 などの比較結果を出力するプログラムを書け。
  4. 配列にユーザに数値を入力させるプログラムを書け。 正しく入力されたかどうか、最後に全て出力してみること。
  5. 配列にユーザに数値を入力させ、 それを別の配列にコピーするプログラムを書け。 正しくコピーされたかどうか、最後に全て出力してみること。
  6. 配列にユーザに数値を入力させ、 それを別の配列に逆順にコピーする (i.e. a[0]b[N-1] に、 a[1]b[N-2] に、…… a[N-1]b[0] に、 のようにコピーする) プログラムを書け。 正しくコピーされたかどうか、最後に全て出力してみること。
  7. ユーザに何個かの数値を入力させ、その階差数列を出力するプログラムを書け。
  8. ユーザに何個かの数値を入力させ、その最大値、最小値を出力するプログラムを書け。 それらが何番目に入力されたものかも出力できるとなおよい。 最大値・最小値が複数個あってもそのうちのどれか一つについて何番目かを出力するだけなら、 配列を使わずにも書ける。
  9. 上のエラトステネスのふるいのプログラムで、 間違って int a[10000]; と書いたらどうなるか試せ。 (たぶん何ともならないが、間違ったプログラムであることに変わりはない。)
  10. 上のエラトステネスのふるいのプログラムでは上限の「10000」 が固定されている。 #define を利用し、簡単に変えられるようにしてみよ。 そして、変えてみよ。 (上限は平方数に限るとしてその平方根を N とし、 N*N までの自然数について調べるプログラムにすればよいだろう。)
  11. 上のエラトステネスのふるいのプログラムで上限を変えたときの実行時間を調べよ。 実行時間は N あるいは上限のどんな関数になるだろうか? (上限が大きくなると出力にかなりの時間を食うし、 「date; ./a.out; date」としても開始時刻が画面から消えてしまうので、 結果の出力をしないように改変し、 ふるいにかけるところまでの時間をはかるとよいだろう。)
  12. 上のエラトステネスのふるいのプログラムを改変し、 素数だけを出力するようにせよ。
  13. 上のエラトステネスのふるいのプログラムを改変し、 合成数については最小の素因数を出力するようにせよ。 (これはちょっとむずかしいが、やりがいのある問題である。 配列に収める値が最小の素因数になるようにすればよい。)
  14. 上のエラトステネスのふるいのプログラムを改良し、 合成数の倍数を消している無駄を省け。 その上で上限を変更し、実行時間との関連を調べよ。 実行時間は N あるいは上限のどんな関数になるだろうか?
  15. 二つの自然数 a, b を入力すると ba で割った商を(たとえば)小数点以下 100 桁まで正確に出力するプログラムを書け。 ba より大きい場合のみに限ってもよい。 (double 型変数に代入して割るだけだと、こんな精度は出ない。 int 型に代入して、小学校で習った筆算のように割り算せよ。)


岩瀬順一