2000 年度「計算機基礎論3B」 2000-11-17

今回は、C言語の続きとして、くり返しと配列について学びます。

くり返しを含むCプログラム

いままでのプログラムは関数電卓でも代用できるものでした。 それに対し「これこれを 1000 回行なえ」のようにくり返しを含む計算は、 コンピュータを使うほうがずっと楽です。

C言語でくり返しを実行させる方法には for と while と do-while の三つがあります。 ここでは for と while だけを説明し、do-while はとりあげません。 まずは抽象的に説明しますが、 そのあとで実例が出てきますから、 合わせて理解してください。

    for (文1; 式2; 文3) {
        ...
    }
は次のように動きます。

もう一つの構文

    while (条件) {
        ...
    }
は次のように動きます。

for も while も、中カッコの中(ループ本体)が一度も実行されない場合があります。

== sum.c ======================================================================
#include <stdio.h>  /* ユーザが数を入力すると,1 からその数までの和を出力 */

main() {
    int i, n, sum;

    printf("いくつまで足しますか?\n");
    scanf("%d", &n);

    sum = 0;

    for (i = 1; i <= n; i++) {
        sum = sum + i;
    }
    printf("1 から %d まで足すと %d です.\n", n, sum);
}
===============================================================================

i++ は「i を 1 だけ増やせ」、 i-- は「i を 1 だけ減らせ」の意味です。 それぞれ「i = i+1」「i = i-1」と書いても同じこと。 これらは等式としては正しくありませんが、 「i に i+1 を代入せよ」「i に i-1 を代入せよ」の意味だからいいのです。 これと for 以外は、すでに習ったことばかりです。

上のプログラムで入力する数を 10, 100, 1000, 10000, ... のようにだんだん大きくしてゆくと、 どこかで int 型の限界を越えて答えがおかしくなります。 その場合でもエラーメッセージなどは一切出ません。

この例では for を使うほうが自然でしょうが、 次に while を使って書いてみました。

== sum2.c =====================================================================
#include <stdio.h>  /* ユーザが数を入力すると,1 からその数までの和を出力 */

main() {
    int i, n, sum;

    printf("いくつまで足しますか?\n");
    scanf("%d", &n);

    sum = 0;
    i = 1;

    while (i <= n) {
        sum = sum + i;
        i++;
    }
    printf("1 から %d まで足すと %d です.\n", n, sum);
}
===============================================================================

ここまでで何かプログラムを書いてみたい人は、 1 から始めて 1, 2, 4, 8, 16, ... と倍々になってゆく数列を表示するプログラムを書いてみてはどうでしょう?  2 の何乗で答えがおかしくなるでしょうか?

== arale.c ====================================================================
#include <stdio.h>  /* アラレ数 */

main() {
    int n;

    printf("自然数を入れてください.\n");
    scanf("%d", &n);
    while (n != 1) {
        if (n % 2 == 0) {
            n = n / 2;          /* n が偶数のとき */
        } else {
            n = 3 * n + 1;      /* n が奇数のとき */
        }
        printf("%d ", n);
    }
}
===============================================================================
アラレ数とは という漸化式で定義される数列です。 この数列は、初項がいかなる自然数であってもそのうち 1, 4, 2, 1, 4, 2, ... というループに落ち着くであろうと予想されているそうです。

このプログラムは、ユーザが入力した数から始めて 1 になるまで、 この数列を出力します。 この例では while を使うほうが自然でしょう。

※ このプログラムは全く改行を出力しないので、 終了後のプロンプトがおかしなところに出るなどの困った点がある。 これは私の手抜き。 直したい人は自分で考えて直すこと。

※ 「アラレ」は日本語の「霰(あられ)」である。 「arale」というつづりは鳥山明氏のマンガ「Dr. スランプ」の登場人物 「アラレちゃん」にちなんでいるだけで深い意味は全くない。:-)

※ ここで中カッコが入れ子になった場合のインデント (行の最初にスペースを入れること)のしかたを説明する。 上のプログラムの while の部分で確かめてみるとよい。

この方針を守っていれば、「ある中カッコと対応する中カッコをさがす」ことや 「ある文を囲む最小の中カッコをさがす」ことはきわめて容易である。

main() の直後の開き中カッコも同じ原理に従っていることに注意。 これが教科書などと違うこの方式を採用した理由の一つである。

== exp.c =====================================================================
#include <stdio.h>  /* 自然対数の底 e の計算 */

main() {
    int n;
    double sum, kaizyo;

    sum = 1;
    kaizyo = 1;
    n = 1;

    for (n = 1; n < 24; n++) {
        kaizyo = kaizyo * n;
        sum = sum + 1 / kaizyo;
        printf("第 %d 項までの和は %.25f です.\n", n, sum);
    }
}
===============================================================================

自然対数の底 e を e = 1/0! + 1/1! + 1/2! + 1/3! + ... として計算しています。 C言語には階乗を表わす演算子はないので自力で計算しなければなりません。 ここでは n! を計算した結果を捨てないで次の (n+1)! の計算に使っています。

なお、「kaizyo = kaizyo * n」のところでは double 型と int 型を掛けています。 こういった場合、結果は double 型になります。

※ 岩波「数学辞典第3版」1434 ページによれば e = 2.7182818284590452353... であり、 上のプログラムの計算結果は小数点以下 16 桁目で違っている。 むやみに桁数を多く表示させても意味がないときもある、 ということがわかっただろうか?

== tansindo.c =================================================================
#include <stdio.h>  /* 単振動 */

#define T 0.01          /* 時刻のきぎみ */

main() {
    double t, x, v;     /* 時刻,変位,速度 */

    x = 1; v = 0;       /* 初期条件 */

    for (t = 0; t < 10; t = t + T) {
        printf("時刻 %5.2f, 変位 %9.6f, 速度 %9.6f\n", t, x, v);
        x = x + v * T;  /* T だけ後の位置を計算 */
        v = v - x * T;  /* T だけ後の速度を計算 */
    }
}
===============================================================================

近似計算で微分方程式を解くプログラムの例です。 ここでは x を変位、v を速度、a を加速度とするとき微分方程式 「a = -x」を初期値 x = 1, v = 0 のもとで解いてみました。

時刻は T = 0.01 きぎみにし、 その間は等速運動をするとして T だけ後の位置を計算しているのが最後から二つめの文、 その間は等加速運動をするとして T だけ後の速度を計算しているのが最後の文です。

「#define T 0.01」というのは 「以後 T が出てきたら 0.01 で置きかえろ」ということでした。 「#define」を使わなくても T の代わりに 0.01 と書けば同じことですが、 時刻のきざみを変えてこのプログラムを試してみたいとき 「#define」を使っていれば「#define T 0.01」の「0.01」 だけを書きかえればよいのに対し、 「#define」を使っていなければ三箇所に出てくる T の値をすべて書きかえなければなりません。

このプログラムは非常にいい加減な近似をしています。 もっと精度のよいやり方は別の講義などにゆずります。

理論的にこの微分方程式を解けば x = cos(t) になります。 それとの差を並べて出力してみるのも面白いかも知れません。

※ プログラムが動いている途中、Ctrl+C で中止させることができる場合がある。 また、一時停止させるときは Ctrl+S を押す。Ctrl+Q を押せばまた動き出す。

※ プログラムの実行結果をファイルに収めるには Cut & Paste を利用してもよいが、 「リダイレクトとパイプ」 を利用してもよい。

「かつ」や「または」は次のように書きます。 これらは for や while の条件部にも使えます。

    if ((x > 0) && (x < 8)) {       /* 「かつ」 */
        ........
    }

    if ((x < 0) || (x > 2)) {       /* 「または」 */
        ........
    }

※ 「|」はシフトキーを押しながら「¥」キーを打って入力する (ようになっているキーボードが多い)。 字体によって縦棒のまん中に切れ目があったりなかったりする。 また、「かつ」も「または」も同じ文字を二つ打つことに注意。 まちがって「&」「|」をひとつだけ書いた場合、 それらにも意味があるのでコンパイラはエラーメッセージを出さない (かもしれない)。

配列

「配列」というのは,変数の列です。

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

#define UNERASED 0              /* ←英語として正しいかどうか */
#define ERASED 1                /*   責任はもてません :-)     */

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

main() {
    int n, i;

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

    for (n = 2; n <= 100; n++) {        /* ふるいにかける */
        for (i = 2; n * i <= 10000; i++) {
            a[n*i] = ERASED;
        }
    }

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

エラトステネスのふるい (Eratosthenes's sieve)を使って 10000 以下の素数を全て求めるプログラムです。

数学科のみなさんには説明するまでもないでしょうが、 紙と鉛筆でやる場合はこうやります。 1 から 10000 までの自然数を書いておき、 まず 2 の倍数を斜線で消します。 次に 3 の倍数を消します。 次に 4 の倍数ですが、 これはすでに 2 の倍数として消されているので消さなくてよい……。 こうやって 100 の倍数まで消していって、 残ったものが素数でした。

「int a[10000+1];」は 10001 個の int 型変数の配列 a[0], ... , a[10000] を宣言する構文です。 C言語の配列は必ず添字 0 から始まるので、 自然数 n に a[n] を対応させるとしたら a[10000] まで用意するためにはサイズ 10001 の配列が必要です。 「int a[10001];」と書いてもいいのですが、 「a[0] があるから +1 が必要だよ」 ということを強調するためわざわざこう書きました。

そして、「斜線で消す」という代わりに、 a[5] に 0 が代入されていたら 5 は消されていない、 1 が代入されていたら消されている、としました。

「#define」で始まる二行ですが、 0 と 1 のどちらが消されている印でどちらが消されていない印だったかわからなくなるといけないので、 こうやって名前をつけました。 「#define」にはこういう用法もあります。 この UNERASED と ERASED は変数名ではなく定数名なので大文字で書いています。

三つの for 文が何をやっているかは、 簡単にコメントしておいたので読めばわかると思います。 二つ目の for 文はその中にさらに for 文を含んでいます。 なお、そこでは合成数の倍数も消していますので、 このプログラムは最も効率のよいものではありません。

※ このプログラムは素数を全て求めてから出力を行なうので、 出力が始まった時点で計算は終わっている。 実行時間のほとんどが最後の出力の部分に費やされていることに注意。

※ 最後の出力部分を変更すれば 1 から 10000 までの素数だけを出力する、 などとすることもできる。いろいろやってみよう。

※ 何カ所かを変更すれば、1000000 までの数を調べるようにできる。 やってみよう。 単純に定数を書き換えて改造した場合は、 出力が始まる前に少し時間がかかるようだ。

※ 工夫すれば、 合成数については最小の素因数が出力されるようにできる。 やってみよう。

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

ここまでに習ったことを組み合わせると、いろいろなプログラムが書けます。

いつだったかは、 課題として「第一項、第二項が 1 である Fibonacci 数列の最初の十数項について、 その値、およびその項と前の項との比の値を出力するプログラムを書け」 というのを出しました。 みなさんもやってみてはいかがでしょう?

※ Fibonacci 数列とは、a[n+2] = a[n+1] + a[n] で定義される数列。 説明の都合で配列の記号を使ったが、プログラムでは使わなくてもできる。

※ 変数 x と y が int のとき「x / y」とすると小数点以下切り捨てになってしまうが、 「(double) x / y」と書けば x を double 型に変換してから y で割るので、 x / y の値が double として計算されることになる。


岩瀬順一