โปรแกรมแบบเรียกซ้ำเพื่อพิมพ์สูตรสำหรับ GCD ของจำนวนเต็ม n ใน C++

เราได้รับจำนวนเต็มเป็นอินพุต เป้าหมายคือการพิมพ์สูตร GCD ของตัวเลข n โดยใช้การเรียกซ้ำ

เรารู้ว่า GCD ของตัวเลขสามตัวบอกว่า a1,b1 และ c1 จะเป็น gcd(a1,gcd(b1,c1)) ในทำนองเดียวกันสำหรับตัวเลขมากกว่าสามตัว gcd สามารถรับได้โดยสูตรเป็น gcd ( a1,gcd(b1, gcd(c1…..,gcd(y1,z1)).

ตัวอย่าง

ป้อนข้อมูล − Num =4;

ผลผลิต − สูตรคือ:

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

ป้อนข้อมูล − Num =6;

ผลผลิต − สูตรคือ:GCD(int a5, GCD(int a4, GCD(int a3, GCD(int a2, GCD(int a1, int b1)))))

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

ในแนวทางนี้ เราใช้ฟังก์ชันเรียกซ้ำ gcdFormula(int num1) ซึ่งนับจำนวนตัวเลขเป็นอินพุตและส่งกลับสตริงที่มีสูตรของ gcd สำหรับตัวเลข num1

สำหรับกรณีพื้นฐาน-:ถ้า num1 เป็น 1 สตริงส่งคืน "int b"+to_string(num1)+""

Else-:เรียกซ้ำอีกครั้งสำหรับ gcdFormula(num1-1) และต่อท้ายสตริงก่อนหน้า

• นำตัวเลขที่ใส่มา

• ฟังก์ชัน gcdFormula(int num1) ซึ่งนับจำนวนตัวเลขเป็นอินพุตและส่งกลับสตริงที่มีสูตรของ gcd สำหรับตัวเลข num1

• หาก num1 เป็น 1 ให้ส่งคืนสตริง "int b"+to_string(num1)+""

• อย่างอื่นพิมพ์ "GCD(int a"<

• ตามด้วยขั้นตอนการเรียกซ้ำเป็นการส่งคืน (gcdFormula(num1 - 1)+")")

• ในตอนท้าย สตริงทั้งหมดจะถูกส่งคืน

• ผลการพิมพ์ที่ได้รับภายใน main.

ตัวอย่าง

#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))))))