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

プログラム作成の練習

前のページ

最大公約数の計算量を求める

以下のプログラムは互除法の剰余計算の回数を表示するものです。 ただし、回数を数える部分が抜けているので、そのままコンパイル実行すると、 剰余計算の回数：0 と表示されてしまいます。剰余計算の回数を正しく表示するように、 プログラムを修正し、コンパイル、実行してみて下さい。

ヒント１：printf(",理論値%.0f\n", ceil(log(n) / log((1 + sqrt(5)) / 2))); と書いてある行は理論的上限を表示しているので関係ありません。

ヒント２：どこかに「cnt++;」と書きます。

ヒント３：１カ所ではありません。

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

int gcd(int x, int y) {
    int r;
    int cnt = 0;
    int n;

    n = y;
    r = x % y;
    while (r > 0) {
	printf("x = %d, y = %d, r = %d\n", x, y, r);
	x = y;
	y = r;
	r = x % y;
    }
    printf("剰余計算の回数:%d", cnt);
    printf(",理論値%.0f\n", ceil(log(n) / log((1 + sqrt(5)) / 2)));
    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;
}
  

ダウンロード： gcd-ren1.c

フィボナッチ数列を表示するプログラム

次のプログラムはフィボナッチ数列を第n項まで表示するものです。ただし、for ループの中が 書かれていません。for ループの中にフィボナッチ数列を計算する部分を書いてください。

ヒント：c という変数が宣言されています。

上級向け：出来た人は、if 文をなくして、for ループだけでもっとスマートに書けないか、 考えてみましょう。

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

void fib(int n) {
    int a = 1;
    int b = 1;
    int c;
    int i;

    printf("%d ", a);
    if (n == 1) {
	return;
    }
    printf("%d ", b);
    for (i = 3; i <= n; i++) {
	/* このあたりにに、フィボナッチ数列の次の値を計算する
	   処理を書きます */
	printf("%d ",    );	/* ここで計算した値を表示します */


    }
    printf("\n");
}

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

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

ダウンロード： fib-ren1.c