2000 年度「計算機基礎論３Ｂ」 2000-11-17

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

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

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

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

    for (文１; 式２; 文３) {
        ...
    }

• 文１（初期設定）を実行。
• 式２（継続条件）が成り立つかどうかチェックする。
  • 式２が真ならば中カッコの中を実行。 文３（再初期化）を実行し、式２のチェックにもどる。
  • 式２が偽ならば，中カッコはとばして次へ進む。

もう一つの構文

    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);
    }
}
===============================================================================

• ある項が偶数のときはその項を 2 で割ったものを次の項とする
• ある項が奇数のときはその項の 3 倍に 1 を加えたものを次の項とする

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

== 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! + ... として計算しています。 Ｃ言語には階乗を表わす演算子はないので自力で計算しなければなりません。 ここでは n! を計算した結果を捨てないで次の (n+1)! の計算に使っています。

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

== 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) になります。 それとの差を並べて出力してみるのも面白いかも知れません。

「かつ」や「または」は次のように書きます。 これらは 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] を宣言する構文です。 Ｃ言語の配列は必ず添字 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 である Fibonacci 数列の最初の十数項について、 その値、およびその項と前の項との比の値を出力するプログラムを書け」 というのを出しました。 みなさんもやってみてはいかがでしょう？