MENU
プログラミングの世界へようこそ
  1. ホーム
  2. C言語
  3. プログラム
  4. 数値処理
  5. 【C言語】最大公約数を再帰関数で求める方法

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

数値処理

この記事では、C言語で最大公約数を再帰関数を用いて求める方法を解説します。

目次から探す

最大公約数の求め方

最大公約数(Greatest Common Divisor, GCD)は、2つ以上の整数の中で共通の約数のうち最大のものを求める方法です。

C言語では、ユークリッドの互除法や再帰関数を使って最大公約数を求めることができます。

ユークリッドの互除法

ユークリッドの互除法は、2つの整数の最大公約数を求めるためのアルゴリズムです。

この方法は、2つの整数のうち大きい方を小さい方で割り、その余りを求めます。

そして、その余りを新たな2つの整数として再帰的に同じ操作を繰り返します。

この操作を繰り返すことで、最終的に余りが0になった時の除数が最大公約数となります。

ユークリッドの互除法の概要

ユークリッドの互除法の概要は以下の通りです。

  1. 2つの整数をaとbとする。
  2. aをbで割った余りをrとする。
  3. rが0であれば、bが最大公約数となる。
  4. rが0でなければ、bをrで置き換え、再び2からの操作を繰り返す。

ユークリッドの互除法のアルゴリズム

ユークリッドの互除法のアルゴリズムは以下のようになります。

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

このアルゴリズムでは、再帰関数を使って最大公約数を求めています。

関数gcdは2つの整数aとbを受け取り、bが0の場合はaを返します。

それ以外の場合は、bとaをbで割った余りを引数として再帰的にgcd関数を呼び出します。

再帰関数を使った最大公約数の求め方

再帰関数を使った最大公約数の求め方は、ユークリッドの互除法を再帰的に呼び出すことで実現されます。

この方法は、再帰関数を使うことでコードの簡潔さと可読性を向上させることができます。

再帰関数の基本的な考え方

再帰関数は、関数内で自分自身を呼び出すことができる関数のことです。

再帰関数を使う場合、以下の2つの要素を考慮する必要があります。

  1. ベースケース(再帰の終了条件)：再帰呼び出しを終了させるための条件を設定します。

ユークリッドの互除法の場合、bが0のときがベースケースとなります。

  1. 再帰呼び出し：再帰関数内で自分自身を呼び出すことで、問題をより小さな部分問題に分割します。

ユークリッドの互除法の場合、bとaをbで割った余りを引数として再帰呼び出しを行います。

再帰関数を使った最大公約数のアルゴリズム

再帰関数を使った最大公約数のアルゴリズムは、先ほどのユークリッドの互除法のアルゴリズムと同じです。

再帰関数を使って最大公約数を求める場合、以下のようなコードになります。

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

このアルゴリズムを使って、2つの整数の最大公約数を求めることができます。

再帰関数を使った最大公約数の実装例

以下は、再帰関数を使って最大公約数を求めるための実装例です。

#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;
    printf("2つの整数を入力してください：");
    scanf("%d %d", &num1, &num2);
    int result = gcd(num1, num2);
    printf("最大公約数は%dです。\n", result);
    return 0;
}

このプログラムでは、ユーザーに2つの整数を入力してもらい、gcd関数を使って最大公約数を求めています。

最後に、求めた最大公約数を表示します。

再帰関数を使って最大公約数を求めることで、効率的かつ簡潔なコードを実現することができます。

数値処理
目次から探す