پروژه اویلر مجموعهای از مسائل برنامهنویسی هیجانانگیز است که اغلب پیشینه ریاضی دارند. این مسائل اغلب به گونهای طراحی میشوند که نیاز به توسعه الگوریتمهای پیچیده برای دستیابی به هدف در یک بازه زمانی معقول داشته باشند. امروز مسئله ۱۵: مسیرهای شبکهای را حل خواهیم کرد که میتوان آنها را با استفاده از روشهای ترکیبی ساده حل کرد.
سوال به شرح زیر است:
„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 \}.$$
این یک مسئله ترکیبی ساده است که در آن ما از مدل urn (بدون تعویض و بدون در نظر گرفتن ترتیب) استفاده می کنیم. اکنون دقیقاً به آن مسیرهایی علاقه مندیم که مشخص می کند \(R\) و \(D\) دقیقاً \(D\) همان فرکانس \(D\) . این نتیجه در تمام ترکیبات ممکن است:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
برای \(n=20\) دریافت می کنیم:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
ما می توانیم مشکل را به شبکه های غیر مربعی گسترش دهیم. راه حل زیر با استفاده از bcmath با زمان اجرا \( O(n) \) با قالب ورودی "تعداد موارد آزمایشی ، \(n_1\) \(m_1\) ...)" با استفاده از bcmath یک محاسبه را اجرا می کند:
47bb78215ee0531a787bb5034652eaf4
ضمناً ، همه مشکلات پروژه اویلر نیز می تواند به صورت آنلاین در سایت پیشنهادی HackerRank حل شود.