فهم العودية والصيغة العودية



جرب أداة القضاء على المشاكل

تكرار

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



0 ، 1 ، 1 ، 2 ، 3 ، 5 ، 8 ، 13 ، 21 ، 34 ، 55 ، 89



خطوات التكرار

يمكن كتابة معادلة فيبوناتشي كـ ،



و (ن) = و (ن - 1) + و (ن - 2)
فيبوناتشي (0) = 0
فيبوناتشي (1) = 1
فيبوناتشي (2) = فيبوناتشي (1) + فيبوناتشي (0) = 1 + 0 = 1
فيبوناتشي (3) = فيبوناتشي (2) + فيبوناتشي (1) = 1 + 1 = 2
فيبوناتشي (4) = فيبوناتشي (3) + فيبوناتشي (2) = 2 + 1 = 3
فيبوناتشي (5) = فيبوناتشي (4) + فيبوناتشي (3) = 3 + 2 = 5
فيبوناتشي (6) = فيبوناتشي (5) + فيبوناتشي (4) = 5 + 3 = 8

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

فيبوناتشي



العودية

في كل مرة نحصل فيها على رقم فيبوناتشي جديد (رقم نون) يكون هذا الرقم في الواقع (ن - 1) رقمًا عندما نجد (ن + 1) فيبوناتشي التالي فيبوناتشي. كما نرى خطوات التكرار المذكورة أعلاه: إذا كان n = 2 إذن
فيبوناتشي (2) = فيبوناتشي (2-1) + فيبوناتشي (2-2) = فيبوناتشي (1) + فيبوناتشي (0) = 1 + 0 = 1

الآن ، نريد توليد فيبوناتشي (3) ، أي ن = 3.

فيبوناتشي (3) = فيبوناتشي (3-1) + فيبوناتشي (3-2) = فيبوناتشي (2) + فيبوناتشي (1) = 1 + 1 = 2
وهذا يعني أنه في كل مرة تزيد n من قيمة الألياف الحالية (n - 1) th و (n - 2) تزيد أيضًا. ولكن من المتعب تتبع (n - 1) th و (n - 2) th فيبوناتشي لكل n. ماذا عن كتابة طريقة تدعو نفسها لتكرار مهمة التكرار من تلقاء نفسها؟

الطريقة التي تستدعي نفسها تسمى الطريقة العودية. يجب أن يكون للطريقة العودية حالة أساسية حيث يتوقف البرنامج عن استدعاء نفسه. الحالة الأساسية لسلسلة فيبوناتشي هي فيبوناتشي (0) = 0 وفيبوناتشي (1) = 1. وإلا فإن طريقة فيبوناتشي تطلق على نفسها مرتين - فيبوناتشي (ن - 1) وفيبوناتشي (ن - 2). ثم يضيفها للحصول على فيبوناتشي (ن). يمكن كتابة طريقة تكرارية لإيجاد فيبوناتشي رقم -

فيبوناكسي 2

إذا نظرنا بعناية ، فإن العودية تتبع خاصية المكدس. يحل مشاكل فرعية أصغر للحصول على حل لمشكلة ما. بالنسبة إلى n> 1 ، يتم تنفيذ السطر الأخير. لذلك ، إذا كان n = 6 ، تستدعي الدالة Fibonacci وتضيفها (6 - 1) و fibonacci (6 - 2). فيبوناتشي (6 - 1) أو فيبوناتشي (5) يدعو ويضيف فيبوناتشي (5 - 1) وفيبوناتشي (5 - 2). تستمر هذه العودية حتى تصل القيمة 6 إلى قيمة الحالة الأساسية وهي فيبوناتشي (0) = 0 أو فيبوناتشي (1) = 1. بمجرد أن تصل إلى الحالة الأساسية ، تضيف قيمتين أساسيتين وترتفع حتى تحصل على قيمة فيبوناتشي ( 6). يوجد أدناه تمثيل شجرة العودية.

شجرة العودية

شجرة العودية

كما نرى ، كيف يمكن أن تكون العودية قوية. فقط سطر واحد من الكود يصنع الشجرة أعلاه (السطر الأخير من الكود أعلاه بما في ذلك الحالات الأساسية). يحافظ العودية على مكدس ويذهب إلى أعمق حتى يصل إلى الحالة الأساسية. البرمجة الديناميكية (DP): التكرار سهل الفهم والتشفير ولكنه قد يكون مكلفًا من حيث الوقت والذاكرة. ألق نظرة على شجرة العودية أدناه. الشجرة الفرعية اليسرى التي تبدأ بـ fib (4) والشجرة الفرعية اليمنى التي تبدأ بـ fib (4) متطابقة تمامًا. يولدون نفس النتيجة وهي 3 لكنهم يقومون بنفس المهمة مرتين. إذا كان n عددًا كبيرًا (على سبيل المثال: 500000) ، فيمكن أن تجعل العودية البرنامج بطيئًا للغاية حيث قد يستدعي نفس المهمة الفرعية عدة مرات.

العودية شجرة محاطة بدائرة

العودية شجرة محاطة بدائرة

لتجنب هذه المشكلة يمكن استخدام البرمجة الديناميكية. في البرمجة الديناميكية ، يمكننا استخدام مهمة فرعية تم حلها مسبقًا لحل مهمة مستقبلية من نفس النوع. هذه طريقة لتقليل مهمة حل المشكلة الأصلية. لنحصل على مصفوفة fib [] حيث نقوم بتخزين حلول المهام الفرعية التي تم حلها مسبقًا. نحن نعلم بالفعل أن fib [0] = 0 و fib [1] = 1. دعونا نخزن هاتين القيمتين. الآن ، ما هي قيمة Fib [2]؟ نظرًا لأنه تم تخزين fib [0] = 0 و fib [1] = 1 بالفعل ، علينا فقط أن نقول fib [2] = fib [1] + fib [0] وهذا كل شيء. يمكننا توليد فيب [3] ، فيب [4] ، فيب [5] ، …… ، فيب [ن] بنفس الطريقة. يتم استدعاء المهام الفرعية التي تم حلها مسبقًا للحصول على المهمة الفرعية التالية حتى لا يتم حل المهمة الأصلية ، وبالتالي يقلل من الحسابات الزائدة عن الحاجة.

فيبوناتشي 3

3 دقائق للقراءة