2007年度後期 情報数理概説 参考プログラム

最大公約数とユークリッドの互除法

前のページ

シラミつぶし版

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

int gcd(int a, int b) {
    int i;
    int n, ans;

    if (a < b) {
	n = a;
    } else {
	n = b;
    }
    for (i = 1; i <= n; i++) {
	if (a % i == 0 && b % i == 0) {
	    ans = i;
	}
    }
    return ans;
}

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

    if (argc <= 2) {
	printf("引数が足りません\n");
	return 1;
    };
    a = strtol(argv[1], NULL, 10);
    b = strtol(argv[2], NULL, 10);
    printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b));
    return 0;
}
  

ダウンロード： gcd2-1a.c

再帰版

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

int gcd(int a, int b) {
    printf("gcd(%d, %d)\n", a, b);
    if (b == 0) {
	return a;
    } else {
	return gcd(b, a % b);
    }
}

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

    if (argc <= 2) {
	printf("引数が足りません\n");
	return 1;
    };
    a = strtol(argv[1], NULL, 10);
    b = strtol(argv[2], NULL, 10);
    printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b));
    return 0;
}

ダウンロード： gcd2-1b.c

ループ版

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

int gcd(int x, int y) {
    int r;

    r = x % y;
    while (r > 0) {
	printf("x = %d, y = %d, r = %d\n", x, y, r);
	x = y;
	y = r;
	r = x % y;
    }
    return y;
}

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

    if (argc <= 2) {
	printf("引数が足りません\n");
	return 1;
    };
    a = strtol(argv[1], NULL, 10);
    b = strtol(argv[2], NULL, 10);
    printf("gcd(%d, %d) = %d\n", a, b, gcd(a, b));
    return 0;
}

ダウンロード： gcd2-1c.c