Chương trình đệ quy để in công thức cho GCD của n số nguyên trong C ++

Chúng tôi được cung cấp một số nguyên làm đầu vào. Mục đích là in công thức GCD của n số bằng cách sử dụng đệ quy.

Chúng ta biết rằng GCD của ba số cho biết a1, b1 và c1 sẽ là gcd (a1, gcd (b1, c1)). Tương tự đối với nhiều hơn ba số, gcd có thể được tính theo công thức như gcd (a1, gcd (b1, gcd (c1… .., gcd (y1, z1)).

Ví dụ

Đầu vào - Số =4;

Đầu ra - Công thức là:

GCD (int a3, GCD (int a2, GCD (int a1, int b1)))

Đầu vào - Số =6;

Đầu ra - Công thức là:GCD (int a5, GCD (int a4, GCD (int a3, GCD (int a2, GCD (int a1, int b1)))))

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Trong cách tiếp cận này, chúng tôi đang sử dụng hàm đệ quy gcdFormula (int num1) nhận đếm số làm đầu vào và trả về chuỗi chứa công thức của gcd cho số num1.

Đối với các trường hợp cơ sở-:if num1 là 1 chuỗi trả về "int b" + to_string (num1) + "".

Else-:Lặp lại lần nữa cho gcdFormula (num1-1) và nối thêm chuỗi trước đó.

• Lấy số đầu vào là Num.

• Hàm gcdFormula (int num1) nhận đếm số làm đầu vào và trả về chuỗi chứa công thức của gcd cho số num1

• Nếu num1 là 1 thì trả về chuỗi "int b" + to_string (num1) + "".

• Bản in khác "GCD (int a" <

• Tiếp theo là bước đệ quy là return (gcdFormula (num1 - 1) + ")")

• Cuối cùng, toàn bộ chuỗi sẽ được trả về.

• In kết quả nhận được bên trong main.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

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