العودية هي أداة مهمة في البرمجة. تسمح لك الخوارزميات العودية بحل المشكلات المعقدة عن طريق تقسيمها إلى مهام فرعية أبسط. أحد الأمثلة على العودية هو الخوارزمية لإيجاد مجموع الأرقام عند استدعاء دالة الفورمولا 1.
ال و1 الخوارزمية هي دالة تأخذ رقم الإدخال ن ويحسب مجموع الأرقام من 1 إلى ن. خصوصية الخوارزمية هي أن الوظيفة تستدعي نفسها ، وتمرير ن - 1 كوسيطة حتى ن يصبح 1. في هذه الحالة ، ترجع الدالة 1 ، وهي الحالة الأساسية.
يمكن تمثيل عملية حساب مجموع الأرقام عند استدعاء دالة و1 على النحو التالي: إذا احتجنا إلى إيجاد مجموع الأرقام من 1 إلى 5 ، فإننا نسمي دالة و1(5) ، والتي بدورها تستدعي دالة و1(4) ، ثم و1(3) ، و1(2) وأخيرا و1(1). عندما يتم استدعاء الدالة إف 1 (1) ، ستعود 1 ، والتي ستكون نتيجة لجميع المكالمات السابقة.
تعد الخوارزمية العودية للعثور على مجموع الأرقام عند الاتصال بوظيفة الفورمولا 1 طريقة بسيطة وأنيقة لحل هذه المشكلة. في الوقت نفسه ، من المهم أن تضع في اعتبارك أن الخوارزميات العودية يمكن أن تكون أقل كفاءة من الخوارزميات التكرارية ، خاصة عند العمل مع مجموعات البيانات الكبيرة. لذلك ، عند اختيار خوارزمية ، من الضروري مراعاة تفاصيل المهمة ومتطلبات الأداء.
- الخوارزمية العودية: إيجاد مجموع الأرقام
- تنفيذ الخوارزمية في وظيفة الفورمولا 1
- مبدأ تشغيل الخوارزمية العودية
- مثال على استخدام خوارزمية متكررة للعثور على مجموع الأرقام
- سؤال وجواب
- كيف خوارزمية متكررة لإيجاد مجموع الأرقام العمل عند استدعاء وظيفة و?
- كيف الخوارزمية العودية لإيجاد مجموع الأرقام عند استدعاء وظيفة و تأخذ في الاعتبار إمكانية الأرقام السالبة?
- يمكن لخوارزمية متكررة للعثور على مجموع الأرقام عند استدعاء وظيفة و يؤدي إلى تجاوز الذاكرة?
خوارزمية العودية: إيجاد مجموع الأرقام
الخوارزمية العودية هي إحدى طرق حل مشكلة إيجاد مجموع الأرقام. لأنه يقوم على مبدأ استدعاء وظيفة في حد ذاته.
لنفكر في خوارزمية تكرارية لإيجاد مجموع الأرقام عند استدعاء دالة الفورمولا 1. بيانات الإدخال عبارة عن سلسلة من الأرقام س 1, س 2,..., شن ، أين ن هو عدد الأرقام.
تتكون الخوارزمية من الخطوات التالية:
- إذا كان عدد الأرقام هو 1 ، فإننا نعيد هذا الرقم نتيجة لذلك.
- خلاف ذلك ، والعثور على مجموع أول رقمين س1 و س2 والكتابة إلى المتغير س.
- ونحن ندعو وظيفة و1 مع قائمة من الأرقام, بدءا من الرقم الثاني س 2,...، شين وتمرير القيمة س كحجة لذلك.
- استدعاء بشكل متكرر وظيفة و1 حتى يكون هناك 1 عدد اليسار في القائمة.
دعنا نشرح الخوارزمية باستخدام مثال سلسلة من الأرقام: 5 ، 3 ، 8 ، 2. أولا ، نجد مجموع الأرقام 5 و 3 ، نحصل على 8. ثم نسمي الدالة و 1 للحصول على قائمة بالأرقام 8 و 8 و 2 ونمررها القيمة 8. بعد ذلك ، نجد مجموع الأرقام 8 و 8 ، والحصول على 16 ، واستدعاء وظيفة و1 لقائمة الأرقام 16 ، 2 ، ويمر عليه قيمة 16. وأخيرا ، نجد مجموع الأرقام 16 و 2 ، نحصل على 18. نتيجة لذلك ، تقوم دالة إف 1 بإرجاع القيمة 18.
وهكذا ، تجد الخوارزمية العودية مجموع الأرقام باستخدام مبدأ استدعاء الوظيفة نفسها. يتيح لك ذلك حل المشكلات المتعلقة بمعالجة تسلسل الأرقام بشكل ملائم وفعال.
تنفيذ الخوارزمية في وظيفة الفورمولا 1
يمكن تنفيذ خوارزمية العثور على مجموع الأرقام عند استدعاء دالة الفورمولا 1 باستخدام العودية. تفترض الخوارزمية العودية استدعاء دالة من نفسها حتى يتم الوصول إلى شرط إكمال معين.
مثال على تنفيذ الخوارزمية في الوظيفة و 1:
الوظيفة واو 1 (ن) {// حالة قاعدة
إذا (ن === 1) {
عودة 1;
}
// حالة متكررة
عودة ن + فورمولا 1 (ن-1);
}
في هذا المثال ، الوظيفة و1 يأخذ الوسيطة ن ، وهو الرقم الذي يجب جمع الأرقام إليه. تبدأ الخوارزمية بالحالة الأساسية عندما ن هو 1. في هذه الحالة ، ترجع الدالة 1 ، وهي القيمة الأساسية لمجموع الأرقام.
في الحالة العودية ، تستدعي الوظيفة نفسها بالحجة ن - 1 ويضيف النتيجة بالقيمة الحالية لـ ن.يتيح لك هذا الأسلوب جمع الأرقام باستمرار من ن إلى 1.
مثال على استخدام الوظيفة:
النتيجة الثابتة = الفورمولا 1 (5);وحدة التحكم.سجل (نتيجة) ؛ / / النواتج 15
في هذا المثال ، يتم استدعاء دالة و 1 بالوسيطة 5 ، مما يعني أنك بحاجة إلى إضافة الأرقام من 5 إلى 1. ستكون النتيجة الرقم 15.
مبدأ تشغيل الخوارزمية العودية
الخوارزمية العودية هي خوارزمية تستدعي نفسها في وقت التشغيل. يستخدم على نطاق واسع في البرمجة لحل المهام بناء على الخطوات المتكررة أو المهام الفرعية.
يمكن تفسير مبدأ تشغيل الخوارزمية العودية على النحو التالي:
- في بداية تنفيذ الخوارزمية ، يتم فحص الشرط الأساسي. إذا تم استيفاء الشرط الأساسي ، تقوم الخوارزمية بإرجاع قيمة معينة وتنتهي.
- إذا لم يتم استيفاء الشرط الأساسي ، فإن الخوارزمية تستدعي نفسها بالوسيطات المعدلة أو بيانات الإدخال. هذا يؤدي إلى التنفيذ المتكرر للخوارزمية في سياق جديد.
- قد يؤدي التنفيذ المتكرر للخوارزمية إلى مكالمات ذاتية جديدة حتى يتم الوصول إلى الحالة الأساسية وتكتمل الخوارزمية.
- تضيف كل مكالمة إلى الخوارزمية إطارا جديدا إلى مكدس الاستدعاءات ، والذي يحتوي على معلومات حول الحالة الحالية لتنفيذ الخوارزمية.
- في نهاية الخوارزمية ، يتم حذف كل إطار من مكدس الاستدعاءات بدوره ، ويعود تنفيذ البرنامج إلى المكالمة السابقة.
تسمح لك الخوارزمية العودية بحل المشكلات المعقدة عن طريق تقسيمها إلى مهام فرعية أبسط. ومع ذلك ، يمكن أن يؤدي التنفيذ غير الصحيح للخوارزمية العودية إلى العودية اللانهائية أو الإنهاء مع وجود خطأ بسبب موارد الذاكرة المحدودة أو مكدس الاستدعاءات.
مثال على استخدام خوارزمية متكررة للعثور على مجموع الأرقام
الخوارزمية العودية هي طريقة لحل مشكلة عن طريق استدعاء الوظيفة نفسها بالتتابع. يمكن تطبيقه في مختلف المجالات ، بما في ذلك الرياضيات والبرمجة. أحد الأمثلة على استخدام خوارزمية تكرارية هو إيجاد مجموع الأرقام.
لنفترض أن لدينا سلسلة من الأرقام [1, 2, 3, 4, 5], ونحن نريد أن نجد مجموعها. يمكننا كتابة دالة تكرارية تسمي نفسها حتى تصل إلى حالة النهاية (في هذه الحالة ، حتى ينتهي التسلسل).
مثال على خوارزمية متكررة لإيجاد مجموع الأرقام:
- إعلان وظيفة و مع المعلمة ن (سلسلة من الأرقام) وعداد المجموع
- نتحقق من الحالة الأساسية: إذا كان التسلسل فارغا (ن. الطول == 0) ، فإننا نعيد المجموع
- خلاف ذلك ، أضف العنصر الأول من التسلسل إلى المجموع واستدعاء الوظيفة و بشكل متكرر للجزء المتبقي من التسلسل (ن. شريحة(1)) والمبلغ الحالي
- يتم إرجاع المبلغ الناتج نتيجة للدالة و
وظيفة و (ن ، مجموع) {
// حالة قاعدة
إذا (ن. الطول = = 0) {
مبلغ الإرجاع;
}
// دعوة متكررة
العودة و (ن. شريحة (1) ، مجموع + ن [0]);
}
// مثال الاستخدام
تسلسل فار= [1, 2, 3, 4, 5];
مجموع فار = و (تسلسل ، 0);
وحدة التحكم.سجل (مجموع) ؛ / / النواتج 15
في هذا المثال ، نقوم بتمرير سلسلة من الأرقام [1, 2, 3, 4, 5] والقيمة الأولية لمجموع 0 من وظيفة و. بعد استدعاءات الدالة العودية ، سيتم إرجاع مجموع جميع الأرقام في التسلسل وتخزينها في متغير المجموع.
يسمح لنا استخدام خوارزمية تكرارية بحل هذه المشكلة بأناقة دون استخدام الحلقات والمتغيرات المؤقتة.
سؤال وجواب
كيف الخوارزمية العودية لإيجاد مجموع الأرقام عند استدعاء وظيفة و العمل?
الخوارزمية العودية لإيجاد مجموع الأرقام عند استدعاء الدالة و يعمل على النحو التالي: الدالة و يأخذ رقم الإدخال ن. إذا ن هو 1 ، ترجع الدالة 1. خلاف ذلك ، فإن وظيفة و يدعو نفسه مع الوسيطة ن - 1 ويضيف ن إلى النتيجة. يحدث هذا حتى الحجة ن يصبح 1. ثم يتم إضافة جميع النتائج ويتم إرجاع مجموع الأرقام.
كيف الخوارزمية العودية لإيجاد مجموع الأرقام عند استدعاء وظيفة و تأخذ في الاعتبار إمكانية الأرقام السالبة?
تم تصميم الخوارزمية العودية لإيجاد مجموع الأرقام عند استدعاء الدالة و للعثور على مجموع الأرقام الموجبة. إذا كان من الضروري مراعاة إمكانية الأرقام السالبة ، فمن الضروري إجراء التغييرات المناسبة على رمز الوظيفة و بحيث تعالج القيم السالبة بشكل صحيح.
يمكن لخوارزمية متكررة للعثور على مجموع الأرقام عند استدعاء وظيفة و يؤدي إلى تجاوز الذاكرة?
من حيث المبدأ ، يمكن أن تؤدي الخوارزمية العودية لإيجاد مجموع الأرقام عند استدعاء الوظيفة و إلى تجاوز سعة الذاكرة في الحالة التي يكون فيها عمق العودية كبيرا جدا ويحتاج إلى تخزين عدد كبير من النتائج الوسيطة. ومع ذلك ، إذا تم تنفيذ الخوارزمية بشكل صحيح وتم استخدام العودية المحسنة للذيل ، فسيكون احتمال تجاوز سعة الذاكرة أقل.