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
Кстати , все проблемы проекта Euler также можно решить онлайн на рекомендованном сайте HackerRank .