計算機基礎B - 13. 配列

この文書の URL は http://www.cc.kyoto-su.ac.jp/~mtkg/lecture/comp_B/2012/13.html です。

配列とは

数学では n 次元ベクトル x の各要素を表すのに x1, x2, ..., xn といった書き方をします。 この要素の番号のことを「添字」といいます。

x = (x1, x2, ..., xn)

配列 (array) というデータ構造を使うと、添字を使ってベクトルや行列、表になったデータなどを簡単に扱うことができます。

配列の宣言

配列を定義するには変数宣言のときに配列名と配列の大きさ（要素数）を指定します。 次のように宣言すると double 型で要素数 3 の配列 x が定義されます。

double x[3];                    /* x[0], x[1], x[2] が利用可能 */

配列の要素は x[0], x[1], x[2] のように表されます。 配列名に続く [ ] のことを「添字演算子」といいます。 C の配列の添字はつねに 0 番からはじまることに注意して下さい。 したがって、要素数 n の配列では 0 から n-1 までが有効な添字の範囲となります。

配列の例

次の例は、配列 a の各要素に先頭から 1, 2, 3, 4, 5 を代入し、逆順に表示するプログラムです。

/* work1301.c */
#include <stdio.h>

int main(void)
{
    int a[5];                   /* 要素数 5 の int 型の配列 */
    int i;

    /* 配列に値をセット */
    for (i = 0; i < 5; i++) {   /* i = 0, 1, ..., 5 */
        a[i] = i + 1;
    }

    /* 逆順に表示 */
    for (i = 0; i < 5; i++) {
        printf("%d\n", a[4-i]); /* 添字 4-i に注意 */
    }

    return 0;
}

エラーになる時は

範囲外の配列要素にアクセスすると、エラーメッセージが表示されたり、計算結果がおかしくなったりします。 例えば、要素数 10 の配列の 11 番目の要素にアクセスしようとした時などです。 このようなミスはなかなか見つけられないことがあります。 そういう時は -fbounds-check というコンパイルオプション利用しましょう。 このオプションを付けてコンパイルすると、配列の添字のチェックをしてくれます。

% gcc -fbounds-check work1301.c

ただし、このオプションを付けると動作が遅くなります。 正しく動作するようになったらオプションを外して、コンパイルし直して下さい。

配列の初期化

配列を初期化するには { } の中に各要素に対する初期値をコンマで区切って並べます。 要素数を省略することもできます。

int a[5] = { 1, 2, 3, 4, 5 };
int b[]  = { 1, 2, 3, 4, 5 };   /* 要素数を省略すると自動的に 5 となる */

右辺の要素数が不足する場合、残りの要素はすべて 0 になります。 逆に、右辺の要素数が多すぎるとエラーになります。

int a[5] = { 1, 2, 3 };             /* a[3] = 0, a[4] = 0 となる */
int b[5] = { 0 };                   /* 全要素を 0 で初期化 */
int c[5] = { 1, 2, 3, 4, 5, 6 };    /* エラー */

配列のコピー

配列 a から配列 b にデータをコピーするには、すべての要素についてひとつずつ代入する必要があります。 Fortran 90/95 のような配列名を使った代入 b = a はできません。

/* work1302.c */
#include <stdio.h>

int main(void)
{
    int a[5] = { 1, 2, 3, 4, 5 };
    int b[5] = { 0 };
    int n;

    /* 配列のコピー: b = a; は不可 */
    for (n = 0; n < 5; n++) {
        b[n] = a[n];
    }

    return 0;
}

練習問題

上のプログラムを修正して、配列 b が { 5, 4, 3, 2, 1 } となるようにせよ。

/* work1303.c */
#include <stdio.h>

int main(void)
{
    int a[5] = { 1, 2, 3, 4, 5 };
    int b[5] = { 0 };
    int n;

    /* 配列のコピー */
    for (n = 0; n < 5; n++) {
        b[4-n] = a[n];
    }

    /* 表示 */
    for (n = 0; n < 5; n++) {
        printf("%d\n", b[n]);
    }

    return 0;
}

配列に値を読み込む

配列に値を読み込み、それを逆順に並び替えてみましょう。 scanf の使い方はこれまでと同様です。

/* work1304.c */
#include <stdio.h>

int main(void)
{
    int a[5], n;

    /* 入力 */
    for (n = 0; n < 5; n++) {
        printf("a[%d]: ", n);
        scanf("%d", &a[n]);     /* & を忘れないように */
    }

    /* 並び替え */
    for (n = 0; n < 5/2; n++) { /* i = 0, 1 */
        int tmp;                /* ブロック内で一時変数を宣言 */
        tmp = a[n];
        a[n] = a[4-n];
        a[4-n] = tmp;
    }

    /* 表示 */
    for (n = 0; n < 5; n++) {
        printf("a[%d] = %d\n", n, a[n]);
    }

    return 0;
}

実行すると次のようになります。

% ./a.out
a[0]: 3
a[1]: 2
a[2]: 4
a[3]: 1
a[4]: 5
a[0] = 5
a[1] = 1
a[2] = 4
a[3] = 2
a[4] = 3

値の交換方法

x と y の値を入れ替えるのに

x = y;
y = x;

としてはいけません（どういうことが起こるか考えてみましょう）。 値を交換するには、作業変数をひとつ用意して

tmp = x;       /* x の値を作業変数に保存 */
x = y;         /* x に y の値を代入 */
y = tmp;       /* 保存しておいた x の値を y に代入 */

とする必要があります。

練習問題1

5個の整数を配列 a に読み込み、最大値を見つけるプログラムを作成せよ。

/*
  work1305.c - 最大値
*/
#include <stdio.h>

int main(void)
{
    int a[5], n, max;

    for (n = 0; n < 5; n++) {
        printf("a[%d] = ", n);
        scanf("%d", &a[n]);
    }

    max = a[0];                 /* 仮の最大値 */
    for (n = 1; n < 5; n++) {   /* n の範囲に注意 */
        if (a[n] > max)
            max = a[n];         /* 最大値を更新 */
    }

    printf("max = %d\n", max);

    return 0;
}

練習問題2

2つの3次元ベクトル x, y をキーボードから入力し、内積 x.y を計算するプログラムを作成せよ。

/*
  work1306.c - 内積の計算
  実行例:
  % ./a.out
  x[0] = 1
  x[1] = 2
  x[2] = 3
  y[0] = 4
  y[1] = 5
  y[2] = 6
  naiseki = 32.000000
*/
#include <stdio.h>

int main(void)
{
    double x[3], y[3], tmp = 0.0;
    int n;

    for (n = 0; n < 3; n++) {
        printf("x[%d] = ", n);
        scanf("%lf", &x[n]);    /* %f ではなく %lf */
    }

    for (n = 0; n < 3; n++) {
        printf("y[%d] = ", n);
        scanf("%lf", &y[n]);
    }

    for (n = 0; n < 3; n++) {
        tmp += x[n] * y[n];
    }

    printf("naiseki = %f\n", tmp);

    return 0;
}

多次元配列

2次元配列を使うと行列が扱えるようになります。 次の例は2行3列の2つの行列 A, B の和を求めるプログラムです。 行列の初期化子の対応関係に注意してください。

/*
  work1307.c
  行列の和
  A = ( 1 2 3 )   B = ( 3 4 5 )
      ( 4 5 6 )       ( 6 7 8 )
*/
#include <stdio.h>

int main(void)
{
    int ma[2][3] = { {1, 2, 3}, {4, 5, 6} };
    int mb[2][3] = { {3, 4, 5}, {6, 7, 8} };
    int mc[2][3] = { 0 };        /* 全要素を 0 に */
    int i, j;

    for (i = 0; i < 2; i++) {      /* i = 0, 1 */
        for (j = 0; j < 3; j++) {  /* j = 0, 1, 2 */
            mc[i][j] = ma[i][j] + mb[i][j];
        }
    }

    for (i = 0; i < 2; i++) {
        for (j = 0; j < 3; j++) {
            printf("%5d", mc[i][j]);
        }
        printf("\n");
    }

    return 0;
}

3次元以上の配列も使えますが、次元数の上限は処理系によって異なるようです。

本日の課題

1. 最小値

キーボードから5つの整数を入力し、その最小値を求めるプログラムを作成せよ。

/*
  work1308.c -- 最小値
 */
#include <stdio.h>

int main(void)
{
    int a[5], n, min;

    /* 入力 */
    for (n = 0; n < 5; n++) {
        printf("a[%d]: ", n);
        scanf("%d", &a[n]);     /* & を忘れないように */
    }

    /* 最小値を探す */
    min = a[0];                 /* 仮の最小値 */
    for (n = 1; n < 5; n++) {   /* n の範囲に注意 */
        if (a[n] < max)
            min = a[n];         /* 最小値を更新 */
    }

    printf("min = %d\n", min);

    return 0;
}

2. 平均値

キーボードから5つの整数を入力し、その平均値を求めるプログラムを作成せよ。

/*
  work1309.c -- 平均値
 */
#include <stdio.h>

int main(void)
{
    int a[5], n, sum = 0;

    /* 入力 */
    for (n = 0; n < 5; n++) {
        printf("a[%d]: ", n);
        scanf("%d", &a[n]);     /* & を忘れないように */
    }

    /* 総和 */
    for (n = 0; n < 5; n++)
        sum += a[n];

    /* 平均 */
    /* double 型の定数 5.0 で割ること */
    printf("mean = %f\n", sum / 5.0);

    return 0;
}

3. 行列の積

次のような3行3列の2つの行列 A, B の行列積 C=AB を求めるプログラムを作成せよ。

A = ( 1 2 3 )   B = ( 3 6 9 )
    ( 4 5 6 )       ( 2 5 8 )
    ( 7 8 9 )       ( 1 4 7 )

行列 C の (i, j) 成分 Ci,j は次のように計算される。

Ci,j = Σ Ai,k * Bk,j     (Σは k = 0, 1, 2 を渡る)

/*
  work1310.c -- 行列の積
  A = ( 1 2 3 )   B = ( 3 6 9 )   C = A B (行列積)
      ( 4 5 6 )       ( 2 5 8 )
      ( 7 8 9 )       ( 1 4 7 )
*/
#include <stdio.h>

int main(void)
{
    int ma[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
    int mb[3][3] = { {3, 6, 9}, {2, 5, 8}, {1, 4, 7} };
    int mc[3][3] = { 0 };        /* 全要素を 0 に */
    int i, j, k;

    /* C = A B */
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++) {
            /* 各 (i, j) について k に関する Σ を計算 */
            for (k = 0; k < 3; k++)
                mc[i][j] += ma[i][k] * mb[k][j];
        }
    }

    /* 結果表示 */
    for (i = 0; i < 3; i++) {
        for (j = 0; j < 3; j++)
            printf("%5d", mc[i][j]);
        printf("\n");
    }

    return 0;
}

チャレンジ問題

1. パスカルの三角形

以下の下三角行列はパスカルの三角形と呼ばれる。

1   0   0   0    ...    0
1   1   0   :           :
1   2   1   0
1   3   3   1   0
1   4   6   4   1   0   :
1   5  10  10   5   1   0
1   6  15  20  15   6   1

この行列を配列 int p[10][10] に作れ。 上三角行列はすべて 0 とし、第 0 列と対角要素をすべて 1 とすると、他の要素はすべて真上と左上の要素の和になる。

/*
  work1311.c -- パスカルの三角形
*/
#include <stdio.h>

/* プログラム中の IMAX という文字列を 10 に置き換える */
#define IMAX 10

int main(void)
{
    int p[IMAX][IMAX] = { 0 };      /* 全要素を 0 で初期化 */
    int i, j;

    for (i = 0; i < IMAX; i++) {
        /* 第 0 列に 1 をセット */
        p[i][0] = 1;
        /* 対角要素に 1 をセット */
        p[i][i] = 1;
    }

    /* 第 2 行から第 9 行まで */
    for (i = 2; i < IMAX; i++) {
        /* 第 1 列から 第 i-1 列まで */
        for (j = 1; j <= i-1; j++) {
            p[i][j] = p[i-1][j] + p[i-1][j-1];
        }
    }

    /* 結果表示 */
    for (i = 0; i < IMAX; i++) {
        for (j = 0; j < IMAX; j++) {
            printf("%5d", p[i][j]);
        }
        printf("\n");
    }

    return 0;
}

2. ルジャンドル多項式

ルジャンドル関数 Pn(x) は |x| <= 1 を満たす x に対して次の漸化式で定義される。

P0(x) = 1
P1(x) = x
Pn(x) = [(2*n-1) * x * Pn-1(x) - (n-1) * Pn-2(x)] / n   (n >= 2)

P5(x) の値を -1 から 1 までの x について 0.1 刻みで求めよ。

/*
  work1312.c -- ルジャンドル多項式 P5(x)
  データのプロット方法
  % ./a.out > p5.dat
  % gnuplot
  gnuplot> plot 'p5.dat' with line
*/
#include <stdio.h>

int main(void)
{
    double pa, pb, pc, x;
    int i, k;
    const int n = 5;

    for (i = -10; i <= 10; i++) {
        x = i / 10.0;
        /* P0, P1 */
        pa = 1.0;
        pb = x;
        /* P2, P3, .., Pn */
        for (k = 2; k <= n; k++) {
            /* 漸化式 */
            pc = ((2*k-1) * x * pb - (k-1) * pa) / k;
            /* 次の繰り返しの準備 */
            pa = pb;
            pb = pc;
        }
        printf("%15.10f %15.10f\n", x, pc);
    }

    return 0;
}

3. 黄金比の連分数展開

黄金比 (1 + √(5)) / 2 は次のような連分数で表される。

1 + √5                 1
-------   =   1 + ---------------
   2                       1
                   1 + ----------
                              1
                        1 + -----
                              :

右辺全体を X とすると、右辺第2項の分母が X に等しいから

         1
X = 1 + ---
         X

という関係が成立することがわかる（実際、この方程式を解くと黄金比が得られる）。 そこで次のような漸化式を考える。

            1
Xn+1 = 1 + ----     (n = 1, 2, ...)
            Xn

初項を X1 = 1 として、Xn の値が一定値に収束するまで計算を行い、結果が黄金比に一致することを確認せよ。 初項の値をいろいろに変えた場合について数値実験を行い、結果がどのように変わるか調べること。

/*
  work1313.c -- 黄金比の連分数展開
  Gn+1 = 1 + 1 / Gn という漸化式を計算する。
  初項 G1 はどうしたらよいかわからないので、いろいろ試す。
  (正の数ならなんでもよさそうである。)
  連分数の正しい計算方法は以下で議論されている。
  Numerical Recipes in Fortran 77, 2nd Ed., pp.163-165
*/
#include <stdio.h>
#include <math.h>               /* fabs(), sqrt() */

int main(void)
{
    double x, y;
    const double eps = 0.10e-8;

    /* 初期値の入力 */
    do {
        printf("Input G1 (> 0): ");
        scanf("%lf", &x);
    } while (x <= 0.0);

    /* 漸化式の計算 */
    while (1) {
        y = 1 + 1 / x;
        if (fabs(x - y) < eps)
            break;              /* 収束したらループから脱出 */
        x = y;
    }

    /* 結果表示 */
    y = (1.0 + sqrt(5.0)) / 2;
    printf("approx : %15.12f\n", x);     /* 近似解 */
    printf("true   : %15.12f\n", y);     /* 厳密解 */
    printf("error  : %15.10e\n", y - x); /* 誤差 */

    return 0;
}