مشروع أويلر: مسارات شعرية

Project Euler عبارة عن سلسلة من مشكلات البرمجة المثيرة ، غالبًا ما تكون ذات خلفية رياضية. غالبًا ما يتم طرح المشكلات بطريقة تتطلب تطوير خوارزميات معقدة من أجل تحقيق الهدف في وقت معقول. نحل اليوم المشكلة 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 الموصى به.

عودة