C言語によるプログラミングの復習

最大公約数を求めるアルゴリズム

以下は，教科書リスト1-1（p. 3）を元にした最大公約数を求めるC言語プログラムである． ソースコードは，gcd_iter.c と main_iter.c に分割されている．

ファイル gcd_iter.c

#include <stdio.h>
#include <stdlib.h>
// Find the greatest common divisor of the two integers, n and m.
int compute_gcd(int n, int m) {
    // Let n be the smaller number.
    if (n > m) {
    int tmp = m;
    m = n;
    n = tmp;
    }
    int gcd = 1;
    int i = 1;
    while (i <= n) {
    if (n % i == 0 && m % i == 0)
        gcd = i;
    i++;
    }
    return gcd;
}

ファイル main_iter.c

#include <stdio.h>
#include <stdlib.h>
int compute_gcd(int, int);

int main(int argc, char *argv[]) {
    // Process arguments.
    if (argc != 3) {
    fprintf(stderr, "Usage: %s <number1> <number2>\n", argv[0]);
    return EXIT_FAILURE;
    }
    int n = atoi(argv[1]);
    int m = atoi(argv[2]);

    // Find the greatest common divisor.
    int gcd = compute_gcd(n, m);
    printf("The GCD of %d and %d is %d.\n", n, m, gcd);

    return EXIT_SUCCESS;
}

C言語特有の記法について簡単に説明する．

int main(int argc, char *argv[]) {

コマンドラインで与えられる引数に対応する変数． argc に引数の数が格納され，argv では引数として与えられた文字列の配列が参照できる．

 fprintf(stderr, "Usage: %s <number1> <number2>\n", argv[0]);

標準エラー出力（stderr）にメッセージを表示している．

return EXIT_FAILURE;

エラーの終了コード．stdlib.h で定義されている．

コンパイルと実行

以下の内容の Makefile を作成する．

ファイル Makefile

gcd_iter: gcd_iter.o main_iter.o

コマンドラインでmakeコマンドを実行すると，Cコンパイラによって実行ファイルが生成される． 実行ファイル gcd_iter に引数を二つ与えて実行すると，結果が表示される．

mac$ make
cc    -c -o gcd_iter.o gcd_iter.c
cc    -c -o main_iter.o main_iter.c
cc   gcd_iter.o main_iter.o   -o gcd_iter
mac$ ./gcd_iter 15 30
The GCD of 15 and 30 is 15.
mac$

基本課題

  1. gcd_iter.c および main_iter.c を入力，コンパイルし，実際に動作を確かめなさい．（レポートでの報告は不要．）
  2. 教科書リスト1-4（p. 7）の「ユークリッドの互除法」に基づいたプログラム gcd_euclid を作成しなさい．関数名は gcd_euclid とすること．レポートには，作成したプログラムのリスト（ソースコード）および実行結果を示すこと．ソースコードは，全体でなく，主要な部分（関数）のみを引用すれば良い．
  3. 適当な入力を例にとり，gcd_iter および gcd_euclid がどのように動作するのかを具体的に説明しなさい．

ヒント

gcd_euclid を作成する場合は，gcd_euclid.c に加えて，対応する main 関数を含む main_euclid.cも作成し Makefile に以下の行を追加する．

gcd_iter: gcd_iter.o main_iter.o

gcd_euclid: gcd_euclid.o main_euclid.o  # 追加

さらに，

make gcd_euclid

を実行することでコンパイルできる．

発展課題

  1. gcd_iter および gcd_euclid について，それぞれの計算量（時間計算量，領域計算量）（教科書1.3.2節（p. 9））を議論しなさい．
  2. gcd_euclid を，再帰的アルゴリズム（教科書p. 14）に基づいて書き換えた gcd_recursive.c を作成しなさい．関数名は gcd_recursive とする．また，適当な入力を例にとり，プログラムがどのように動作するのか上と同様具体的に説明しなさい．

提出締切

2022年10月10日（月）13:30