2004 年度「計算機基礎論３Ｂ」 2004-11-12

配列

「配列」というのは変数の列です。 K&R2 では §1.6 にあります。

#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]);
    }
}

#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++) {
            a[n*i] = KESITA;
        }
    }

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

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

プログラムの中止・一時停止・再開、more

練習問題の前に、エラトステネスのふるいのプログラムで次の練習をしておくとよい。

プログラムの実行を途中で中止するときは Ctrl+C を押す。
プログラムの実行を途中で一時停止するときは Ctrl+S を押す。
一時停止したプログラムの実行を再開するときは Ctrl+Q を押す、と習ったものだが、ここの linux は任意のキーで再開するようだ。

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

練習問題

配列を適当な数列で初期化し、次にユーザに数を入力させる。すると、それが「何番目の項に一致する」「どれにも一致しない」などの結果を出力するプログラムを書け。
配列を適当な狭義単調増加数列で初期化し、次にユーザに数を入力させる。すると、それが「何番目の項に一致する」「何番目の項と何番目の項の間にある」などの比較結果を出力するプログラムを書け。
長さ N の配列 a[0], ... , a[N-1] にユーザに数値を入力させるプログラムを書け。正しく入力されたかどうか、最後に全て出力してみること。（N は #define を利用し、簡単に変更できるようにするとよい。以下同様。）
長さ N の配列 a[0], ... , a[N-1] にユーザに数値を入力させ、それを別の配列にコピーするプログラムを書け。正しくコピーされたかどうか、最後に全て出力してみること。
長さ N の配列 a[0], ... , a[N-1] にユーザに数値を入力させ、それを別の配列に逆順にコピーする（i.e. a[0] を b[N-1] に、 a[1] を b[N-2] に、… a[N-1] を b[0] にコピーする）プログラムを書け。正しくコピーされたかどうか、最後に全て出力してみること。
ユーザに N 個の数値を入力させ、その階差数列を出力するプログラムを書け。
ユーザに N 個の数値を入力させ、その最大値、最小値を出力するプログラムを書け。それらが何番目に入力されたものかも出力できるとなおよい。最大値・最小値が複数個あってもそのうちのどれか一つについて何番目かを出力するだけなら、配列を使わずにも書ける。
第一項、第二項が 1 である Fibonacci 数列（漸化式 a_n+2 = a_n+1 + a_n を満たす数列）の最初の十数項を出力するプログラムを書け。配列を使っても、使わなくても書ける。隣り合った項の比も出力するようにできるとさらによい。（その場合は全て double 型変数にするのが簡単である。）
自然対数の底 e を計算するプログラムを、配列を使って書き換えてみよ。階乗 n! を入れる配列、1/n! を入れる配列、級数の部分和を入れる配列など、配列は各自で考えて必要なだけ作ること。
上のエラトステネスのふるいのプログラムで、間違って int a[10000]; と書いたらどうなるか試せ。
上のエラトステネスのふるいのプログラムでは上限の「10000」が固定されている。 #define を利用し、簡単に変えられるようにしてみよ。そして、変えてみよ。（上限は平方数に限るとしてその平方根を N とし、 N*N までの自然数について調べるプログラムにすればよいだろう。）
上のエラトステネスのふるいのプログラムで上限を変えたときの実行時間を調べよ。実行時間は N あるいは上限のどんな関数になるだろうか？（上限が大きくなると出力にかなりの時間を食うし、「date; ./a.out; date」としても開始時刻が画面から消えてしまうので、結果の出力をしないように改変し、ふるいにかけるところまでの時間をはかるとよいだろう。）
上のエラトステネスのふるいのプログラムを改変し、素数だけを出力するようにせよ。
上のエラトステネスのふるいのプログラムを改変し、合成数については最小の素因数を出力するようにせよ。
上のエラトステネスのふるいのプログラムを改良し、合成数の倍数を消している無駄を省け。その上で上限を変更し、実行時間との関連を調べよ。実行時間は N あるいは上限のどんな関数になるだろうか？

岩瀬順一