🤣 🧚🏽 🤽🏽 जीसीडी की गणना - एक त्रुटि जो ध्यान नहीं दी जाती है 🔞 👩🏼‍🏭 👩🏻‍🌾

जीसीडी क्या है, स्कूल से सभी जानते हैं। जो लोग भूल गए हैं, मैं आपको याद दिलाता हूं: जीसीडी सबसे बड़ा सामान्य भाजक है, दो पूर्णांकों को शेष के बिना विभाजित करता है। उदाहरण के लिए, संख्या 100 और 45 का GCD 5 है, और संख्या 17 और 7 का GCD है। इस संख्या के लिए कई अलग-अलग खोज एल्गोरिदम हैं। हालांकि, इस तथ्य के बावजूद कि ये काफी सरल एल्गोरिदम हैं, वे अक्सर एक छोटी, लेकिन बहुत महत्वपूर्ण त्रुटि करते हैं।

जीसीडी गणना एल्गोरिदम

मैं GCD की गणना के लिए 5 एल्गोरिदम पर विचार करूंगा:

1. पुनरावृत्ति और बचे हुए

public static int gcd_1(int a, int b) { if (b == 0) return a; return gcd_1(b, a % b); }

2. एक ही अवशिष्ट, लेकिन पुनरावृत्ति के बिना

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

3. क्लासिक यूक्लिडियन एल्गोरिथ्म

 public static int gcd_3(int a, int b) { while (a != b) { if (a > b) { a = a - b; } else { b = b - a; } } return a; }

4. जीसीडी खोजने के लिए बाइनरी एल्गोरिदम

 public static int gcd_4(int a, int b) { if (a == b) return a; if (a == 0) return b; if (b == 0) return a; if ((~a & 1) != 0) { if ((b & 1) != 0) return gcd_4(a >> 1, b); else return gcd_4(a >> 1, b >> 1) << 1; } if ((~b & 1) != 0) return gcd_4(a, b >> 1); if (a > b) return gcd_4((a - b) >> 1, b); return gcd_4((b - a) >> 1, a); }

5. बाइनरी एल्गोरिथ्म बिट अंकगणितीय पर आधारित है

 public static int gcd_5(int a, int b) { int shift; if (a == 0) return b; if (b == 0) return a; for (shift = 0; ((a | b) & 1) == 0; ++shift) { a >>= 1; b >>= 1; } while ((a & 1) == 0) a >>= 1; do { while ((b & 1) == 0) b >>= 1; if (a > b) { int t = b; b = a; a = t; } b = b - a; } while (b != 0); return a << shift; }

स्वाभाविक रूप से, पहला विकल्प सबसे अधिक बार लिखा जाता है - यह याद रखना आसान है, जल्दी से लिखा गया है, और तेजी से पर्याप्त है।

pretests

कार्यान्वयन ऐसे परीक्षणों पर सही ढंग से काम करता है:

 gcd(1, 10) = 1 gcd(5, 10) = 5 gcd(24, 24) = 24 gcd(0, 0) = 0 gcd(5,10) = 5

स्वाभाविक रूप से, वे समान परीक्षणों पर काम करेंगे, जहां गैर-नकारात्मक पूर्णांक तर्क के रूप में कार्य करते हैं। लेकिन क्या अगर ...

पहली चाल परीक्षण

... यदि आप संख्याओं में से एक को शून्य से प्रतिस्थापित करते हैं? उदाहरण के लिए, इस तरह:

 gcd(5, 0) = 5 gcd(0, 15) = 15

शास्त्रीय यूक्लिडियन एल्गोरिथ्म (नंबर 3) पहले से ही एक अनंत लूप में आता है।

गहरी खुदाई

परिभाषा के अनुसार, GCD को किन्हीं दो पूर्णांकों के लिए परिभाषित किया जा सकता है। तो उन परीक्षणों की कोशिश क्यों न करें जहां एक संख्या नकारात्मक है:

 gcd(-5,10) = ?

सब कुछ दिलचस्प होता जा रहा है। पहले दो कार्यान्वयन उत्तर के रूप में -5 देते हैं। तीसरा एल्गोरिथ्म फिर से एक अनंत लूप में आता है। उसके साथ एक अनंत लूप में पांचवां एल्गोरिथ्म है। चौथा StackOverFlow पर गिरता है - सबसे अधिक संभावना एक अंतहीन लूप में भी आती है।
लेकिन उत्तर -5 गलत है। परिभाषा के अनुसार, GCD सबसे बड़ा सामान्य कारक है। और ऐसा नंबर 5 है । आखिरकार, पहली और दूसरी संख्या 5 से विभाज्य है। पहले दो कार्यान्वयन सही उत्तर नहीं देते हैं।

क्यों समाधान नंबर 3-5 एक अनंत लूप में आते हैं?

यूक्लिडियन एल्गोरिथ्म तर्कों में अनंत वृद्धि के कारण लूप में जाता है यदि उनमें से एक नकारात्मक है। वास्तव में, यदि आप इन रेखाओं को देखते हैं, तो आप देख सकते हैं कि यदि a (या b ) ऋणात्मक है, तो घटाव संचालन को जोड़ दिया जाता है।

 if (a > b) { a = a - b; } else { b = b - a; }

चौथी और पाँचवीं एल्गोरिथ्म में एक समान बात होती है:

 if (a > b) return gcd_4((a - b) >> 1, b); return gcd_4((b - a) >> 1, a);

 if (a > b) { int t = b; b = a; a = t; } b = b - a;

ऐसी स्थिति में जहां एक या बी 0 के बराबर होता है, फिर शून्य का एक अनंत घटाव होता है, जो किसी भी तरह से तर्कों का मूल्य नहीं बदलता है।

तो क्या गलत है?

ये सभी एल्गोरिदम इनपुट के लिए सही हैं जब संख्या ए और बी दोनों गैर-नकारात्मक पूर्णांक हैं। लेकिन हमें एक बार फिर याद करते हैं - जीसीडी किसी भी दो पूर्णांकों के लिए मौजूद है।

क्या करें?

फ़ंक्शन के तर्क के रूप में, आप संख्याओं के निरपेक्ष मान को पारित कर सकते हैं, फिर उत्तर सही होगा:

 int ans = gcd(Math.abs(a), Math.abs(b));

समस्या को हल करने का दूसरा तरीका उत्तर का निरपेक्ष मान लौटाना है:

 public static int gcd(int a, int b) { if (b == 0) return Math.abs(a); return gcd(b, a % b); }

दूसरा विकल्प बहुत बेहतर है: पहले विकल्प की तुलना में कम अनावश्यक गणना की जाएगी।

परिणाम

हमने सबसे बड़े सामान्य कारक की गणना के लिए पांच अलग-अलग विकल्पों पर ध्यान दिया। उनमें से प्रत्येक के लिए, हमने उस इनपुट का संकेत दिया, जिस पर उत्तर मौजूद है, लेकिन समाधान "गिरता है", साथ ही समस्या को हल करने का एक तरीका है।
इस तरह की छोटी गलतियों को अक्सर इस तथ्य के कारण किया जाता है कि वे किसी समस्या को हल करने के लिए "फिसलन" स्थानों को नोटिस नहीं करते हैं। उनमें से कुछ परीक्षण प्रक्रिया के दौरान पकड़े जाते हैं, और कुछ ध्यान नहीं देते हैं।
जीसीडी की गणना के साथ स्थिति में, लगभग सभी कार्यान्वयन एक त्रुटि के साथ दिए गए हैं। वेब पर, मुझे केवल सही ढंग से काम करने वाले समाधानों के जोड़े मिले, बाकी पोस्ट की शुरुआत में दिए गए समान हैं।

प्रयुक्त साहित्य, स्रोत, कार्यान्वयन:

बाइनरी जीसीडी एल्गोरिदम - विकिपीडिया
यूक्लिडियन एल्गोरिथ्म - विकिपीडिया
यूक्लिडियन एल्गोरिथ्म - ई-मैक्सएक्स
बाइनरी जीसीडी - डिक्शनरी ऑफ अल्गोरिद्म और डेटा स्ट्रक्चर्स
कोरमेन - एल्गोरिदम - निर्माण और विश्लेषण

जीसीडी की गणना - एक त्रुटि जो ध्यान नहीं दी जाती है