القاسم المشترك الطبيعي (غد) من رقمين هو أكبر عدد يقسم كلا الرقمين دون بقية. هناك خوارزميات مختلفة لعقد الحوسبة ، بما في ذلك الطريقة العودية. تتيح الطريقة العودية تبسيط عملية عقد الحوسبة عن طريق تقسيم المهمة إلى مهام فرعية أبسط وأصغر.
تسمح طريقة حساب العقدة المعدلة بتحسين كفاءة الخوارزمية وتقليل عدد العمليات الحسابية. تعتمد هذه الطريقة على حقيقة أن العقدة(أ ، ب) تساوي العقدة(أ — ب ، ب) لـ أ > ب. وبالتالي ، من الممكن حساب عقدة رقمين عن طريق تقليل الرقم الأكبر بقيمة الرقم الأصغر حتى تتحقق المساواة.
تتمثل الطريقة العودية لإيجاد العقد باستخدام الطريقة المعدلة في كتابة دالة تأخذ وسيطتين-أ و ب ، وإرجاع عقدة هذه الأرقام. يتم فحص شرط المساواة في جسم الوظيفة ، وإذا تم الوفاء به ، يتم إرجاع قيمة الرقم أ أو ب. خلاف ذلك ، يتم استدعاء نفس الوظيفة مع الحجج أ — ب و ب.
مثال على وظيفة بايثون:
ديف ريكورسيف_غد (أ ، ب):
إذا أ = = ب:
العودة أ
إذا أ > ب:
عودة ريكورسيف_غد (أ-ب ، ب)
عودة ريكورسيف_غد (أ ، ب-أ)
وبالتالي ، فإن وظيفة حساب غد العودية باستخدام الطريقة المعدلة هي وسيلة فعالة لتحديد القاسم المشترك الأكبر من عددين طبيعيين.
- تنفيذ وظيفة متكررة لحساب العقد من رقمين
- وصف خوارزمية حساب العقدة
- باستخدام طريقة حساب العقدة المعدلة
- مزايا الدالة العودية على الدالة التكرارية
- مثال على رمز بايثون لحساب العقدة العودية
- اختبار وتحليل نتائج وظيفة
- سؤال وجواب
- لماذا استخدام وظيفة العودية لحساب العقد?
- ما الحجج لا تأخذ وظيفة العودية?
- كيف تعمل وظيفة العودية لعقد الحوسبة?
- كيف يمكن استخدام الطريقة المعدلة لحساب العقد?
- كيف يمكن تحسين وظيفة العودية لعقد الحوسبة?
تنفيذ وظيفة متكررة لحساب العقد من رقمين
لحساب القاسم المشترك الأكبر (غد) من رقمين ، يمكنك استخدام وظيفة متكررة. تسمح لك الطريقة العودية بتقسيم المهمة بسهولة إلى مهام فرعية أبسط ، وتجنب التعليمات البرمجية المتكررة.
لكتابة خوارزمية متكررة لحساب العقد من رقمين ، يكفي استخدام النهج التالي:
- تحقق مما إذا كان أحد الأرقام هو صفر. إذا كانت هذه هي الحالة ، فإن العقدة تساوي رقما آخر.
- خلاف ذلك ، قم بإجراء استدعاء دالة تكرارية ، وتمرير أحد الأرقام والباقي من قسمة رقم على آخر كوسيطات له.
- ستكون نتيجة الوظيفة عقدة من الأرقام الأصلية.
مثال على تنفيذ هذه الخوارزمية في جافا سكريبت:
. والنتيجة هي عقدة من الأرقام الأصلية.
في هذا المثال ، ستكون نتيجة الوظيفة هي عقدة الرقمين 12 و 18 ، أي ما يعادل 6.
وصف الخوارزمية لحساب العقدة
ويستند خوارزمية لحساب القاسم المشترك الأكبر (غد) من اثنين من الأرقام الطبيعية على استخدام وظيفة متكررة وطريقة معدلة. العقدة المكونة من رقمين هي أكبر رقم يقبل به كلا الرقمين القسمة بدون الباقي.
يتم تنفيذ خوارزمية حساب العقدة على النحو التالي:
- إذا كان كلا الرقمين متساويين ، فإن العقدة تساوي هذا الرقم وتنتهي الحسابات.
- إذا كان أحد الأرقام هو 0 ، فإن العقدة تساوي الرقم الآخر وتنتهي الحسابات.
- إذا كان أحد الأرقام زوجيا والآخر فرديا ، فإن العقدة تساوي عقدة نصف رقم زوجي (مقسوما على 2) ورقم فردي.
- إذا كان كلا الرقمين متساويين ، فإن العقدة تساوي ضعف عقدة نصف كل رقم (مقسوما على 2).
- إذا كان كلا الرقمين فرديين ، فإن العقدة تساوي عقدة الفرق بين هذه الأرقام وأكثر من الأصغر منها.
يتم تنفيذ الخوارزمية بشكل متكرر ، واستدعاء وظيفة حساب العقدة بقيم أرقام مخفضة حتى يتم استيفاء أحد شروط الخروج.
وبالتالي ، فإن وظيفة حساب العقدة العودية تجعل من الممكن العثور بكفاءة وببساطة على أكبر قاسم مشترك لرقمين طبيعيين باستخدام الطريقة المعدلة.
باستخدام طريقة حساب العقدة المعدلة
وتستند الطريقة المعدلة لحساب القاسم المشترك الأكبر (غد) من عددين طبيعيين على استخدام وظيفة متكررة. وهو يختلف عن طريقة حساب العقدة القياسية في أنه يستخدم إجراء تكراري بسيط.
لنفترض أن لدينا رقمين طبيعيين أ و ب. نريد إيجاد العقدة الخاصة بهم. للقيام بذلك ، يمكنك استخدام الخوارزمية التالية:
- نتحقق مما إذا كان أ و ب هي نفسها. إذا كانت الإجابة بنعم ، ثم العقدة (أ ، ب) = أ (أو ب)
- إذا أ > ب ، فاستبدل أ بـ أ - ب وانتقل إلى الخطوة 1. خلاف ذلك ، استبدل ب ب — أ وانتقل إلى الخطوة 1.
يمكن كتابة هذه الخوارزمية كدالة تكرارية ستطلق على نفسها حتى يتم الوصول إلى شرط الخروج.
قد تبدو الدالة العودية لحساب عقد رقمين طبيعيين باستخدام الطريقة المعدلة كما يلي:
وظيفة غد (أ ، ب) {
إذا (أ === ب) {
العودة أ;
} آخر إذا (أ > ب) {
عودة غد (أ-ب ، ب);
} آخر {
عودة غد (أ ، ب-أ);
}
}
كما يتضح من الكود ، تتحقق الوظيفة أولا من الشرط ما إذا كان الرقمان أ و ب متماثلان. إذا كان الأمر كذلك ، فإنه يرجع القيمة أ (أو ب). خلاف ذلك ، فإنه يدعو نفسه بشكل متكرر ، والانتقال إلى الخطوة التالية من الخوارزمية.
يمكن أن يكون استخدام طريقة حساب العقدة المعدلة مفيدا في الحالات التي يكون فيها من الضروري العثور على عقدة بأعداد كبيرة ، حيث يوفر الوقت والذاكرة مقارنة بطريقة حساب العقدة القياسية.
مزايا الدالة العودية على الدالة التكرارية
وظيفة متكررة لحساب القاسم المشترك الأكبر (غد) من اثنين من الأرقام الطبيعية لديها العديد من المزايا على وظيفة تكرارية:
- البساطة والوضوح من التعليمات البرمجية. عادة ما تتم كتابة الوظيفة العودية في شكل أبسط وأكثر إيجازا ، مما يسهل فهمها وصيانتها.
- المرونة والتنوع. يمكن تطبيق الخوارزمية العودية على مهام مختلفة دون الحاجة إلى تغيير هيكلها. وبالتالي ، يمكن استخدامه في سياقات أخرى ، ليس فقط لعقد الحوسبة.
- القدرة على العمل بأعداد كبيرة. تسمح لك الخوارزمية العودية بالعمل بفعالية مع الأرقام التي لا تتناسب مع أبعاد أنواع البيانات الرقمية في لغة البرمجة.
- من السهل التصحيح. إذا كانت هناك أخطاء في الخوارزمية العودية ، فمن الأسهل تصحيحها ، حيث تحدث كل خطوة من الخوارزمية في وظيفة منفصلة تسمى ، مما يبسط عملية تحديد النقاط الإشكالية.
ومع ذلك ، يجب أن يؤخذ في الاعتبار أن الوظيفة العودية قد تكون أقل كفاءة في الوقت وتتطلب الذاكرة بسبب استخدام مجموعة من استدعاءات الوظائف. أيضا ، إذا كان التنفيذ غير صحيح أو كانت قيم المعلمات كبيرة بشكل غير كاف ، يمكن أن تؤدي الوظيفة العودية إلى تجاوز سعة المكدس وتسبب خطأ "تجاوز سعة المكدس". لذلك ، قبل استخدام العودية ، من الضروري تقييم تكاليف الذاكرة والأداء المحتملة بعناية.
مثال على رمز بايثون لحساب العقدة العودية
وفيما يلي مثال على رمز بيثون تنفيذ وظيفة لحساب متكرر العقد من رقمين طبيعيين باستخدام طريقة معدلة:
(أ ، ب):
إذا ب= = 0:
العودة أ
آخر:
عودة غد-ريكورسيف (ب ، أ ٪ ب)
# مثال على استخدام الوظيفة
عدد1 = 24
عدد2 = 36
النتيجة = غد_ ريكورسيف (عدد 1 ، عدد 2)
طباعة (و " عقدة الأرقام {رقم 1} و {رقم 2} تساوي {نتيجة}")
في هذا المثال ، تأخذ دالة غد-ريكورسيف معلمتين-الأرقام أ و ب. تتحقق الدالة مما إذا كان الرقم ب صفرا. إذا كانت متساوية ، فإن الدالة ترجع الرقم أ ، لأن أ و ب هي بالفعل قواسم للرقم أ والعقدة تساوي أ.
إذا كان الرقم ب ليس صفرا ، فإن الوظيفة تستدعي نفسها بشكل متكرر ، وتمرر كوسائط قيم ب والباقي من قسمة أ على ب. يسمح لك هذا بتقليل قيم الأرقام تدريجيا حتى يصبح أحدها صفرا.
يوضح مثال على استخدام الوظيفة كيفية حساب العقدة لرقمين معينين وعرضها على الشاشة.
اختبار وتحليل نتائج وظيفة
لاختبار الوظيفة العودية لحساب عقد رقمين طبيعيين باستخدام الطريقة المعدلة ، يمكن استخدام المجموعة التالية من بيانات الاختبار:
بيانات الاختبار: الأرقام أ = 12 و ب = 18.
النتيجة المتوقعة: العقدة (أ ، ب) = 6.
التحليل: الرقمان 12 و 18 لهما قاسم مشترك 6 ، وهو العقدة الخاصة بهما. يجب أن تقوم الوظيفة بحساب هذه القيمة وإرجاعها بشكل صحيح.
بيانات الاختبار: الأرقام أ = 8 و ب = 12.
النتيجة المتوقعة: العقدة (أ ، ب) = 4.
التحليل: الرقمان 8 و 12 لهما قاسم مشترك 4 ، وهو العقدة الخاصة بهما. يجب أن تقوم الوظيفة بحساب هذه القيمة وإرجاعها بشكل صحيح.
بيانات الاختبار: الأرقام أ = 17 و ب = 29.
النتيجة المتوقعة: العقدة (أ ، ب) = 1.
التحليل: الرقمان 17 و 29 هما عددان أوليان وليس لهما قواسم مشتركة باستثناء 1 ، وهي العقدة الخاصة بهما. يجب أن تقوم الوظيفة بحساب هذه القيمة وإرجاعها بشكل صحيح.
بعد اختبار وتحليل نتائج الوظيفة ، من الممكن استنتاج أنها صحيحة وفعالة. إذا كانت الوظيفة تعمل بشكل صحيح وتعيد النتائج المتوقعة لجميع الاختبارات ، فيمكن القول إنها تؤدي مهمة حساب عقد رقمين طبيعيين باستخدام الطريقة المعدلة.
بالإضافة إلى ذلك ، من الممكن تحليل وقت تنفيذ الوظيفة للمدخلات المختلفة. سيساعدك هذا على تقييم فعالية الوظيفة وتحديد مدى سرعة تنفيذها. يمكن قياس وقت تنفيذ الوظيفة باستخدام أداة قياس أداء خاصة.
وبالتالي ، يعد اختبار وتحليل نتائج الوظيفة جزءا مهما من تطوير البرامج ويسمح لك بالتحقق من صحة الوظيفة وفعاليتها.
سؤال وجواب
لماذا استخدام وظيفة العودية لحساب العقد?
الدالة العودية هي إحدى طرق حساب العقدة (أكبر قاسم مشترك) لرقمين. يمكن أن يكون مفيدا في حل المشكلات المختلفة ، خاصة عندما يكون عدد التكرارات المطلوبة لحساب العقدة غير معروف مسبقا.
ما الحجج لا تأخذ وظيفة العودية?
تأخذ الدالة العودية وسيطتين-رقمان طبيعيان تحتاج إلى العثور على عقدة لهما.
كيف تعمل وظيفة العودية لعقد الحوسبة?
تستخدم الدالة العودية طريقة القسمة المتسلسلة لحساب العقدة. إذا كان أحد الأرقام صفرا ، فإن العقدة تساوي الرقم الآخر. خلاف ذلك ، تستدعي الوظيفة نفسها ، وتمرير ما تبقى من قسمة الرقم الأول على الرقم الثاني والرقم الثاني نفسه كوسيطات.
كيف يمكن استخدام الطريقة المعدلة لحساب العقد?
تستخدم الطريقة المعدلة دالة تكرارية لحساب العقدة. يطلق على نفسه حتى يصبح أحد الأرقام صفرا. ثم يقوم بإرجاع رقم آخر ، وهو العقدة للأرقام الأصلية.
كيف يمكن تحسين وظيفة العودية لعقد الحوسبة?
يمكن تحسين الوظيفة العودية لعقد الحوسبة باستخدام خوارزمية إقليدس ، مما يقلل من عدد المكالمات العودية. بدلا من قسمة الأرقام تماما ، يمكنك استخدام عملية إيجاد باقي القسمة. سيساعد هذا في تسريع العمليات الحسابية.