تصف هذه المقالة خوارزمية Java لحل أعظم مقسوم مشترك بين اثنين من الأعداد الصحيحة غير السالبة. شاركه للرجوع إليه ، على النحو التالي:
وظائف الكود:
1. تنفيذ Java (رمز المصدر الكامل مع حالات الاختبار) ؛
2. حل أعظم مقسومات مشتركة بين أعداد صحيحة غير سالبة P و Q (p> = q) ؛
3. حلان: طريقة الحلقة والطريقة العودية ؛
رمز المصدر الكامل:
/ * GCD: Greateast Common Compisor */Public Class GCD {public static void main (String args []) {/ * test case */int p = 32 ؛ int q = 24 ؛ System.out.println ("أعظم Divisior من"+P+"و"+Q+"IS /N"+"[GCD1]:"+GCD1 (P ، Q)+" /N"+"[GCD2]:"+GCD2 (P ، Q)) ؛ } // (q ٪ gcd == 0 و p ٪ gcd == 0 [gcd from q إلى 1]) static int gcd1 (int p ، int q) {int gcd = 1 ؛ int d = q ؛ بينما (d> 0) {d-- ؛ if (q ٪ d == 0 && p ٪ d == 0) {gcd = d ؛ استراحة؛ }} إرجاع GCD ؛ } // gcd (p ، q) = gcd (q ، p ٪ q) [if q = 0 ، gcd = p] public static int gcd2 (int p ، int q) {if (q == 0) return p ؛ int r = p ٪ q ؛ //system.out.println("("+q+"،"+r+ ")") ؛ إرجاع GCD2 (Q ، R) ؛ }}تشغيل لقطة الشاشة:
شرح الرمز:
الطريقة الدائرية GCD1 (P ، Q)
الوصف اللغوي الطبيعي: حلقة الحلول تحل أكبر مقسّرات شائعة لاثنين من الأعداد الصحيحة غير السلبية P ، Q (p> = q) ، أي ، يحل القيمة القصوى للقسمة المشتركة لـ Q. دع D (مقسمة) الانخفاض من P (خطوة الانخفاض = 1) D هو دائمًا "الحد الأقصى لقيمة الحالة التي على وشك أن تكون راضية". عندما يلتقي D بالشرط (يمكن تقسيمه على P و Divisible بواسطة P) ، فإن D هو المقسوم الشائع لـ P و Q ، و D هو أعظم مقسوم شائع لـ P و Q ؛
الطريقة العودية GCD2 (P ، Q)
الوصف اللغوي الطبيعي: الطريقة العودية تحل أعظم مقسوم شائع لاثنين من الأعداد الصحيحة غير السالبة P ، Q (p> = q). عندما يكون Q يساوي 0 ، فإن أعظم مقسوم مشترك هو P ؛ خلاف ذلك ، خذ ما تبقى من p و q للحصول على r = p ٪ q ، وأكبر مقسوم مشترك لـ p و q هو أعظم مقسوم شائع لـ Q و R ؛
تجربة الكود:
فيما يتعلق بطريقة الحلقة ، في البداية ، كان ما فكرت به هو كتابة طريقة لحل المقسومات الشائعة ، واستخدام مجموعة عدد صحيح لتخزين جميع المقسومات الشائعة لأحد الأعداد غير السالبة ، ثم قارن وأكتشف أكبر مقسوم مشترك شائع في P و Q ، وهو أعظم مقسمة شائعة من رقمين. في وقت لاحق ، اعتقدت ، لأنه هو العثور على الحد الأقصى ، ألن يكون من الأسهل الانخفاض مباشرة من الظهر إلى الأمام؟ يمكن أن يضمن التناقص من الخلف إلى المقدمة أن هذا الرقم هو دائمًا الأكبر في الوقت الحالي ، لأن الأشخاص الأكبر مما لا يفي بالظروف (يمكن تقسيمه بواسطة P و Q في نفس الوقت) ، مما يتجنب مشكلة العثور على الحد الأقصى في البداية. على الرغم من أن هناك العديد من الطرق للعثور على الحد الأقصى ، إذا كان لديك أو لم تكن بحاجة لإثبات وبحث ، هاها ، لماذا تشعر قليلاً بالفلسفة؟
فيما يتعلق بالكروية ، فإن ما يمكنني فهمه تمامًا بناءً على حدسي هو الجملة الوحيدة التي يعتبرها أعظم مقسوم مشترك لـ P و Q هو أعظم مقسوم شائع لـ Q و R (r = p ٪ Q) ، وهي بداية الحلبة ، لكنني ما زلت لا أفهم تمامًا أن حالة النهاية هي 0 ، وإعادة P ؛
على الرغم من أنه حل بسيط للغاية لأكبر خوارزمية المقسومات الشائعة ، إلا أنني يجب أن أكتبها بطريقتين ، بشكل أساسي لأشعر بأسلوب التكرار الذي لست على دراية به. في الماضي ، رأيت الصيغة الواضحة لخوارزمية العودية لحل برج هانوفر وأرقام فيبوناتشي التي كانت مضاءة هناك ، وكنت تنهد أن هذه الرياضيات تمامًا! كان الشعور الذي تعلمته اليوم أكثر صدمة من ذلك الوقت. تساءلت عما حدث وحلها بشكل غريب. في ذلك الوقت ، لم أهتم كثيرًا بالذاكرة والكفاءة والمؤشرات الأخرى. لقد ظننت أن الرجال الذين يمكنهم التفكير في هذا كان ذكيًا حقًا. بالنسبة لهم ، سواء كان جهاز كمبيوتر أو لغة برمجة ، فقد كانت مجرد أداة لحل المشكلة. يقول بعض الناس أن العودية هي خوارزمية تسمح للدماغ بالتفكير في أجهزة الكمبيوتر لحسابها ، وهي تشعر أنها مناسبة حقًا.
مراجع
سلسلة برمجة تورينج: الخوارزميات (الطبعة الرابعة) روبرت سيدجويك (مؤلف) ، كيفن واين (مؤلف) ، Xie Luyun (مترجم)
لمزيد من المعلومات حول خوارزميات Java ، يمكن للقراء المهتمين بهذا الموقع عرض الموضوعات: "بنية بيانات Java وبرنامج تعليمي الخوارزمية" ، "ملخص" Tips Java ".
آمل أن يكون هذا المقال مفيدًا لبرمجة Java للجميع.