Project Euler är en serie spännande programmeringsproblem, ofta med matematisk bakgrund. Problemen ställs ofta på ett sådant sätt att sofistikerade algoritmer måste utvecklas för att uppnå målet på en rimlig tid. Idag löser vi problem 15: Gittervägar , där du kan hitta lösningen med enkla kombinatoriska medel.
Frågan är följande:
„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 också formuleras annorlunda: Vad som behövs är kraften i delmängden av alla vägar
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Vi har här att göra med ett enkelt kombinationsproblem där vi använder urnmodellen (utan att ersätta och utan att ta hänsyn till ordern). Vi är nu intresserade av just de vägar för vilka det hävdas att \(R\) och \(D\) exakt samma frekvens. Detta resulterar i alla möjliga kombinationer:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
För \(n=20\) vi:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Vi kan utvidga problemet till icke-kvadratiska rutnät. Följande lösning implementerar en beräkning i PHP med bcmath med en körtid \( O(n) \) med inmatningsformatet "Antal testfall, \(n_1\) \(m_1\) , ...":
47bb78215ee0531a787bb5034652eaf4
Förresten , alla problem i Euler-projektet kan också lösas online på den rekommenderade HackerRank- webbplatsen.