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

ファイル gcd_euclid.c

#include <stdio.h>
#include <stdlib.h>

// Find the greatest common divisor of the two integers, n and m.
int gcd_euclid(int n, int m) {

    // 関数を完成させよ

    return n;
}

ファイル main_euclid.c

#include <stdio.h>
#include <stdlib.h>

// Find the greatest common divisor of the two integers, n and m.
int gcd_euclid(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]);

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

  return EXIT_SUCCESS;
}

ファイル gcd_recursive.c

#include <stdio.h>
#include <stdlib.h>

// Find the greatest common divisor of the two integers, n and m.
int gcd_recursive(int n, int m) {

    // 関数を完成させよ

    return n;
}

ファイル main_recursive.c

#include <stdio.h>
#include <stdlib.h>

// Find the greatest common divisor of the two integers, n and m.
int gcd_recursive
(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]);

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

  return EXIT_SUCCESS;
}

ファイル Makefile

all: gcd_iter gcd_euclid gcd_recursive

gcd_iter: gcd_iter.o main_iter.o

gcd_euclid: gcd_euclid.o main_euclid.o

gcd_recursive: gcd_recursive.o main_recursive.o

コードの解説

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

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

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

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

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

return EXIT_FAILURE;

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

コンパイルと実行

コマンドラインでmakeコマンドを実行すると，Makefileの内容に従って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 完成させなさい．レポートには，作成したプログラムの主要部分および実行結果を示すこと．（ソースコードは全体でなく主要な部分のみを引用すれば良い．）
  3. 適当な入力を例にとり，gcd_iter および gcd_euclid がどのように動作するのかを具体的に説明しなさい．

発展課題

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

提出物について

自動採点の注意点

  • レポートの自動採点を行うため，以下の指示に従ってプログラムを作成，提出すること．
  • 関数名，引数，戻り値はサンプルから変更しないこと．
  • プログラムの出力もサンプルから変更しないこと．

提出ファイル一覧

  • report1.pdf （レポート）
  • Makefile
  • gcd_iter.c
  • main_iter.c
  • gcd_euclid.c
  • main_euclid.c
  • gcd_recursive.c （発展課題のみ）
  • main_recursive.c （発展課題のみ）

提出ファイルの構成

  • ディレクトリ class1 を作成して，その中に上記ファイルを配置すること．
  • class1 を ZIP で圧縮した class1.zip ファイルを manaba に提出すること．
（class1.zip）の構造）
class1/
  +-report1.pdf
  +-Makefile
  +-gcd_iter.c
  +-main_iter.c
  +-...

提出締切

2024年10月16日（水）13:30