【C++】再帰を使ってn個の整数のGCD（最大公約数）の式を出力するプログラム

この記事では、整数が入力として与えられたときに、再帰（リカージョン）を利用してn個の整数のGCD（最大公約数）を求める式を出力する方法を解説します。

GCDには次のような性質があります。3つの数 a1、b1、c1 の最大公約数は gcd(a1, gcd(b1, c1)) のように表せます。これを一般化すると、3つ以上の数についても、

gcd(a1, gcd(b1, gcd(c1, …, gcd(y1, z1))))

という入れ子構造の式でGCDを求めることができます。

実行例

入力： Num = 4;

出力：

Formula is:
GCD(int a3, GCD(int a2, GCD(int a1, int b1)))

入力： Num = 6;

出力：

Formula is: GCD(int a5, GCD(int a4, GCD(int a3, GCD(int a2, GCD(int a1, int b1)))))

プログラムのアプローチ

このアプローチでは、引数として数の個数を受け取り、その個数に対応するGCDの式を含む文字列を返す再帰関数 gcdFormula(int num1) を使用します。

ベースケース： num1 が 1 の場合、文字列 "int b" + to_string(num1) を返します。
再帰ケース： それ以外の場合は、gcdFormula(num1 - 1) を再帰的に呼び出し、その結果に前段の文字列を連結して返します。

具体的な手順は以下の通りです。

• 個数を表す数値 Num を入力として受け取ります。
• 関数 gcdFormula(int num1) は、数の個数を受け取り、対応するGCDの式を含む文字列を返します。
• num1 が 1 の場合、文字列 "int b" + to_string(num1) を返します。
• それ以外の場合は、"GCD(int a" << num1 - 1 << ", " を出力します。
• 続いて再帰呼び出しを行い、return (gcdFormula(num1 - 1) + ")") として閉じ括弧を追加します。
• 最終的に完全な式の文字列が返されます。
• main関数内で結果を出力します。

C++サンプルコード

#include <bits/stdc++.h>
using namespace std;
string gcdFormula(int num1){
   if (num1 == 1){
      return ("int b"+to_string(num1)+"");
   }
   else{
      cout<<"GCD(int a"<<num1-1<<", ";
      return (gcdFormula(num1 - 1)+")");
   }
}
int main(){
   int Num = 6;
   cout<<"Formula is :"<<endl;
   cout<<gcdFormula(Num);
   return 0;
}

出力結果

上記のコードを実行すると、以下の出力が得られます。

Formula is :
GCD(int a6, GCD(int a5, GCD(int a4, GCD(int a3, GCD(int a2, GCD(int a1, int b1))))))