Cho một số nguyên làm đầu vào. Mục tiêu là in công thức GCD của n số bằng đệ quy.
Biết GCD của ba số a1,b1,c1 là gcd(a1,gcd(b1,c1)). Tương tự cho nhiều số: gcd(a1,gcd(b1,gcd(c1,...,gcd(y1,z1)))).
Ví dụ
Đầu vào - Num = 4
Đầu ra - Công thức là:
GCD(int a3, GCD(int a2, GCD(int a1, int b1)))
Đầu vào - Num = 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 sử dụng trong chương trình dưới đây
Dùng hàm đệ quy gcdFormula(int num1) nhận số lượng số, trả về chuỗi chứa công thức GCD cho num1 số.
Trường hợp cơ sở: num1 == 1 trả về "int b" + to_string(num1).
Ngược lại: in "GCD(int a" + num1-1 + ", " rồi đệ quy gcdFormula(num1-1) + ")".
Nhập số Num.
Hàm gcdFormula(int num1) trả về chuỗi công thức GCD.
Nếu num1 == 1 trả về "int b" + to_string(num1).
Ngược lại in "GCD(int a" << num1-1 << ", "; return gcdFormula(num1-1) + ")".
In kết quả trong main.
Ví dụ mã
#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<<"Công thức là :"<<endl; cout<<gcdFormula(Num); return 0; }
Đầu ra
Nếu chạy mã trên sẽ cho kết quả:
Công thức là : GCD(int a5, GCD(int a4, GCD(int a3, GCD(int a2, GCD(int a1, int b1)))))