입력으로 정수가 주어집니다. 목표는 재귀를 사용하여 n개 숫자의 GCD 공식을 출력하는 것입니다.
우리는 세 숫자의 GCD가 a1,b1 및 c1이 gcd(a1,gcd(b1,c1))가 될 것이라는 것을 알고 있습니다. 세 개 이상의 숫자에 대해 유사하게 gcd는 gcd( a1,gcd(b1, gcd(c1…..,gcd(y1,z1)).
예시
입력 - 숫자 =4;
출력 − 공식은 다음과 같습니다.
GCD(int a3, GCD(int a2, GCD(int a1, int b1)))
입력 - 숫자 =6;
출력 - 공식은 다음과 같습니다. GCD(int a5, GCD(int a4, GCD(int a3, GCD(int a2, GCD(int a1, int b1)))))
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서 우리는 재귀 함수 gcdFormula(int num1)를 사용하고 있습니다. 이 함수는 숫자의 개수를 입력으로 받아 num1 숫자에 대한 gcd 공식을 포함하는 문자열을 반환합니다.
기본 경우-:num1이 1이면 문자열 "int b"+to_string(num1)+""을 반환합니다.
Else-:gcdFormula(num1-1)에 대해 다시 재귀하고 이전 문자열을 추가합니다.
-
입력된 번호를 가져옵니다.
-
숫자의 개수를 입력으로 받아 num1 숫자에 대한 gcd 공식을 포함하는 문자열을 반환하는 함수 gcdFormula(int num1)
-
num1이 1이면 문자열 "int b"+to_string(num1)+""을 반환합니다.
-
그렇지 않으면 인쇄 "GCD(int a"<
-
다음에는 return으로 재귀 단계가 뒤따릅니다. (gcdFormula(num1 - 1)+")")
-
마지막에 전체 문자열이 반환됩니다.
-
메인 내부에서 얻은 결과를 인쇄합니다.
예시
#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))))))