Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: रिकर्सिव यूक्लिड एल्गोरिदम से GCD ज्ञात करना


महत्तम समापवर्तक (GCD)

दो संख्याओं का GCD वह सबसे बड़ी संख्या है जो दोनों को विभाजित करती है।

उदाहरण

63 = 7 × 3 × 3
21 = 7 × 3
GCD(63, 21) = 21

यूक्लिड का रिकर्सिव एल्गोरिदम

एल्गोरिदम: gcd(a, b) = gcd(b, a % b) जब तक b शून्य न हो जाए।

C++ प्रोग्राम उदाहरण

#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() फ़ंक्शन

रिकर्सिव फ़ंक्शन जो आधार स्थिति (b == 0) पर a लौटाता है, अन्यथा खुद को (b, a%b) के साथ कॉल करता है।

मुख्य फ़ंक्शन

उपयोगकर्ता से दो संख्याएं लेता है और gcd() फ़ंक्शन कॉल करके परिणाम प्रदर्शित करता है।

समय जटिलता

O(log min(a, b)) - बहुत कुशल एल्गोरिदम।

  1. - दो संख्याओं का GCD (महत्तम समापवर्तक) ज्ञात करना

    परिचय गणित में, ग्रेटेस्ट कॉमन डिवाइजर (GCD) वह सबसे बड़ी संभव पूर्णांक है जो दोनों पूर्णांकों को विभाजित करती है। शर्त यह है कि संख्याएँ शून्येतर होनी चाहिए। हम दो संख्याओं का GCD ज्ञात करने के लिए यूक्लिडियन एल्गोरिदम का पालन करेंगे। इनपुट और आउटपुट इनपुट: दो संख्याएँ 51 और 34 आउटपुट: GCD है: 17

  1. नॉन-रिकर्सिव फंक्शन का उपयोग करके संख्याओं का GCD खोजने का C प्रोग्राम नॉन-रिकर्सिव फंक्शन का उपयोग करके संख्याओं का GCD खोजने का C प्रोग्राम

    समस्या दो दी गई संख्याओं के लिए महत्तम सामान्य भाजक (GCD) को नॉन-रिकर्सिव फंक्शन का उपयोग करके खोजें। समाधान यह नीचे समझाया गया है कि नॉन-रिकर्सिव फंक्शन का उपयोग करके दो दी गई संख्याओं के लिए महत्तम सामान्य भाजक (GCD) कैसे खोजें। एल्गोरिथम नॉन-रिकर्सिव फंक्शन का उपयोग करके दो दी गई संख्याओं के लि

  1. रिकर्सिव फंक्शन का उपयोग करके संख्याओं का GCD खोजने का C प्रोग्राम रिकर्सिव फंक्शन का उपयोग करके संख्याओं का GCD खोजने का C प्रोग्राम

    समस्या C प्रोग्रामिंग भाषा में रिकर्सिव फंक्शन का उपयोग करके दो दी गई संख्याओं के लिए महत्तम सामान्य भाजक (GCD) खोजें। समाधान रिकर्सिव फंक्शन का उपयोग करके दो दी गई संख्याओं के लिए महत्तम सामान्य भाजक (GCD) खोजने का समाधान निम्नानुसार है: एल्गोरिथम रिकर्सिव फंक्शन का उपयोग करके दो दी गई संख्याओं क