مشروع أويلر عبارة عن سلسلة من مسائل البرمجة الشيقة، والتي غالبًا ما تستند إلى خلفية رياضية. تُصمَّم هذه المسائل عادةً بحيث تتطلب تطوير خوارزميات متطورة لتحقيق الهدف ضمن إطار زمني معقول. سنحل اليوم المسألة رقم 15: مسارات الشبكة ، والتي يمكن حلها باستخدام طرق توافقية بسيطة.
السؤال هو على النحو التالي:
„Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid?“
يمكن أيضًا صياغة المشكلة بشكل مختلف: ما نحتاج إليه هو قوة المجموعة الفرعية لجميع المسارات
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
هذه مشكلة اندماجية بسيطة نستخدم فيها نموذج الجرار (بدون استبدال ودون النظر في الترتيب). نحن مهتمون الآن على وجه التحديد بتلك المسارات التي تؤكد أن \(R\) و \(D\) تحدثان بنفس التردد تمامًا. ينتج عن هذا كل المجموعات الممكنة:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
لـ \(n=20\) نحصل عليها:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
يمكننا توسيع المشكلة إلى شبكات غير مربعة. يقوم الحل التالي بتنفيذ عملية حسابية في PHP بمساعدة bcmath بوقت تشغيل \( O(n) \) بتنسيق الإدخال "عدد حالات الاختبار ، \(n_1\) \(m_1\) ، ...":
47bb78215ee0531a787bb5034652eaf4
بالمناسبة ، يمكن أيضًا حل جميع مشكلات مشروع أويلر عبر الإنترنت على موقع HackerRank الموصى به.