Project Euler: Gitterstier

Project Euler er en række spændende programmeringsproblemer, ofte med matematisk baggrund. Problemerne stilles ofte på en sådan måde, at sofistikerede algoritmer skal udvikles for at nå målet på en rimelig tid. I dag løser vi problem 15: Gitterstier , hvor du kan finde løsningen med enkle kombinatoriske midler.


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.

Tilbage