【C言語】最大公約数を再帰関数で求める方法

2023-09-132024-07-22

C言語でプログラミングを学び始めたばかりの方へ、この記事では「最大公約数」を求める方法をわかりやすく解説します。

特に、再帰関数を使ったユークリッドの互除法というアルゴリズムを中心に、具体的なコード例やその応用方法について詳しく説明します。

この記事を読むことで、再帰関数の基本的な使い方や、最大公約数を利用した実用的なプログラムの作り方が理解できるようになります。

目次から探す

最大公約数を求める再帰関数の実装

ユークリッドの互除法の再帰的実装

アルゴリズムの説明

最大公約数(GCD: Greatest Common Divisor)を求めるための最も効率的な方法の一つが、ユークリッドの互除法です。

このアルゴリズムは、2つの整数の最大公約数を求めるために、以下の手順を繰り返します。

2つの整数 (a) と (b) を用意します。
(a) を (b) で割った余りを求めます。
余りが0であれば、(b) が最大公約数です。
余りが0でなければ、(a) を (b) に、(b) を余りに置き換えて手順2に戻ります。

この手順を再帰的に実装することで、非常にシンプルかつ効率的なコードを書くことができます。

擬似コードの紹介

以下に、ユークリッドの互除法を再帰的に実装した擬似コードを示します。

function gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

この擬似コードでは、関数 gcd が2つの引数 (a) と (b) を受け取り、(b) が0であれば (a) を返し、そうでなければ再帰的に gcd(b, a % b) を呼び出します。

C言語での具体的な実装

コードの全体像

以下に、C言語でユークリッドの互除法を再帰的に実装したコードを示します。

#include <stdio.h>
// 最大公約数を求める再帰関数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}
int main() {
    int num1, num2;
    // ユーザーから2つの整数を入力
    printf("2つの整数を入力してください: ");
    scanf("%d %d", &num1, &num2);
    // 最大公約数を計算
    int result = gcd(num1, num2);
    // 結果を表示
    printf("%d と %d の最大公約数は %d です。\n", num1, num2, result);
    return 0;
}

各部分の詳細な解説

ヘッダファイルのインクルード

#include <stdio.h>

標準入出力を使用するために stdio.h をインクルードしています。

最大公約数を求める再帰関数

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	} else {
		return gcd(b, a % b);
	}
}

この関数 gcd は2つの整数 (a) と (b) を引数に取り、再帰的に最大公約数を計算します。

b が0であれば (a) を返し、そうでなければ gcd(b, a % b) を再帰的に呼び出します。

メイン関数

int main() { 
	int num1, num2; // ユーザーから2つの整数を入力 
	printf("2つの整数を入力してください: ");
	scanf("%d %d", &num1, &num2); 
	// 最大公約数を計算
	int result = gcd(num1, num2); 
	// 結果を表示
	printf("%d と %d の最大公約数は %d です。\n", num1, num2, result); 
	return 0; 
}

メイン関数では、ユーザーから2つの整数を入力し、それらの最大公約数を gcd 関数を使って計算します。

計算結果は result に格納され、最終的に結果を表示します。

このように、ユークリッドの互除法を再帰的に実装することで、シンプルかつ効率的に最大公約数を求めることができます。

再帰関数の理解を深めるためにも、ぜひこのコードを実際に動かしてみてください。

応用と発展

最大公約数を利用した応用例

最大公約数(GCD: Greatest Common Divisor)は、単に数学的な興味だけでなく、実際のプログラミングやアルゴリズムの設計においても非常に有用です。

ここでは、最大公約数を利用した具体的な応用例をいくつか紹介します。

分数の約分

分数の約分は、最大公約数を利用する典型的な例です。

分子と分母の最大公約数を求め、その値で分子と分母を割ることで、分数を最も簡単な形にすることができます。

#include <stdio.h>
// 最大公約数を求める再帰関数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
// 分数を約分する関数
void reduceFraction(int *numerator, int *denominator) {
    int gcdValue = gcd(*numerator, *denominator);
    *numerator /= gcdValue;
    *denominator /= gcdValue;
}
int main() {
    int numerator = 42;
    int denominator = 56;
    printf("約分前: %d/%d\n", numerator, denominator);
    reduceFraction(&numerator, &denominator);
    printf("約分後: %d/%d\n", numerator, denominator);
    return 0;
}

このプログラムを実行すると、分数 42/56 が 3/4 に約分されることが確認できます。

数列の問題

最大公約数は、数列の問題を解く際にも役立ちます。

例えば、数列の全ての要素の最大公約数を求めることで、その数列がどのような共通の因数を持つかを知ることができます。

#include <stdio.h>
// 最大公約数を求める再帰関数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
// 数列の最大公約数を求める関数
int gcdOfArray(int arr[], int n) {
    int result = arr[0];
    for (int i = 1; i < n; i++) {
        result = gcd(result, arr[i]);
    }
    return result;
}
int main() {
    int arr[] = {56, 98, 42, 84};
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = gcdOfArray(arr, n);
    printf("数列の最大公約数: %d\n", result);
    return 0;
}

このプログラムを実行すると、数列 {56, 98, 42, 84} の最大公約数が 14 であることが確認できます。

他のアルゴリズムとの比較

最大公約数を求める方法は、再帰的なユークリッドの互除法だけではありません。

ここでは、他のアルゴリズムとの比較を行います。

反復法との比較

再帰的なユークリッドの互除法と同様に、反復法を用いて最大公約数を求めることもできます。

反復法は、再帰を使わずにループを用いて同じ計算を行います。

#include <stdio.h>
// 最大公約数を求める反復法
int gcdIterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
int main() {
    int a = 56;
    int b = 98;
    int result = gcdIterative(a, b);
    printf("反復法による最大公約数: %d\n", result);
    return 0;
}

このプログラムを実行すると、再帰的な方法と同じ結果が得られます。

反復法は、再帰の深さに制限がある場合や、再帰呼び出しのオーバーヘッドを避けたい場合に有用です。

他の再帰的アルゴリズム

ユークリッドの互除法以外にも、再帰的に最大公約数を求めるアルゴリズムがあります。

例えば、Steinのアルゴリズム(ビットシフトを用いた方法)もその一つです。

#include <stdio.h>
// Steinのアルゴリズムによる最大公約数
int gcdStein(int a, int b) {
    if (a == b) {
        return a;
    }
    if (a == 0) {
        return b;
    }
    if (b == 0) {
        return a;
    }
    if ((a & 1) == 0) { // aが偶数
        if ((b & 1) == 1) { // bが奇数
            return gcdStein(a >> 1, b);
        } else { // aもbも偶数
            return gcdStein(a >> 1, b >> 1) << 1;
        }
    }
    if ((b & 1) == 0) { // bが偶数
        return gcdStein(a, b >> 1);
    }
    if (a > b) {
        return gcdStein((a - b) >> 1, b);
    }
    return gcdStein((b - a) >> 1, a);
}
int main() {
    int a = 56;
    int b = 98;
    int result = gcdStein(a, b);
    printf("Steinのアルゴリズムによる最大公約数: %d\n", result);
    return 0;
}

このプログラムを実行すると、Steinのアルゴリズムでも同じ結果が得られます。

Steinのアルゴリズムは、ビット演算を多用するため、特定の状況では効率的に動作することがあります。

以上のように、最大公約数を求める方法には様々なアプローチがあり、それぞれの方法には利点と欠点があります。

具体的な用途や制約に応じて、最適な方法を選択することが重要です。