सी ++ संस cmath लाइब्रेरी में जीसीडी फ़ंक्शन

Question

मैं एक मिश्रित संख्या वर्ग लिख रहा हूं और एक त्वरित और आसान 'सबसे बड़ा आम divisor' फ़ंक्शन की आवश्यकता है। क्या कोई मुझे कोड या कोड के लिंक दे सकता है?

Answer 1

मुझे बंद करने के लिए वोट देने का लुत्फ उठाना है - ऐसा लगता है कि एक कार्यान्वयन मुश्किल होगा, लेकिन जो निश्चित रूप से जानता है।

unsigned GCD(unsigned u, unsigned v) { 
    while (v != 0) { 
     unsigned r = u % v; 
     u = v; 
     v = r; 
    } 
    return u; 
} 

Answer 2

एक त्वरित पुनरावर्ती संस्करण:

unsigned int gcd (unsigned int n1, unsigned int n2) { 
    return (n2 == 0) ? n1 : gcd (n2, n1 % n2); 
} 

या समकक्ष पुनरावृत्ति संस्करण यदि आप हिंसक प्रत्यावर्तन ^{करने का विरोध कर रहे हैं (क)}:

unsigned int gcd (unsigned int n1, unsigned int n2) { 
    unsigned int tmp; 
    while (n2 != 0) { 
     tmp = n1; 
     n1 = n2; 
     n2 = tmp % n2; 
    } 
    return n1; 
} 

अपनी खुद में बस स्थानापन्न डेटा प्रकार, शून्य तुलना, असाइनमेंट और मॉड्यूलस विधि (यदि आप उदाहरण के लिए bignum कक्षा जैसे कुछ गैर-मूल प्रकार का उपयोग कर रहे हैं)।

इस समारोह वास्तव में स्क्रीन आकार के लिए अभिन्न पहलू अनुपात बाहर काम करने के लिए एक earlier answer of mine से आया है लेकिन मूल स्रोत इयूक्लिडियन एल्गोरिथ्म मैं एक लंबे समय पहले सीखा है, विस्तृत here on Wikipedia था अगर आप इसके पीछे गणित जानना चाहते हैं।

---

^(क) कुछ पुनरावर्ती समाधान के साथ समस्या यह है कि वे इस तरह के बहुत बुरी तरह से बाहर सोचा (छद्म साथ के रूप में जवाब दृष्टिकोण तो धीरे धीरे आपको ढेर स्थान शेष नहीं करते हैं इससे पहले कि आप वहां पहुंचें, है कोड):

def sum (a:unsigned, b:unsigned): 
    if b == 0: return a 
    return sum (a + 1, b - 1) 

आपको लगता है कि बहुत sum (1, 1000000000) की तरह कुछ पर महंगा लगता है के रूप में आप (करने की कोशिश) एक अरब का उपयोग या तो फ्रेम ढेर होगा। रिकर्सन के लिए आदर्श उपयोग केस बाइनरी खोज की तरह कुछ है जहां आप प्रत्येक पुनरावृत्ति के लिए आधे से समाधान स्थान को कम करते हैं। सबसे बड़ा आम विभाजक भी एक है जहां समाधान स्थान तेजी से कम हो जाता है, इसलिए भारी ढेर के उपयोग के बारे में डर वहां बेकार हैं।

Answer 3

Euclidean एल्गोरिथ्म सी

int gcd(int a, int b) { 
    while (b != 0) { 
    int t = b; 
    b = a % b; 
    a = t; 
    } 
    return a; 
} 

Answer 4

libstdC++ एल्गोरिथ्म पुस्तकालय एक छिपा gcd समारोह (मैं जी का उपयोग कर रहा ++ 4.6.3) है में लिखने के लिए काफी आसान है।

#include <iostream> 
#include <algorithm> 

int main() 
{ 
    cout << std::__gcd(100,24); 
    return 0; 
} 

आपका स्वागत है :)

अद्यतन: जैसा कि @ chema989, यह ध्यान दिया सी ++ 17 वहाँ std::gcd() समारोह <numeric> हैडर के साथ उपलब्ध है में।

Answer 5

मेरे दो सेंट; टेम्प्लेट की इयूक्लिडियन एल्गोरिथ्म अहस्ताक्षरित पूर्णांक प्रकार के लिए XOR swap का उपयोग कर:

template <class Unsigned> 
Unsigned gcd(Unsigned a, Unsigned b) 
{ 

    static_assert(
     std::numeric_limits<Unsigned>::is_integer && 
     !std::numeric_limits<Unsigned>::is_signed, "Unsigned required."); 

    while (b) 
    { 
     b ^= a; 
     a ^= b; 
     b = (b^a) % a; 
    } 
    return a; 
} 

Answer 6

std::gcd के लिए सी ++ 17 आप उपयोग कर सकते हैं हैडर <numeric> में परिभाषित:

auto res = std::gcd(10, 20);