Projekt Euler: ścieżki kratowe

Projekt Euler to seria ekscytujących problemów programistycznych, często o podłożu matematycznym. Często problemy stawiane są w taki sposób, że trzeba opracować zaawansowane algorytmy, aby osiągnąć cel w rozsądnym czasie. Dzisiaj rozwiązujemy problem 15: Ścieżki kratowe , dla których można znaleźć rozwiązanie za pomocą prostych środków kombinatorycznych.


Pytanie jest następujące:

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

Problem można też sformułować inaczej: potrzebna jest moc podzbioru wszystkich ścieżek

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

Jest to prosty problem kombinatoryczny, w którym używamy modelu urny (bez wymiany i bez rozważania kolejności). Jesteśmy teraz zainteresowani dokładnie tymi ścieżkami, dla których, jak twierdzi, \(R\) i \(D\) dokładnie taką samą częstotliwością. Powoduje to wszystkie możliwe kombinacje:

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

Dla \(n=20\) otrzymujemy:

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

Możemy rozszerzyć problem na niekwadratowe siatki. Poniższe rozwiązanie implementuje obliczenia w PHP za pomocą bcmath ze środowiskiem wykonawczym \( O(n) \) z formatem wejściowym „Liczba przypadków testowych, \(n_1\) \(m_1\) , ...”:

47bb78215ee0531a787bb5034652eaf4

Nawiasem mówiąc, wszystkie problemy Projektu Euler można również rozwiązać online na zalecanej stronie HackerRank .

Plecy