計算機基礎B - 12. 繰り返し

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

for 文による繰り返し

次のプログラムは 1 から 10 までの和を求めて結果を表示します。

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

int main(void)
{
    int i, sum = 0;

    for (i = 1; i <= 10; i++)   /* i++ は i = i + 1 と同じ */
        sum += i;               /* sum = sum + i と同じ */

    printf("1 + 2 + ... + 10 = %d\n", sum);

    return 0;
}

変数の初期化

C では変数の宣言時に初期値を指定することができます。 これを「初期化」といい、右辺の定数などの式のことを「初期化子」といいます。 変数を宣言する際は、初期化する習慣をつけるとよいでしょう。

for 文

for 文は次のような構造をしています。

for (A; B; C)
    ループ本体;

A, B, C の意味は次のようになっています。

• A は繰り返しが開始される前に一度だけ実行されます。 上の例では i = 1 が A に相当し、変数 i に 1 をセットします。
• B は繰り返しを続けるかどうかの判定式です。 この式を評価した値が非 0 であればループ本体が実行されます。 上の例では i <= 10 が B に相当し、i が 10 以下であれば非 0 を返します。
• C はループ本体の最後に毎回評価されます。 上の例では i++ が C に相当し、変数 i の値が 1 だけ増やされます（i++ は i = i + 1 と同じ意味です）。

上の例では i の値は 1 から 10 まで 1 ずつ増加することになります。

ループ本体には単文のほか、複数の文を { } でくくった複合文（ブロック）を使うこともできます。

後置増分演算子と後置減分演算子

ある変数の値を 1 だけ増やす（減らす）場合、 C では後置増分演算子 ++ （後置減分演算子 --）が用いられます。

• i++ : i の値を 1 だけ増やす。（式全体を評価すると増加前の値となる）
• i-- : i の値を 1 だけ減らす。（式全体を評価すると減少前の値となる）

次の例を考えてみましょう。

int i = 0, j;
j = i++;
printf("i = %d, j = %d\n", i, j);

j = i++ が評価されると i++ は 0 となり、j には 0 が代入されます。 そのあとで i がインクリメントされ 1 になります。 つまり、j = i++; は次のような計算と等価になります。

j = i;                          /* i の値が変わる前に代入文が評価される */
i = i + 1;                      /* その後で i の値が 1 増やされる */

結局、printf で画面に表示されるのは「i = 1, j = 0」になります。

複合代入分

sum += i は sum = sum + i と同じ意味になります。 このような演算子のことを「複合代入演算子」といいます。 C には以下の演算子に対して、対応する複合代入演算子が用意されています。

+  -  *  /  %  <<  >>  &  ^  |

当面は加減乗除と剰余 + - * / % だけ覚えておけば十分です。

x += a;        /* x = x + a */
x -= a;        /* x = x - a */
x *= a;        /* x = x * a */
x /= a;        /* x = x / a */
x %= a;        /* x = x % a */

練習問題

キーボードから整数 n の値を読み込み、1 から n までの奇数の和と奇数の積をそれぞれ求めるプログラムを作成せよ。

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

int main(void)
{
    int i, n, sum = 0;
    double prod = 1.0;

    printf("Input a positive integer N: ");
    scanf("%d", &n);

    for (i = 1; i <= n; i += 2) {
        sum += i;               /* sum = sum + i */
        prod *= i;              /* prod = prod * i */
    }
    /* for ループから抜けた時点で i は n より大きい最小の奇数になっている */

    printf("1 + 3 + ... + %d = %d\n", i-2, sum);
    printf("1 * 3 * ... * %d = %f\n", i-2, prod); /* prod は double 型なので %f を使う */

    return 0;
}

減少ループ

キーボードから整数 n を入力し、n の2重階乗 n!! を求めるプログラムを考えてみましょう。 2重階乗 n!! は次のように定義されます。

 n!! = 1 * 3 * 5 * … * n    (n が奇数の場合)
       2 * 4 * 6 * … * n    (n が偶数の場合)
 0!! = 1
-1!! = 1

定義をみると n の偶奇で場合分けする必要があるように思えますが、for 文をうまく使うと不要です。

/*
  work1203.c
  2重階乗 n!! の計算
*/
#include <stdio.h>

int main(void)
{
    int i, n;
    double tmp = 1.0;

    printf("Input a positive integer N: ");
    scanf("%d", &n);

    for (i = n; i > 0; i -= 2)  /* A: i=n, B: i>0, C: i=i-2 */
        tmp *= i;               /* tmp = tmp * i */

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

    return 0;
}

プログラムの流れ

i の値の変化

変数 i の値がどのように変化するか考えてみましょう。 for 文の C に相当する部分が i -= 2 なので i の値は 2 ずつ減少します。 繰り返しの条件は i > 0 です。 したがって、

• n = 5 （奇数）の場合 : i の値は 5, 3, 1 と変化します。
• n = 6 （偶数）の場合 : i の値は 6, 4, 2 と変化します。

となります。 ループの中で i の値は 0 にならないことに注意しましょう。

tmp の値の変化

n = 5 の場合を考えてみましょう。 double 型の変数 tmp には初期値 1.0 が与えられています。 for 文の処理が開始されると変数 i は 5 にセットされるので、 ループ本体の

tmp *= i

によって tmp の値は tmp * i （つまり 1.0 * 5）に更新されます。

次に i には 3 がセットされます。 tmp *= i によって tmp の値は tmp * i （つまり 5.0 * 3）に更新されます。

この処理は i が 1 になるまで繰り返されます。 結果として tmp には 5 * 3 * 1 の値が入ります。

do 文による繰り返し

Newton 法で正数 a の平方根を求めるプログラムを考えてみましょう。

Newton 法

方程式 f(x) = 0 の根は次のように求めることができます。 x0 を根の第1近似とします。 曲線 y = f(x) 上の点 (x0, f(x0)) における接線が x 軸と交わる点を x1 とすると、 x1 は x0 よりも f(x) = 0 の根に近い値となります。 第 n 近似 xn が求まったとすると次の近似 xn+1 は次の式で求めることができます。

xn+1 = xn - f(xn) / f'(xn)

これを繰り返すことによって方程式の根を得ることができます。 これを Newton 法といいます。 【Wikipedia の説明をみる】

解の収束は xn と xn+1 の差が十分小さくなったかどうかで判定します。

平方根の計算

f(x) = x*x - a とすると f(x) = 0 の解が a の平方根になります。 Newton 法の一般論より次の数列が √a に収束します。

xn+1 = (xn + a / xn) / 2

これをプログラムにすると下のようになります。

/*
  work1204.c
  Newton method
*/
#include <stdio.h>
#include <math.h>               /* fabs() */

int main(void)
{
    double a, xold, xnew, dx;
    const double eps = 1.0e-5;  /* 定数の宣言 */

    printf("Input a posive real: ");
    scanf("%lf", &a);

    /* 第 0 近似を a とする */
    xold = a;

    /* 漸化式の計算 */
    do {
        xnew = (xold + a / xold) / 2;
        dx = xnew - xold;       /* 相対誤差 */
        xold = xnew;            /* 次の繰り返しの準備 */
    } while (fabs(dx) > eps);   /* 繰り返すかどうかの判定 */

    /* 結果表示 */
    printf("%15.10f\n", xnew);

    return 0;
}

do 文

do 文は次のような構造をしています。

do {
    ループ本体
} while (条件式);

条件式が非 0 であれば「ループ本体」の部分が繰り返されます。 while は「〜の間」というような意味です。

最初の条件判定はループ本体が1回目に実行されたあとで行われます。 したがって、条件式の値に関わらず、ループ本体が最低1回は実行されることに注意しましょう。

定数の宣言

定数を宣言するには、型宣言文に const 修飾子をつけます。

const double eps = 1.0e-5;

とすれば double 型の変数 eps は「定数」となり、値の変更が禁止されます。

絶対値関数 abs(), fabs()

絶対値を返す関数には int 型の abs() と、double 型の fabs() があります。 型によって名前が異なるので注意しましょう。

• abs(n) は int 型の引数 n を取り、その絶対値を int 型で返します。
• fabs(x) は double 型の引数 x を取り、その絶対値を double 型で返します。

fabs() などの関数（数学関数）を使う場合はプログラムの冒頭で math.h をインクルードする必要があります。 stdio.h や math.h などのファイルは「ヘッダファイル」と呼ばれます。 ヘッダファイルには関数や関数の引数に関する情報や、いろいろな定数などが書かれています。 UNIX では /usr/include というディレクトリに各種ヘッダファイルが集められています。

関数の引数や戻り値に関する情報は、次のように表されることがあります。 関数名の前の型名が戻り値の型を示し、括弧の中の型名が引数の個数と型を表します。

int abs(int);                   /* int 型の絶対値 */
double fabs(double);            /* double 型の絶対値 */
double atan2(double, double);   /* tan() の逆関数（2変数用） */

練習問題

キーボードから読み込んだ整数値を、逆順に表示するプログラムを作成せよ。 例えば、1357 と入力すると 7531 と表示する。

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

int main(void)
{
    int n;

    do {
        printf("Input a positive integer: ");
        scanf("%d", &n);
    } while (n <= 0);           /* 0 以下の値が入力されたら再度入力させる */

    do {
        printf("%d", n % 10);   /* 10 で割った余り（1の位の値）を表示 */
        n /= 10;                /* 1桁右にシフトする: 1357 -> 135 -> 13 -> 1 */
    } while (n > 0);
    printf("\n");

    return 0;
}

while 文による繰り返し

Newton 法のプログラムを while 文を使って書き直してみましょう。

/*
  work1206.c
  Newton method
*/
#include <stdio.h>
#include <math.h>               /* fabs() */

int main(void)
{
    double a, xold, xnew, dx;
    const double eps = 1.0e-5;  /* 定数の宣言 */

    printf("Input a posive real: ");
    scanf("%lf", &a);

    /* 第 0 近似を a とする */
    xold = a;

    /* 漸化式の計算 */
    while (1) {
        xnew = (xold + a / xold) / 2;
        dx = xnew - xold;       /* 相対誤差 */
        if (fabs(dx) < eps)
            break;              /* |dx| < eps なら while ループから脱出 */
        xold = xnew;            /* 次の繰り返しの準備 */
    }

    /* 結果表示 */
    printf("%15.10f\n", xnew);

    return 0;
}

while 文

while 文は次のような構造をしています。

while (条件式) {
    ループ本体
}

条件式が非 0 であればループ本体が繰り返し実行されます。 do 文との違いは「ループ本体が実行される前に条件式がチェックされる」点です。 したがって、while 文ではループ本体が1回も実行されないことがあります。

上のプログラムでは条件式が定数 1 になっています。 こうすると while 文は無限ループになります。

break 文

while 文のループから脱出するにはループの中で break 文を実行します。 break 文は for 文や do 文からの脱出にも使うことができます。

多重ループ

for 文を入れ子にすることで複数の変数を独立に変化させることができます。 例として、かけ算九九の表を作成するプログラムを考えてみましょう。

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

int main(void)
{
    int i, j;

    for (i = 1; i <= 9; i++) {
        for (j = 1; j <= 9; j++) {
            printf("%d * %d = %d\n", i, j, i * j);
        }
    }

    return 0;
}

字下げ

変数 j のループは行頭に空白を入れ、右にずらして書いてあります。 こうすると変数 j の for ループが変数 i の for ループの中に包含されていることが視覚的にはっきりします。 このような記法を「字下げ」（インデント）といいます。

Emacs では TAB キーを押すことによって適切な字下げを行うことができます。

本日の課題

1. 階乗の計算

キーボードから整数 n を入力し、n の階乗 n! を求めるプログラムを作成せよ。 繰り返しには for 文を用い、 0! = 1 も正しく計算できるようにすること。

/*
  work1208.c
  n! の計算
*/
#include <stdio.h>

int main(void)
{
    int i, n;
    double tmp = 1.0;

    printf("Input a positive integer N: ");
    scanf("%d", &n);

    for (i = n; i > 0; i--)
        tmp *= i;

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

    return 0;
}

2. 立方根の計算

Newton 法で正数 a の立方根を求めるプログラムを作成せよ。 f(x) = x^3 - a とすると f(x) = 0 の解が立方根を与える。 Newton 法の一般論から、漸化式は次のようになる。

xn+1 = xn - (xn**3 - a) / (3 * xn**2)
     = (2 * xn + a / xn**2) / 3

繰り返しには while 文を用いること。

/*
  work1209.c
  a の立方根を計算する
*/

3. 入力の繰り返し

キーボードから整数 n を入力し、n が正ならそれを表示して終了するプログラムを作成せよ。 n が 0 または負の場合は入力を繰り返すようにすること。

/*
  work1210.c
*/
#include <stdio.h>
#include <unistd.h>             /* sleep() */

int main(void)
{
    int n;

    do {
        printf("Input an integer: ");
        scanf("%d", &n);
        if (n <= 0)
            printf("N must be positive. Input again.\n");
    } while (n <= 0);

    printf("Wait for %d seconds", n);

    while (n--) {
        printf(".");
        fflush(stdout);
        sleep(1);               /* 1秒待つ */
    }
    printf("\n");

    return 0;
}

4. 数表の作成

0 から 2 までの x に対する平方根の表を 0.1 きざみで作成せよ。 平方根の計算には組み込み関数 sqrt(x) を用いてよい。

/*
  work1211.c
  数表の作成
*/
#include <stdio.h>
#include <math.h>               /* sqrt() */

int main(void)
{
    int i;
    double x;

    for (i = 0; i <= 20; i++) {
        x = i / 10.0;
        printf("%f %f\n", x, sqrt(x));
    }

    return 0;
}

チャレンジ問題

1. 最大公約数と最小公倍数

キーボードから2つの自然数 a, b を入力し、最大公約数と最小公倍数を求めるプログラムを作成せよ。 最大公約数を求めるには「ユークリッドの互除法」を用いる。 変数 a, b, m, n, k は int 型とする。

• step 1: a, b をそれぞれ変数 m, n に代入する。
• step 2: m を n で割ったあまりを k とする。
• step 3: k が 0 なら n が求める最大公約数である。k が 0 でなければ step 4 へ。
• step 4: m に n の値を代入し、n に k の値を代入して step 2 へ戻る。

/*
  work1212.c
  GCM and LCM
*/
#include <stdio.h>

int main(void)
{
    int a, b;
    int m, n, k, gcm, lcm;

    printf("Input two integers: ");
    scanf("%d %d", &a, &b);

    /* 最大公約数 gcm */
    m = a;
    n = b;
    while (1) {
        k = m % n;
        if (k == 0) {
            gcm = n;
            break;
        }
        m = n;
        n = k;
    }

    /* 最小公倍数 lcm */
    lcm = gcm * (a / gcm) * (b / gcm);

    printf("%d %d\n", gcm, lcm);

    return 0;
}

2. 等比級数

どんな高さから落としても、もとの高さの 0.65 倍の高さまで跳ね返るボールがある。 このボールを h メートルの高さから落としたら、何回目でボールが 1 メートル以下になるか求めよ。 （はじめの高さ h はキーボードから入力する。）

/*
  work1213.c
  等比級数
*/
#include <stdio.h>

int main(void)
{
    double h;
    int n = 0;

    do {
        printf("Input initial height (> 1.0): ");
        scanf("%lf", &h);
    } while (h <= 1.0);

    do {
        h *= 0.65;              /* h = h * 0.65 */
        n++;                    /* n += 1 と書いてもよい */
        printf("%d %f\n", n, h);
    } while (h > 1.0);

    return 0;
}

3. 整数のパズル

3桁の整数で、各桁の数字の3乗和がもとの数と等しくなるようなもの（例えば 153 など）をすべて求めよ。 答えは 153 を含めて4つある。

/*
  work1214.c
  3桁の整数で、各桁の数字の3乗和がもとの数と等しくなるようなもの
*/
#include <stdio.h>

int main(void)
{
    int m, n;                   /* 3桁の整数 (234 など) */
    int i, j, k;                /* 各桁の数字 (234 なら i=2, j=3, k=4 など) */

    for (m = 100; m < 1000; m++) {
        i = m / 100;
        j = (m - i * 100) / 10;
        k = (m - i * 100 - j * 10);
        n = i*i*i + j*j*j + k*k*k;
        if (m == n)
            printf("%d\n", m);
    }

    return 0;
}

4. 二分探索法

区間 [a, b] で定義される単調増加関数 y = f(x) があり、 f(a) < 0, f(b) > 0 であることがわかっているとする。 このとき、次のような方法で f(x) = 0 の数値解を求めることができる。

1. a, b の中点を m とする。
2. a, b の距離が十分近かったら中点 m を解として終了する。 そうでなかったら step 3 へ。
3. f(m) > 0 なら b を m で置き換え、f(m) < 0 なら a を m で置き換える。 このように区間を半分に縮小し、step 1 に戻る。

このような方法を「二分探索法」という。

関数 f(x) = x*x-5 を区間 [0, 5] で考えると単調増加である。 二分探索法で f(x) = 0 の解を求めよ。 解析解は √5 である。

/*
  work1215.c
  二分探索法
*/
#include <stdio.h>
#include <math.h>               /* fabs, sqrt */

int main(void)
{
    double a, b, m, f;
    const double eps = 0.1e-7;

    /* 最初の区間 [0, 5] */
    a = 0.0;
    b = 5.0;

    while (1) {
        /* 中点と関数値 */
        m = (a + b) / 2;
        f = m * m - 5.0;
        /* |b - a| < eps ならループ終了 */
        if (fabs(a - b) < eps)
            break;
        /* 区間を縮小し、次の繰り返しへ */
        if (f >= 0.0) {
            b = m;
        } else {
            a = m;
        }
    }

    /* 結果表示 */
    printf("%15.12f\n", m);
    printf("%15.12f\n", sqrt(5.0));

    return 0;
}