Proyecto Euler: caminos de celosía

El Proyecto Euler es una serie de interesantes problemas de programación, a menudo con antecedentes matemáticos. Los problemas a menudo se plantean de tal manera que es necesario desarrollar algoritmos sofisticados para lograr el objetivo en un tiempo razonable. Hoy resolvemos el problema 15: Caminos de celosía , para el cual puedes encontrar la solución con medios combinatorios simples.


La pregunta es la siguiente:

„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?“

El problema también se puede formular de manera diferente: lo que se necesita es el poder del subconjunto de todos los caminos

$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$

Este es un problema combinatorio simple en el que usamos el modelo de urna (sin reemplazar y sin considerar el orden). Ahora estamos interesados ​​precisamente en aquellos caminos para los que se sostiene que \(R\) y \(D\) exactamente con la misma frecuencia. Esto da como resultado todas las combinaciones posibles:

$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$

Para \(n=20\) obtenemos:

$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$

Podemos extender el problema a las cuadrículas no cuadradas. La siguiente solución implementa un cálculo en PHP con la ayuda de bcmath con un tiempo de ejecución de \( O(n) \) con el formato de entrada "Número de casos de prueba, \(n_1\) \(m_1\) , ...":

47bb78215ee0531a787bb5034652eaf4

Por cierto, todos los problemas del Proyecto Euler también se pueden resolver en línea en el sitio recomendado de HackerRank .

Atrás