كيفية العثور على القاسم المشترك الأكبر لرقمين في بايثون

واحدة من مهام البرمجة المشتركة هي العثور على القاسم المشترك الأكبر (غد) من رقمين. العقدة هي أكبر رقم مقسوم على كل من الرقم الأول والرقم الثاني. في البرمجة ، يمكن استخدام خوارزمية إقليدس للعثور على العقد ، والتي تستند إلى المبدأ التالي: أكبر قاسم مشترك لرقمين يساوي أكبر قاسم مشترك لبقية قسمة الرقم الأول على الرقم الثاني.

تجد خوارزمية إقليدس بشكل متكرر عقدة رقمين. يتكون من خطوتين: إذا كان الرقم الثاني صفرا ، فإن القاسم المشترك الأكبر يساوي الرقم الأول; خلاف ذلك ، يمكن العثور على عقدة الأرقام المطلوبة كأكبر قاسم مشترك للرقم الثاني والباقي من قسمة الرقم الأول على الرقم الثاني.

مثال: ابحث عن عقدة الرقمين 12 و 18. اقسم 18 على 12 واحصل على الباقي 6. ابحث عن عقدة الرقمين 12 و 6 (باقي القسمة السابقة). قسم 12 على 6 واحصل على الباقي 0. في هذه الخطوة ، تكون العقدة 6 ، لأن ما تبقى من القسمة هو صفر.

في بايثون ، يمكنك كتابة دالة للعثور على عقد رقمين باستخدام خوارزمية إقليدس. تأخذ الدالة وسيطتين-الأرقام التي تحتاج إلى العثور على العقدة ، وإرجاع العقدة نفسها. باستخدام هذه الوظيفة ، يمكنك العثور على عقدة أي رقمين في بايثون واستخدامها لحل المشكلات المختلفة.

1. تحديد القاسم المشترك الأكبر
2. طريقة إقليدس
3. وصف الخوارزمية
4. التنفيذ العودي
5. باستخدام العودية
6. مثال الاستخدام
7. سؤال وجواب
8. كيف يمكنني العثور على القاسم المشترك الأكبر (عقدة) من رقمين في بيثون?

تحديد القاسم المشترك الأكبر

أكبر القاسم المشترك (غد) هو أكبر عدد الذي هو في وقت واحد المقسوم من اثنين أو أكثر من الأرقام. يمكن أن تكون العقدة موجبة أو سالبة اعتمادا على علامات الأرقام.

يمكن تنفيذ تعريف العقدة بطرق مختلفة:

1. طريقة القسمة مع الباقي
2. طريقة إقليدس
3. خوارزمية شتاين

الطريقة الأكثر شيوعا والأبسط هي طريقة تقسيم الباقي. يعتمد على حقيقة أنه بالنسبة للأرقام أ و ب يوجد أ = ف * ب + ص ، أين ف هو حاصل القسمة و ص هو ما تبقى من قسمة أ على ب. إذا كان ما تبقى من ص هو 0 ، إذن ب هي عقدة الرقمين أ و ب. خلاف ذلك ، الباقي غير صفري ويتم العثور على العقدة بقسمة ب على ص.

تعتمد الطريقة الإقليدية على نفس المبدأ ، ولكن يتم تنفيذها بشكل مختلف قليلا. للأرقام أ و ب ، هناك الباقي ص من قسمة أ على ب. ثم يتم استبدال الأرقام أ و ب بالقيم ب و ص ، على التوالي. تتكرر هذه العملية حتى يصبح الباقي 0. في النهاية ، سيتم الحصول على القيمة ب كعقدة.

خوارزمية شتاين هي نسخة محسنة من الطريقة الإقليدية ، والتي تتيح لك العثور على عقد رقمين بكفاءة أكبر. في خوارزمية شتاين ، يتم حساب الباقي باستخدام عمليات البت ، مما يقلل من عدد عمليات القسمة. هذا مفيد بشكل خاص عند العمل بأعداد كبيرة ، لأنه يقلل من وقت تنفيذ الخوارزمية.

في بيثون ، يمكنك استخدام الرياضيات.غد () وظيفة من وحدة الرياضيات للعثور على العقد. فإنه يأخذ وسيطتين وإرجاع عقدة من هذه الأرقام.

طريقة إقليدس

الطريقة الإقليدية هي خوارزمية لإيجاد القاسم المشترك الأكبر لرقمين. تعتمد الخوارزمية على ملاحظة أن عقدة رقمين لن تتغير إذا تمت إضافة رقم أصغر أو طرحه من رقم أكبر.

يمكن وصف خوارزمية العثور على عقد من رقمين باستخدام الطريقة الإقليدية على النحو التالي:

1. تبدأ مع اثنين من أرقام معينة.
2. تحقق مما إذا كان أحد الأرقام هو صفر. إذا كانت هذه هي الحالة ، فسيكون الرقم الآخر هو العقدة.
3. إذا لم يكن أي من الأرقام صفرا ، اطرح الرقم الأصغر من الرقم الأكبر.
4. استبدل الرقم الأكبر بالفرق الناتج.
5. كرر الخطوات من 2 إلى 4 حتى يصبح أحد الأرقام صفرا.
6. سيكون الرقم غير الصفري عقدة.

مثال:

في هذا المثال ، عقدة الرقمين 12 و 18 هي 6.

الطريقة الإقليدية القائمة على الطرح هي طريقة بسيطة وفعالة للعثور على عقد رقمين. يستخدم على نطاق واسع في مختلف المجالات مثل الحساب والتشفير والخوارزميات لإيجاد الأعداد الأولية. تستخدم إصدارات أكثر كفاءة من الطريقة الإقليدية ، مثل الخوارزمية العودية أو خوارزمية شتاين ، للعمل بأعداد كبيرة.

وصف الخوارزمية

عادة ما يتم العثور على القاسم المشترك الأكبر (غد) من رقمين باستخدام خوارزمية إقليدس. تعتمد هذه الخوارزمية على ملاحظة بسيطة: إذا كان أ و ب رقمين ، فإن العقدة الخاصة بهما تساوي عقدة الرقم أ والباقي من قسمة الرقم ب على أ.

يتم تطبيق خوارزمية إقليدس في التسلسل التالي من الخطوات:

1. يتم تضمين رقمين أ و ب.
2. تحقق مما إذا كان أ صفرا ، ثم العقدة (أ ، ب) تساوي ب. إكمال الخوارزمية.
3. خلاف ذلك ، العقدة (أ ، ب) تساوي العقدة(ب ٪ أ ، أ) ، حيث ٪ هو العامل المتبقي للقسمة.
4. نعين أ يساوي ب و ب يساوي ما تبقى من قسمة ب على أ.
5. كرر الخطوات من 2 إلى 4 حتى يصبح صفرا.

بعد اكتمال الخوارزمية ، ستكون العقدة (أ ، ب) مساوية للقيمة الأخيرة عندما أ أصبح صفرا. سيكون هذا هو القاسم المشترك الأكبر لرقمين أ و ب.

يوضح الجدول أدناه تطبيق خوارزمية إقليدس للعثور على عقدة الرقمين 18 و 24:

وبالتالي ، فإن العقدة(18 ، 24) تساوي 6.

التنفيذ العودي

العودية هي عملية استدعاء دالة نفسها. في حالة العثور على أكبر القاسم المشترك (غد) من رقمين ، العودية يمكن أن يكون حلا جيدا.

تبدو خوارزمية العثور على عقد رقمين باستخدام العودية كما يلي:

• تحقق مما إذا كان الرقم الثاني هو صفر. إذا كان الأمر كذلك ، فهذا يعني أن الرقم الأول هو عقدة الأرقام الأصلية. في هذه الحالة ، تقوم الدالة بإرجاع الرقم الأول.
• خلاف ذلك ، استدعاء الدالة بشكل متكرر ، وتمرير الرقم الأول كوسيطة أولى والباقي من قسمة الرقم الأول على الرقم الثاني كوسيطة ثانية.
• إرجاع النتيجة التي تم الحصول عليها من استدعاء دالة متكررة.

مثال على تنفيذ خوارزمية لإيجاد العقد باستخدام العودية في بايثون:

"'بايثون

(أ ، ب):

إذا ب = = 0:

العودة أ

عودة غد-ريكورسيف (ب ، أ ٪ ب)

"`

لاستدعاء الوظيفة والحصول على النتيجة ، يكفي تمرير رقمين كوسائط:

"'بايثون

النتيجة = غد_ ريكورسيف(24 ، 36)

طباعة (النتيجة) # الإخراج: 12

"`

وبالتالي ، فإن التنفيذ المتكرر لإيجاد عقد رقمين هو طريقة بسيطة وفعالة لحل هذه المشكلة.

باستخدام العودية

في بيثون ، يمكنك العثور على أكبر القاسم المشترك (عقدة) من رقمين باستخدام العودية. العودية هي عملية استدعاء دالة مرة أخرى داخل نفسها.

للعثور على عقدة رقمين باستخدام العودية ، يمكنك استخدام خوارزمية إقليدس. خوارزمية إقليدس هي كما يلي:

1. إذا كان أحد الأرقام صفرا ، فإن العقدة تساوي الرقم الآخر.
2. خلاف ذلك ، ونحن جعل استدعاء وظيفة متكررة ، ويمر الرقم الثاني والباقي من تقسيم الرقم الأول من الثانية لذلك.

لنلق نظرة على مثال الكود:

(أ ، ب):

إذا ب= = 0:

العودة أ

آخر:

عودة غد (ب ، أ ٪ ب)

في هذا المثال ، تجد وظيفة غد() أكبر القاسم المشترك من رقمين أ و ب باستخدام العودية. إذا كان أحد الأرقام صفرا ، تقوم الدالة بإرجاع رقم آخر. خلاف ذلك ، تقوم الدالة بإجراء مكالمة متكررة ، وتمرير الرقم الثاني والباقي من قسمة الرقم الأول على الرقم الثاني.

وفيما يلي مثال على استخدام وظيفة غد() :

أ = 24

ب = 18

طباعة (غد (أ ، ب))

في هذا المثال ، هناك عقدة من الأرقام 24 و 18 باستخدام وظيفة غد (). يتم عرض النتيجة على الشاشة.

ستكون نتيجة تنفيذ الكود:

6

لذلك استخدمنا العودية لإيجاد القاسم المشترك الأكبر لرقمين في بايثون.

مثال الاستخدام

للعثور على أكبر قاسم مشترك لرقمين في بايثون ، يمكنك استخدام الكود التالي:

العودة أ

1

في هذا المثال

، وظيفة غد()

يأخذ رقمين ويجد أكبر القاسم المشترك. تتوافق نتيجة الوظيفة مع القيم المتوقعة لكل حالة.