Projekt Euler er en række spændende programmeringsproblemer, ofte med en matematisk baggrund. Problemerne er ofte designet til at kræve udvikling af sofistikerede algoritmer for at nå målet inden for en rimelig tidsramme. I dag løser vi problem 15: Gitterbaner , som kan løses ved hjælp af simple kombinatoriske metoder.
Spørgsmålet er som følger:
„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?“
Problemet kan også formuleres forskelligt: Det, der er nødvendigt, er kraften i delmængden af alle stier
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Vi har her at gøre med et simpelt kombinatorisk problem, hvor vi bruger urnemodellen (uden at udskifte og uden at være opmærksom på ordren). Vi er nu interesseret i netop de stier, for hvilke det fastslås, at \(R\) og \(D\) nøjagtig samme frekvens. Dette resulterer i alle mulige kombinationer:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
For \(n=20\) får vi:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Vi kan udvide problemet til ikke-kvadratiske net. Den følgende løsning implementerer en beregning i PHP ved hjælp af bcmath med en runtime på \( O(n) \) med inputformatet "Antal testcases, \(n_1\) \(m_1\) , ...":
47bb78215ee0531a787bb5034652eaf4
Forresten kan alle problemer i Euler-projektet også løses online på det anbefalede HackerRank- sted.