दो संख्याओं का सबसे बड़ा सामान्य भाजक (GCD) उन दोनों को विभाजित करने वाली सबसे बड़ी संख्या है।
उदाहरण के लिए:मान लें कि हमारे पास निम्नलिखित दो संख्याएँ हैं:45 और 27
63 = 7 * 3 * 3 42 = 7 * 3 * 2 So, the GCD of 63 and 42 is 21
रिकर्सन का उपयोग करके दो नंबरों के जीसीडी को खोजने का कार्यक्रम इस प्रकार दिया गया है।
उदाहरण
#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 0 है, तो फ़ंक्शन 0 देता है। यदि a या b बराबर हैं, तो फ़ंक्शन a देता है। यदि a, b से बड़ा है, तो फ़ंक्शन स्वयं को a-b और b मानों के साथ पुनरावर्ती रूप से कॉल करता है। यदि b, a से बड़ा है, तो फ़ंक्शन स्वयं को 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() एक पुनरावर्ती कार्य है। इसके दो पैरामीटर हैं यानी ए और बी। यदि b 0 से बड़ा है, तो a मुख्य () फ़ंक्शन पर वापस आ जाता है। अन्यथा, gcd() फ़ंक्शन स्वयं को b और a%b मानों के साथ पुनरावर्ती रूप से कॉल करता है।
यह निम्नलिखित कोड स्निपेट का उपयोग करके प्रदर्शित किया जाता है।
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}