C++ で関数を使って最大公約数を求める

はじめに

この実験では、C++ の関数を使って2つの数の最大公約数（Greatest Common Divisor: GCD）を求める方法を学びます。GCD は、与えられた2つの数を割り切る最大の数です。再帰的なアプローチを使って関数を実装します。

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL cpp(("C++")) -.-> cpp/ControlFlowGroup(["Control Flow"]) cpp(("C++")) -.-> cpp/IOandFileHandlingGroup(["I/O and File Handling"]) cpp(("C++")) -.-> cpp/SyntaxandStyleGroup(["Syntax and Style"]) cpp(("C++")) -.-> cpp/BasicsGroup(["Basics"]) cpp(("C++")) -.-> cpp/FunctionsGroup(["Functions"]) cpp/BasicsGroup -.-> cpp/variables("Variables") cpp/BasicsGroup -.-> cpp/operators("Operators") cpp/BasicsGroup -.-> cpp/strings("Strings") cpp/ControlFlowGroup -.-> cpp/conditions("Conditions") cpp/FunctionsGroup -.-> cpp/function_parameters("Function Parameters") cpp/FunctionsGroup -.-> cpp/recursion("Recursion") cpp/IOandFileHandlingGroup -.-> cpp/output("Output") cpp/IOandFileHandlingGroup -.-> cpp/files("Files") cpp/SyntaxandStyleGroup -.-> cpp/code_formatting("Code Formatting") subgraph Lab Skills cpp/variables -.-> lab-96189{{"関数を使って最大公約数を求める"}} cpp/operators -.-> lab-96189{{"関数を使って最大公約数を求める"}} cpp/strings -.-> lab-96189{{"関数を使って最大公約数を求める"}} cpp/conditions -.-> lab-96189{{"関数を使って最大公約数を求める"}} cpp/function_parameters -.-> lab-96189{{"関数を使って最大公約数を求める"}} cpp/recursion -.-> lab-96189{{"関数を使って最大公約数を求める"}} cpp/output -.-> lab-96189{{"関数を使って最大公約数を求める"}} cpp/files -.-> lab-96189{{"関数を使って最大公約数を求める"}} cpp/code_formatting -.-> lab-96189{{"関数を使って最大公約数を求める"}} end

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

~/project ディレクトリに main.cpp という名前の新しいC++ファイルを作成します。

touch ~/project/main.cpp

ライブラリをインクルードする

ファイルに必要なライブラリをインクルードします。

#include<iostream>

GCDを計算する関数を定義する

2つの整数型の引数を入力として受け取り、整数型を出力として返す再帰関数 gcd() を定義します。この出力は、2つの入力数のGCDになります。

int gcd(int a, int b) {
    if (a == 0 || b == 0)
        return 0;
    else if (a == b)
        return a;
    else if (a > b)
        return gcd(a - b, b);
    else
        return gcd(a, b - a);
}

メイン関数を書く

main() 関数で、2つの整数型の変数を宣言して値を代入します。その後、これら2つの変数をパラメータとして gcd() 関数を呼び出し、結果を出力します。

int main() {
    int a = 105, b = 30;
    std::cout << "GCD of " << a << " and " << b << " is " << gcd(a,b) << std::endl;
    return 0;
}

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

ファイルに加えた変更を保存して終了します。以下の端末コマンドを使ってプログラムをコンパイルします。

g++ main.cpp -o main

プログラムを実行するには、端末に以下のコマンドを入力します。

./main

出力

プログラムを実行した後、端末には以下のように出力されます。

GCD of 105 and 30 is 15

まとめ

この実験では、C++ の再帰関数を使って2つの数の最大公約数（GCD）を求める方法を学びました。これは、コンピュータサイエンスと数学において便利な応用です。