الدورة
البرمجة الديناميكية والتحسين دورة برمجة متقدمة في سبعة دروس، بعد دورة الاستدعاء الذاتي والتراجع. كل درس بـPython بسيطة على لوحة Pi، مع بناء المعرض ذي LED اثنين ووحدة إشارة المرور حيث يجب أن يضيء شيء ما. كل خطوة تُفحص مقابل ما تطبعه لوحة Pi أو ما تفعله أطرافها، وكل رقم في الدروس رقم يطبعه البرنامج فعلًا.
- Overlapping subproblems: a 16-rung docking ladder climbed 1, 2 or 3 rungs at a time. The slow recursion makes 37,921 calls and works out rung 2 3,136 times; a memo cuts it to 49 calls, a table fills it bottom up, and three rolling numbers climb 1000 rungs.
- Coin change: thruster burns of 9, 6, 5 and 1 m/s. Greedy uses three burns for 11 m/s where DP finds two (5 and 6), a pick table says which, a second table counts the 6 mixes, and reachability lists the speeds 4 and 7 m/s burns can never make.
- حقيبة الظهر: 10 kg من حمولة صواريخ لأقصى قدر من العلم. تعداد شامل على 256 حمولة، وجدول حقيبة الظهر 0/1، وسير الحمولة رجوعًا، ونسخة الصف الواحد مع خطأ الاتجاه الأمامي الشهير، و30 صندوقًا تُحلّ في 3,030 خانة.
- مسافة التحرير: أوامر مجسّات مشوّشة. لماذا يفشل عدّ المواضع، وجدول Levenshtein مطبوعًا كاملًا، وسير التحريرات رجوعًا، وسطر أوامر يجيب: "هل تعني DEPLOY؟"
- الجشع مقابل البرمجة الديناميكية: مرور الأقمار الصناعية بالانتهاء الأبكر (صحيح إثباتيًا) مقابل الأقصر أولًا (خطأ)، وقود مقسّم مقابل خزانات كاملة، وفحص أنظمة العملات التي ينجح معها الجشع.
- الجدولة: مرورات تحمل كميات بيانات مختلفة. الجشع يحصل على 105 MB، وبرمجة ديناميكية مع
bisectتحصل على 120، والجدول يُسار رجوعًا ويُعرض على LED الأحمر، وخط مسح يعدّ الهوائيات. - مشروع: مخطط مسارات: الخاتمة.
الخاتمة
مخطط لعبارات بين ثماني محطات فضائية. أقصر الأزمنة تأتي من برمجة ديناميكية بترتيب المحطات (الخريطة تطير إلى الخارج فقط، فهي رسم بياني موجّه بلا دورات): من الأرض إلى Titan في 45 ساعة. يُستخرج المسار رجوعًا من came_from، وجدول ثانٍ يجيب عن أفضل مسار بأقصى k مراحل (دورات Bellman-Ford، 49 ساعة في أربع مراحل)، وكشك يستقبل وجهة عبر الشاشة التسلسلية ويضيء أضواء المرور: أخضر لمسار موجود، وأحمر لمحطة غير موجودة.
ما يفعله محرك Pi بشكل مختلف
يعمل Pi على MicroPython 1.29 وليس CPython:
- لا يوجد numpy، لذا فكل جدول قائمة أو قائمة من قوائم، وهكذا تُدرَّس البرمجة الديناميكية على أي حال.
- القواميس لا تحفظ ترتيب إدخال المفاتيح. المخطط يقرأ قواميسه بالمفتاح فقط، وكل ما يُطبع يأتي من قوائم.
- الاستدعاء الذاتي يتوقف قرب 1,000 استدعاء، لذا لا تستطيع ذاكرة مؤقتة من الأعلى إلى الأسفل صعود سلّم من 1000 درجة. تستخدم الدورة ذلك لتوضيح لماذا تهم الجداول من الأسفل إلى الأعلى.
str.rjustمفقودة، لذا يحشو جدول مسافة التحرير الأرقام بـ"%2d" % v. وbisectوfunctoolsوالأعداد الصحيحة الكبيرة تعمل كما في CPython.