দুটি সংখ্যার সর্বশ্রেষ্ঠ সাধারণ ভাজক (GCD) হল বৃহত্তম সংখ্যা যা তাদের উভয়কে ভাগ করে।
উদাহরণস্বরূপ:ধরা যাক আমাদের নিম্নলিখিত দুটি সংখ্যা রয়েছে:45 এবং 27
63 = 7 * 3 * 3 42 = 7 * 3 * 2 So, the GCD of 63 and 42 is 21
পুনরাবৃত্তি ব্যবহার করে দুটি সংখ্যার GCD খুঁজে বের করার জন্য একটি প্রোগ্রাম নিম্নরূপ দেওয়া হয়েছে।
উদাহরণ
#include<iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
}
int main() {
int a = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} আউটপুট
GCD of 63 and 42 is 21
উপরের প্রোগ্রামে, gcd() একটি পুনরাবৃত্ত ফাংশন। এর দুটি পরামিতি রয়েছে যেমন a এবং b। a বা b 0 হলে, ফাংশনটি 0 প্রদান করে। a বা b সমান হলে, ফাংশনটি a প্রদান করে। a যদি b এর থেকে বড় হয়, ফাংশনটি recursively নিজেকে a-b এবং b মান দিয়ে কল করে। b a এর থেকে বড় হলে, ফাংশনটি recursively নিজেকে a এবং b-a মান দিয়ে কল করে।
এটি নিম্নলিখিত কোড স্নিপেট দ্বারা প্রদর্শিত হয়৷
৷int gcd(int a, int b) {
if (a == 0 || b == 0)
return 0;
else if (a == b)
return a;
else if (a > b)
return gcd(a-b, b);
else return gcd(a, b-a);
} ফেরত দিন পুনরাবৃত্তি ব্যবহার করে দুটি সংখ্যার GCD খুঁজে বের করার আরেকটি পদ্ধতি নিম্নরূপ।
উদাহরণ
#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 = 63, b = 42;
cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
return 0;
} আউটপুট
GCD of 63 and 42 is 21
উপরের প্রোগ্রামে, 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);
} 