C 言語プログラミング | 最小公倍数の計算 | 再帰

はじめに

この実験では、再帰を使って 2 つの数の最小公倍数（LCM：Least Common Multiple）を求める C プログラムを書きます。LCM とは、両方の数で割り切れる最小の正の整数で、余りを残さずに割り切れます。

最小公倍数の概念を理解する

プログラミングを始める前に、最小公倍数（LCM）の概念を理解しましょう。2 つの整数の LCM は、両方の数の倍数である最小の正の整数です。2 つの数の LCM を求めるには、次の式を使うことができます。

LCM = (number1 * number2) / GCD

ここで、number1とnumber2は LCM を求める対象の 2 つの数であり、GCD はその 2 つの数の最大公約数です。

新しい C ファイルを作成する

プログラムを書く~/project/ディレクトリに、main.cという名前の新しい C ファイルを作成しましょう。

コードを書く

以下のコードをコピーしてmain.cファイルに貼り付けます。

#include<stdio.h>

int find_lcm(int, int); // 関数プロトタイプ宣言

int main()
{
    int a, b, lcm;
    printf("Enter two integers to find LCM:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // 関数呼び出し
    printf("LCM of %d and %d is %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // 関数定義
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

プログラムをコンパイルして実行する

main.cファイルを保存し、ターミナルで以下のコマンドを使ってプログラムをコンパイルします。

gcc main.c -o main

以下のコマンドを使ってプログラムを実行します。

./main

プロンプトが表示されたら 2 つの整数を入力し、プログラムはその 2 つの数の最小公倍数を表示します。

コードを理解する

さっき書いたコードを理解しましょう。

まず、#include<stdio.h>を使ってプログラムに標準入出力ライブラリを含めます。
後でプログラムで定義するfind_lcm関数のプロトタイプを宣言します。これは、メイン関数でfind_lcm関数を実際の定義より前に呼び出しているため必要です。
メイン関数では、3 つの整数型変数a、b、およびlcmを宣言します。
printfを使ってユーザーに 2 つの整数を入力するよう促し、scanfを使って入力を受け付けます。
その後、find_lcm関数を呼び出し、aとbを引数として渡します。
find_lcm関数は 2 つの整数型引数aとbを受け取り、再帰を使って 2 つの数の最小公倍数を返します。
静的変数tempを 1 で初期化します。これは、倍数をチェックしている現在の値を保持します。
各再帰で、tempがaとbの両方の倍数であるかどうかをチェックします。
倍数である場合、tempを最小公倍数として返します。
倍数でない場合、tempをインクリメントして再帰的にfind_lcm関数を呼び出し、最小公倍数を見つけるまで続けます。

プログラムをテストする

さまざまな入力値を使ってプログラムをテストし、正しい最小公倍数の出力が得られることを確認します。

完全なコード

再帰を使って 2 つの数の最小公倍数を求める C 言語プログラムの完全なコードは以下の通りです。

#include<stdio.h>

int find_lcm(int, int); // 関数プロトタイプ宣言

int main()
{
    int a, b, lcm;
    printf("Enter two integers to find LCM:\n");
    scanf("%d %d", &a, &b);
    lcm = find_lcm(a, b); // 関数呼び出し
    printf("LCM of %d and %d is %d.\n", a, b, lcm);

    return 0;
}

int find_lcm(int a, int b) // 関数定義
{
    static int temp = 1;
    if(temp % a == 0 && temp % b == 0)
        return temp;
    else
    {
        temp++;
        find_lcm(a, b);
        return temp;
    }
}

まとめ

この実験では、再帰を使って 2 つの数の最小公倍数を求める C 言語プログラムを書く方法を学びました。再帰関数を使って最小公倍数を求め、プログラムの各ステップを詳細に説明しました。また、ターミナルを使って C 言語プログラムをコンパイルして実行する方法も学びました。

C 言語における再帰的な最小公倍数の計算