โปรแกรม C++ เพื่อค้นหา GCD ของตัวเลขสองตัวโดยใช้อัลกอริทึมยุคลิดแบบเรียกซ้ำ

ตัวหารร่วมที่ยิ่งใหญ่ที่สุด (GCD) ของตัวเลขสองตัวคือจำนวนที่มากที่สุดที่หารทั้งสองตัวได้

ตัวอย่างเช่น สมมติว่าเรามีตัวเลขสองตัวคือ 63 และ 21

63 = 7 * 3 * 3
21 = 7 * 3

ดังนั้น GCD ของ 63 และ 21 คือ 21

อัลกอริทึมของ Euclid แบบเรียกซ้ำจะคำนวณ GCD โดยใช้จำนวนเต็มบวก a และ b และคืนค่า b และ a%b จนถึง b เป็นศูนย์

โปรแกรมค้นหา GCD ของตัวเลขสองตัวโดยใช้อัลกอริธึมแบบเรียกซ้ำของ Euclid มีดังต่อไปนี้ -

ตัวอย่าง

#include <iostream>
using namespace std;
int gcd(int a, int b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}
int main() {
   int a , b;
   cout<<"Enter the values of a and b: "<<endl;
   cin>>a>>b;
   cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
   return 0;
}

ผลลัพธ์

ผลลัพธ์ของโปรแกรมข้างต้นเป็นดังนี้ −

Enter the values of a and b: 105 30
GCD of 105 and 30 is 15

ในโปรแกรมข้างต้น gcd() เป็นฟังก์ชันแบบเรียกซ้ำ มันมีพารามิเตอร์สองตัวคือ a และ b ถ้า b เท่ากับ 0 แล้ว a จะถูกส่งกลับไปยังฟังก์ชัน main() มิฉะนั้น gcd() ฟังก์ชันจะเรียกตัวเองซ้ำด้วยค่า b และ a%b สิ่งนี้แสดงให้เห็นโดยข้อมูลโค้ดต่อไปนี้ -

int gcd(int a, int b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}

ในฟังก์ชัน main() ผู้ใช้จะขอค่า a และ b จากนั้นเรียกใช้ฟังก์ชัน gcd() และแสดงค่าของ GCD ของ a และ b ด้านล่างนี้ −

int main() {
   int a , b;
   cout<<"Enter the values of a and b: "<<endl;
   cin>>a>>b;
   cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
   return 0;
}