計算機基礎B - 14. 関数

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

関数

大きなプログラムは機能的にまとまったいくつかの「部品」に分割すると作りやすくなります。 C ではこのような部品のことを関数 (function) といいます。

これまでにも sqrt や fabs といった数学関数を利用してきましたが、関数は自分でも作成することができます。

簡単な例として、2つの整数を受け取り、和の値を返す関数 add を作ってみましょう。 以下のプログラムは関数 add の定義と、add を利用するメインプログラムの2つの部分から成っています。

/* work1401 */
#include <stdio.h>

/* 引数の和を返す関数 */
int add(int p, int q)
{
    return p + q;
}

/* メインプログラム */
int main(void)
{
    int a, b;

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

    printf("%d + %d = %d\n", a, b, add(a, b));

    return 0;
}

関数の定義

関数 add の構造を詳しくみてみましょう。

■ int add(int p, int q)

関数頭部 (function header) は次のような形式をしています。

関数の型 関数名(引数1の型 a1, 引数2の型 a2, ..., 引数nの型 an)

関数 add の定義の冒頭にある int は関数の返す値（戻り値）が int 型であることを示します。

a1, a2, ..., an は関数が受け取る「仮引数」 (dummy argument) と呼ばれます。 仮引数には型もいっしょに指定します。 仮引数が複数個あるときは型と変数名の組をカンマ , で区切って並べます。 関数 add では int 型の2つの変数 p, q が仮引数になります。 メインプログラム中では add(a, b) と呼び出されているので、実行時に p, q は a, b の値を持つことになります。 メインプログラム側の引数のことを「実引数」 (actual argument) といいます。

引数を持たない関数を定義することもできます。 その場合は関数名に続く ( ) の中に void と書くことになっています。

/* int 型の 1 を返す関数 */
int one(void)
{
    return 1;
}

これまでおまじないとして使ってきた main 関数の定義の意味がやっとわかりましたね。

■ return p + q;

関数を終了し、関数の呼び出し元（この場合はメインプログラム）に制御を戻します。 関数の戻り値は return 文の後ろに与えた式の値になります。 return 文に与える式は return; のように省略することもできます。 その場合は不定値が返されることになります。

return 式;                      /* 式を評価した値を返す: retrun 1 + 2; なら 3 が戻り値 */
return;                         /* 不定値を返す */

練習問題 (1) — 2数の最大値

2つの整数を受け取り、大きい方の値を返す関数 max2 を作れ。

/* work1402 */
#include <stdio.h>

/* 大きい方の値を返す関数 */
int max2(int p, int q)
{
    /* 「式1 ? 式2 : 式3」は式1が非 0 なら式2、0 なら式3を評価する */
    return (p > q) ? p : q;

    /* if 文を使うと次のようになる */
    /*
    if (p > q)
        return p;
    else
        return q;
    */
}

/* メインプログラム */
int main(void)
{
    int nx, ny;

    printf("Input two integers: ");
    scanf("%d %d", &nx, &ny);

    printf("max2 = %d\n", max2(nx, ny));

    return 0;
}

練習問題 (2) — 3数の最大値

3つの整数を受け取り、最大値を返す関数 max3 を作成せよ。

/* work1403 */
#include <stdio.h>

/* 3つの整数の最大値を返す関数 */
int max3(int p, int q, int r)
{
    int tmp;

    tmp = p;
    if (tmp < q) tmp = q
    if (tmp < r) tmp = r

    return tmp;
}

/* メインプログラム */
int main(void)
{
    int nx, ny, nz;

    printf("Input 3 integers: ");
    scanf("%d %d %d", &nx, &ny, &nz);

    printf("max3 = %d\n", max3(nx, ny, nz));

    return 0;
}

階乗の関数

0 以上の整数 n を受け取り、階乗 n! の値を返す関数 fact を考えてみましょう。 int 型では値の範囲が狭いので、関数の戻り値は double 型とします。

/* work1404 */
#include <stdio.h>

/* 階乗 n! を返す関数 */
double fact(int n)
{
    int i;                      /* ローカル変数 */
    double tmp = 1.0;

    for (i = 1; i <= n; i++)
        tmp *= i;

    return tmp;
}

/* メインプログラム */
int main(void)
{
    int n;

    for (n = 0; n <= 20; n += 2) {
        printf("%3d    %20.12e\n", n, fact(n));
    }

    return 0;
}

仮引数の有効範囲

ある関数の中で宣言された変数は、その関数の中だけで有効です。 他の関数やメインプログラムに同じ名前の変数があっても、まったく別のものとして扱われます。

この例では n という変数がメインプログラムと関数 fact の両方に現れていますが、関数の仮引数は関数の中だけで有効で、メインプログラムの n とは何の関係もありません。 この性質があるため、関数の設計はメインプログラムや他の関数とまったく独立に行うことができます。

引数の「値渡し」と「参照渡し」

C では仮引数の値を関数の中で変更するような操作を行っても、呼び出し元の実引数の値には何の影響も与えません。 このような引数の受け渡し方法を「値渡し」といいます。 この性質を使うと階乗の関数 fact(n) はローカル変数 i を使わず次のように書くことができます。

double fact(int n)
{
    double tmp = 1.0;

    while (n > 0)               /* n-- によって n の値を変更しても */
        tmp *= n--;             /* 呼び出し元（実引数）には影響しない */

    return tmp;
}

一方、Fortran では仮引数の値を変更すると呼び出し元の実引数の値も変更されます。 このような引数の受け渡し方法を「参照渡し」といいます。

練習問題

Zeller の公式を用いて年月日から曜日を計算する関数を作れ。 y を西暦年、m を月、d を日とすると、

w = y + [y/4] - [y/100] + [y/400] + [2.6*m + 1.6] + d

で定義される w を 7 で割ったあまりが曜日となる（0 から 6 が日曜日から土曜日に対応する）。 ただし、1月と2月は前年の13月と14月とすること （例えば、2001年1月20日の曜日を計算する場合、2000年13月20日として上式に代入する）。 [x] はガウス記号で x を超えない整数を表す。

1月と2月の場合の修正を加えた年月日を y, m, d とすると、整数 w は以下で計算できる。

w = y + y/4 - y/100 + y/400 + (13*m+8)/5 + d

/* work1405 */
#include <stdio.h>

/* Zeller の公式で年月日 y, m, d から曜日 w を計算する関数 */
int zeller(int y, int m, int d)
{
    if (m == 1 || m == 2) {
        y -= 1;                 /* 仮引数を変更しても実引数には影響しない */
        m += 12;
    }
    return (y + y/4 - y/100 + y/400 + (13*m+8)/5 + d) % 7;
}

/* メインプログラム */
int main(void)
{
    int y, m, d;

    printf("Input YYYY MM DD: ");
    scanf("%d %d %d", &y, &m, &d);

    printf("%d\n", zeller(y, m, d));

    return 0;
}

値を返さない関数

メッセージを画面に表示するだけといった、「値を返さない関数」を定義することもできます。 このような関数では戻り値の型を void とし、return 文は省略することができます。 （省略しない場合は return; とします。）

例として、自分自身が実行された回数を画面に出力する関数 count を作ってみましょう。

/* work1406 */
#include <stdio.h>

/* 呼び出された回数を表示する関数 */
void count(void)                /* 戻り値なし、引数なし */
{
    static int n = 0;           /* n は静的変数 */
    printf("%d\n", ++n);        /* n++ との違いに注意 */
    return;                     /* return は省略することも可能 */
}

/* メインプログラム */
int main(void)
{
    count();
    count();
    count();

    return 0;
}

このプログラムを実行すると次のようになります。

% ./a.out
1
2
3

記憶域クラス指定子 static

関数の中で宣言された変数や配列の内容は、値を設定する前は不定です。 また、関数の中でいったん値を設定しても、return 文によって関数を終了した時点で再び不定となり、次にまたその関数が呼ばれても前回の値は残っていません。 （残っていることもありますが、それはたまたまです。） これを「自動記憶域期間」といい、このような変数のことを「自動変数」 (automatic variable) といいます。

ただし、関数の中で static を付けて宣言された変数には「静的記憶域期間」が与えられ、関数が終了してもその値を保持することができます。 このような変数のことを「静的変数」 (static variable) といいます。 また、静的変数の初期化は main 関数を実行する前に一度だけ行われます。 したがって、関数 count が何回か呼び出されたからといって、その都度、初期化が行われるわけではありません。

前置増分演算子

printf の引数の ++n は n の値を 1 だけ増やし、その結果を返します。 つまり、n の値が 0 の場合に printf("%d\n", ++n); を実行すると、まず n の値が 1 となり、画面に 1 が表示されます。 後置増分演算子 n++ に似ていますが、 n++ では増加前の値が返されるという違いがあります。

同様に、int 型の変数の値を 1 だけ値を減らす前置減分演算子 --n もあります。

++n    n の値を 1 増やす（式全体を評価すると増加後の値となる）
--n    n の値を 1 減らす（式全体を評価すると減少後の値となる）

配列の受け渡し

配列を関数の引数にすることもできます。 次の関数 maxval は int 型の1次元配列 vec[] の最大値を返します。

/* work1407 */
#include <stdio.h>

/* 配列 vec[size] の最大値を返す関数 */
int maxval(int vec[], int size)
{
    int max, i;

    max = vec[0];
    for (i = 1; i < size; i++) {
        if (max < vec[i])
            max = vec[i];
    }

    return max;
}

/* メインプログラム */
int main(void)
{
    int x[] = { 5, 1, 3, 2, 8 };
    printf("max of x: %d\n", maxval(x, 5));
    return 0;
}

配列の受け渡し方法

関数 maxval の冒頭部分は次のようになっています。

int maxval(int vec[], int size)

int vec[] は「vec は int 型の配列」という意味です。 これだけでは配列の要素数がわからないことに注意しましょう。 配列の要素数は別の引数にします。 このプログラムでは配列の要素数を2番目の引数 int size として渡しています。

関数を呼び出す際は maxval(x, 5) のように配列の名前だけ書いたものを渡します。 メインプログラムでの配列名は x ですが、これが maxval に渡されるとその中では vec という名前で参照されます。 したがって、 関数 maxval の中では vec[0] は x[0]、 vec[1] は x[1]、 …、 vec[4] は x[4] を表すことになります。

練習問題

int 型の1次元配列 vec[] の最小値を返す関数 minval を作れ。

/* work1408 */
#include <stdio.h>

/* 配列 vec[size] の最大値を返す関数 */
int minval(int vec[], int size)
{
    int min, i;

    min = vec[0];
    for (i = 1; i < size; i++) {
        if (min > vec[i])
            min = vec[i];
    }

    return min;
}

/* メインプログラム */
int main(void)
{
    int x[] = { 5, 1, 3, 2, 8 };
    printf("min of x: %d\n", minval(x, 5));
    return 0;
}

配列の値の変更

スカラー変数（配列ではない変数のこと）の場合、C では引数が「値渡し」されるため、仮引数の値を関数の中で変更しても、呼び出し元の実引数の値には何の影響も与えません。 ところが、引数が配列の場合はこのルールが（一見）成り立たず、仮引数として受け取った配列を関数の中で変更すると、呼び出し元の配列の内容も同じように変更されます。

次の例では関数 change_sign() の中で配列 vec[] の各要素の符号を変化させています。 その結果、呼び出し元の実引数である配列 x[] の内容も変化することを確かめましょう。

/* work1409 */
#include <stdio.h>

/* 配列の符号を変える関数 */
void change_sign(int vec[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        vec[i] *= -1;
}

/* メインプログラム */
int main(void)
{
    int x[] = { 5, 1, 3, 2, 8 };
    int i;

    change_sign(x, 5);

    for (i = 0; i < 5; i++)
        printf("%d\n", x[i]);

    return 0;
}

C では引数は値渡しであり、仮引数を変更しても実引数には影響を与えないことと矛盾するように感じるかもしれませんが、これは C の配列が「ポインタ」というもので実現されているためです。 この講義ではポインタの説明を行わないので、

• スカラー変数の場合、仮引数の変数を変更しても呼び出し元の実引数には影響しない
• ただし、配列は例外で、仮引数の配列を変更すると呼び出し元の実引数の配列も変更される

と覚えましょう。

C の配列とポインタについて詳しく知りたい人は参考書で調べるとよいでしょう。 なお、Fortran ではすべての引数が参照渡しされるため、仮引数を変更すると呼び出し元の実引数も変更されます。

仮引数に対する const 型修飾子

仮引数の宣言に const 型修飾子を付けると、関数の中で受け取った配列の内容を変更できなくなります。 うっかりミスを防止するため、変更する必要のない配列引数には const を付けておくとよいでしょう。

int maxval(const int vec[], int size)
{
    /* 配列 vec[] は変更不可 */
    :
}

練習問題

ベクトル（double 型の1次元配列）の大きさを 1 に正規化する関数 norm() を作れ。

/* work1410 */
#include <stdio.h>
#include <math.h>               /* sqrt */

/* 正規化する関数 */
void norm(double vec[], int size)
{
    int i;
    double tmp = 0.0;

    /* |x|**2 = x1*x1 + x2*x2 + ... + xn*xn */
    for (i = 0; i < size; i++)
        tmp += vec[i] * vec[i];

    /* |x|**2 -> |x| */
    tmp = sqrt(tmp);

    /* ゼロベクトルの場合は何もしない */
    if (tmp == 0.0)
        return;

    /* 正規化 x -> x / |x| */
    for (i = 0; i < size; i++)
        vec[i] /= tmp;
}

/* メインプログラム */
int main(void)
{
    double x[] = { 1.0, 2.0, -2.0 };
    int i;

    norm(x, 3);

    for (i = 0; i < 3; i++)
        printf("%f\n", x[i]);

    return 0;
}

再帰関数

0 以上の整数 n の階乗 n! は次のように定義することができます。

n! = (n-1)! * n     (n = 1, 2, ...)
0! = 1

n! の定義に (n-1)! が含まれていることに注意してください。 このように、あるもの（階乗）を定義するのに自分自身を使って定義する方法を「再帰的定義」といいます。 C では再帰的定義をそのままプログラムにすることができます。

#include <stdio.h>

double fact(int n)
{
    if (n == 0)
        return 1.0;
    else
        return fact(n-1) * n;   /* 再帰呼び出し */
}

関数 fact の定義の中に fact が使われています。 自分自身を呼び出す関数のことを「再帰関数」 (recursive function) といいます。 ただし、再帰関数が常に自分自身を呼び出す訳ではないことに注意しましょう。 上の例では、n = 0 の場合は再帰呼び出しが行われず、戻り値として 1.0 が返されます。 常に再帰呼び出しが行われると無限ループになってしまうため、再帰関数には再帰呼び出しを終了させるための条件が必ず含まれなければいけません。

関数とスタック

関数の仮引数や関数の中で定義される変数はメモリ中の「スタック」という領域に格納されます。 再帰関数の中で再帰呼び出しの回数（深さ）が多くなりすぎると、スタック領域が不足し、「スタックオーバーフロー」というエラーになることがあるので注意しましょう。

練習問題

1 から n までの和を返す再帰関数 sum1(n) を定義せよ。 ただし、n は 1 以上の整数とする。

/* work1411 */
#include <stdio.h>

/* 1 から n までの和を求める再帰関数 */
int sum1(int n)
{
    if (n == 1)
        return 1;
    else
        return sum1(n-1) + n;
}

/* メインプログラム */
int main(void)
{
    int n;

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

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

    return 0;
}

本日の課題

1. メッセージの表示

画面に hello と表示する戻り値のない関数 print_hello(n) を作成せよ。 hello の個数を int 型の引数 n で指定できるようにすること。

/* work1412 */
#inculde <stdio.h>

/* hello を n 回表示する関数 */
void print_hello(int n)
{
    while (n-- > 0)
        printf("hello\n");
}

/* メインプログラム */
int main(void)
{
    print_hello(5);
    return 0;
}

2. 内積の計算

2つの double 型の配列 x[], y[] を受け取り、内積 x.y を返す関数 naiseki(x, y) を作成せよ。

/* work1413 */
#inculde <stdio.h>

/* 内積を返す関数 */
double naiseki(const double x[], const double y[], int size)
{
    int i;
    double tmp = 0.0;

    int (i = 0; i < size; i++)
        tmp += x[i] * y[i];

    return tmp;
}

/* メインプログラム */
int main(void)
{
    double x[] = {  1.0,  2.0, -3.0 };
    double y[] = { -2.0,  3.0,  1.0 };

    printf("naiseki = %f\n", naiseki(x, y, 3));

    return 0;
}

3. チェビシェフ多項式

次数 n のチェビシェフ (Chebyshev) 多項式 Tn(x) は次の3項間漸化式で定義される。

T0(x) = 1
T1(x) = x
Tn(x) = 2 * x * Tn-1(x) - Tn-2(x)   (n>=2)

n と x を与えて Tn(x) の値を返す関数 tc(n, x) を定義せよ。 この関数を利用して

x = -1, -0.95, -0.90, ..., 0.95, 1

における x と Tn(x) の値の組 (xi, yi) を出力するプログラムを作成し、 n=5 の場合についてグラフを Gnuplot で図示せよ。

/* work1414 */
#include <stdio.h>

/*
  n 次のチェビシェフ多項式 Tn(x)
  T0(x) = 1
  T1(x) = x
  Tn(x) = 2 * x * Tn-1(x) - Tn-2(x)   (n>=2)
*/
double tc(int n, double x)
{
    int i;
    double a, b, c;

    /* n = 0, 1 の場合 */
    if (n == 0) return 1.0;
    if (n == 1) return x;

    /* T0, T1 */
    a = 1.0;
    b = x;

    /* Tn */
    for (i = 2; i <= n; i++) {
        c = 2 * x * b - a;
        a = b;
        b = c;
    }
    return c;
}

/*
  メインプログラム
  x = -1, -0.95, -0.90, ..., 0.95, 1 で T5(x) の値を出力する
  %20.12f は浮動小数点数を「全体を 20 桁、小数点以下を 12 桁」で出力するための書式
*/
int main(void)
{
    int i;
    double xi;

    for (i = -20; i <= 20; i++) {
        xi = i / 20.0;
        printf("%20.12f %20.12f\n", xi, tc(5, xi));
    }

    return 0;
}

チャレンジ問題

1. モンテカルロ法

家族が男子を得るまで子供を作るとする。 100家族についてシミュレーションして、1家族あたり平均何人の女子を持つことになるか求めよ。 ただし、男女の出生率は同じとする。 乱数を利用して数値実験を行う手法を「モンテカルロ法」という（カジノで有名なモナコ公国の地名「モンテ・カルロ」にちなんで名付けられた）。 また、解析解を求めて結果を比較せよ。

ヒント： 乱数の発生には関数 rand() を利用する。 あらかじめヘッダファイル stdlib.h をインクルードすること。 rand() は 0 から RAND_MAX までの整数をランダムに返す関数である。 したがって半開区間 [0, 1) での乱数を作るには次のようにすればよい。

rand() / (1.0 + RAND_MAX)

■ 重要な注意

関数 rand() の作る乱数はあくまでも「疑似乱数」で、あまり品質のよくないものです。 様々な疑似乱数の原理や特徴（利点と欠点）について、和田維作氏の「良い乱数・悪い乱数」に詳しい説明があります。 品質のよい乱数が必要な場合はメルセンヌツイスターなどを使いましょう。

/* work1415 */
#include <stdio.h>
#include <stdlib.h>             /* rand() */

/* モンテカルロ法 */
int main(void)
{
    const int nmax = 100;
    int n, girl = 0;
    double p;

    for (n = 0; n < nmax; n++) {
        while (1) {
            /* [0, 1) の乱数を p にセットする */
            p = rand() / (1.0 + RAND_MAX);
            /* p が [0, 0.5) なら男子、[0.5, 1) なら女子とする */
            if (p < 0.5)
                break;          /* 男子が生まれたので次の家族 (次の n) へ */
            /* 女子の数をインクリメント */
            girl++;
        }
    }

    /* 女子の期待値 */
    printf("expected: %f\n", ((double) girl) / nmax);

    return 0;
}

2. ソート（単純挿入法）

正整数 n と長さ n の double 型配列 x[] を引数とし、 x(1), x(2), ..., x(n) を小さい順（昇順という）に並び替える関数 isort(n, x) を定義せよ。

void isort(int n, double x[])

並び替え (sort) には次のような方法を用いること。

1. まず1番目の要素に注目し、0番目との大小関係が正しくなるようにする。
2. 次に2番目の要素に注目し、最初の2つと見比べて正しい位置に挿入する。
3. 以下、同様の操作を繰り返し、最後の要素を適当な場所に挿入した時点で並び替えが完了する。

このようなソート方法を「単純挿入法」という。

単純ソートではソートする配列のサイズが大きくなると並べ替えに要する時間が著しく増大する。 計算時間の増加を抑えた高速なソート方法には

• ヒープソート (heap sort) 【Wikipedia の説明をみる】
• クイックソート (quick sort) 【Wikipedia の説明をみる】

などが知られている。

/* work1416 */
#include <stdio.h>
#include <stdlib.h>

/* 単純ソート */
void isort(int n, double x[])
{
    int i, j;
    double tmp;

    /* j 番目の要素に着目する */
    for (j = 1; j < n; j++) {
        tmp = x[j];
        /* x[j] より小さい要素がみつかるまで、要素を1つずつ後ろにずらす */
        for (i = j-1; i >= 0; i--) {
            if (x[i] < tmp) break;
            x[i+1] = x[i];
        }
        /* 空いた場所に x[j] を入れ終了。次の j に移る */
        x[i+1] = tmp;
    }

    return;
}

/*
  メインプログラム
  組み込み関数 qsort() と結果を比較する
*/
#define NMAX 4096

/* qsort() 用の比較関数 */
int cmp_double(const void *a, const void *b)
{
    double *x = (double *) a;
    double *y = (double *) b;
    return (*x > *y) - (*x < *y);
}

/* メイン関数 */
int main(void)
{
    double x[NMAX], y[NMAX];
    int i, c = 0;

    /* 配列 x[], y[] に同じ乱数列をセット */
    for (i = 0; i < NMAX; i++)
        x[i] = y[i] = rand() / (1.0 + RAND_MAX);

    /* ソート */
    isort(NMAX, x);
    qsort(y, NMAX, sizeof(double), cmp_double);

    /* 結果の表示と比較 */
    for (i = 0; i < NMAX; i++) {
        printf("%20.15f %20.15f\n", x[i], y[i]);
        if (x[i] != y[i]) c++;
    }
    printf("%d error(s) found.\n", c);

    return 0;
}