- قيد الملء
- يُقرأ منها
- الإجابة
فيبوناتشي بالبرمجة الديناميكية
أعداد فيبوناتشي هي المثال الأول الكلاسيكي على البرمجة الديناميكية. فالعودية البسيطة تطلب الحدود نفسها مرة بعد مرة، لكن مع جدول يتذكّر كل حد لا يزداد العمل إلا بزيادة n. اختر حدًا، واختر من الأسفل إلى الأعلى أو من الأعلى إلى الأسفل، ثم تقدّم خطوة بخطوة لترى كل خلية تُملأ مرة واحدة. اضغط «تشغيل» لمشاهدة الجدول وهو يمتلئ، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. اختر n، أي الحد المطلوب حسابه، والطريقة: الطريقة من الأسفل إلى الأعلى تملأ الجدول من اليسار، والطريقة من الأعلى إلى الأسفل تحتفظ بالعودية لكنها تبحث في الجدول أولًا، ويصبح الصف أسفل الجدول حينها مكدس الاستدعاءات المفتوحة. «مثال جديد» يختار قيمة أخرى لـ n. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.
كيف يعمل
- اكتب في خانة «الحد n» الحد المطلوب حسابه، واختر «من الأسفل إلى الأعلى» أو «من الأعلى إلى الأسفل».
- اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع.
- راقب كل خلية وهي تقرأ الخليتين السابقتين لها. في الطريقة من الأعلى إلى الأسفل، الصف أسفل الجدول هو مكدس الاستدعاءات المفتوحة.
من الأسفل إلى الأعلى ومن الأعلى إلى الأسفل
الطريقة من الأسفل إلى الأعلى، وتُسمى أيضًا الجدولة، تبدأ بـ F(0) = 0 وF(1) = 1 وتملأ الجدول من اليسار إلى اليمين: كل خلية جديدة هي مجموع الخليتين السابقتين لها. أما الطريقة من الأعلى إلى الأسفل، وتُسمى أيضًا التذكّر (memoization)، فتحتفظ بالتعريف العودي: لإيجاد F(n) اطلب F(n − 1) وF(n − 2). والفرق عن العودية البسيطة أن كل استدعاء يبحث في الجدول أولًا، ولا يحسب الحد إلا إذا كانت خليته لا تزال فارغة. كلتا الطريقتين تملأ كل خلية مرة واحدة وتستخدم n − 1 من عمليات الجمع.
لماذا العودية البسيطة بطيئة إلى هذا الحد
من دون جدول، يستدعي F(n) كلًّا من F(n − 1) وF(n − 2)، وكلاهما يستدعي F(n − 3)، وهكذا: تشكّل الاستدعاءات شجرة تظهر فيها الحدود نفسها مرارًا وتكرارًا. عدد الاستدعاءات هو 2·F(n + 1) − 1، وهو ينمو بسرعة نمو أعداد فيبوناتشي نفسها: 177 استدعاءً لـ F(10)، و21,891 لـ F(20)، وأكثر من 331 مليونًا لـ F(40). والمسائل الجزئية المتداخلة مثل هذه هي بالضبط ما وُجدت البرمجة الديناميكية من أجله.
الأسئلة المتداولة
ما البرمجة الديناميكية؟
طريقة لحل مسألة بتقسيمها إلى مسائل أصغر متداخلة، وحل كل مسألة أصغر مرة واحدة، وحفظ إجابتها في جدول. وأعداد فيبوناتشي هي أبسط مثال: كل حد يُبنى من الحدين السابقين له.
ما الفرق بين التذكّر والجدولة؟
التذكّر يحتفظ بالشيفرة العودية ويخزّن كل إجابة أول مرة تُحسب فيها، فتكتفي الاستدعاءات اللاحقة بقراءتها. أما الجدولة فتملأ الجدول بترتيب يضمن أن كل إجابة تحتاجها الخلية موجودة مسبقًا. كلتاهما تُجري عمليات الجمع نفسها؛ الجدولة تستغني عن مكدس الاستدعاءات، والتذكّر لا يحسب إلا الخلايا المطلوبة فعلًا.
كم عملية جمع يحتاج F(n)؟
n − 1 مع الجدول: عملية لكل حد من F(2) إلى F(n). ولا يُقرأ في أي وقت إلا آخر حدين، لذا يمكن للبرنامج أيضًا أن يحتفظ بعددين فقط بدلًا من الجدول كله.
لماذا يتوقف التطبيق عند n = 40؟
لا يزال F(40) = 102,334,155 يتسع على الشاشة بسهولة، وكانت العودية البسيطة ستحتاج من أجله إلى 331,160,281 استدعاءً. والحدود الأكبر تنمو بسرعة: F(78) هو أكبر حد يحفظه عدد JavaScript بدقة.
هل يُرسَل أي شيء إلى أي مكان؟
لا. كل شيء يُحسب في متصفحك، وتبقى آخر إعداداتك في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر