Projekt Euler är en serie spännande programmeringsproblem, ofta med matematisk bakgrund. Problemen är ofta utformade för att kräva utveckling av sofistikerade algoritmer för att uppnå målet inom en rimlig tidsram. Idag ska vi lösa problem 15: Gitterbanor , som kan lösas med enkla kombinatoriska metoder.
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.