Project Euler este o serie de probleme de programare interesante, adesea cu un fundal matematic. Problemele sunt adesea puse în așa fel încât algoritmi sofisticati trebuie să fie dezvoltați pentru a atinge obiectivul într-un timp rezonabil. Astăzi rezolvăm problema 15: Căi de rețea , pentru care puteți găsi soluția cu mijloace combinatorii simple.
Întrebarea este următoarea:
„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?“
Problema poate fi formulată și în mod diferit: ceea ce este necesar este puterea subsetului tuturor căilor
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Aceasta este o problemă combinatorie simplă în care folosim modelul urnei (fără a înlocui și fără a lua în considerare ordinea). Acum suntem interesați de acele căi pentru care susține că \(R\) și \(D\) exact cu aceeași frecvență. Acest lucru are ca rezultat toate combinațiile posibile:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
Pentru \(n=20\) obținem:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Putem extinde problema la rețelele care nu sunt pătrate. Următoarea soluție implementează un calcul în PHP cu ajutorul bcmath cu un timp de rulare de \( O(n) \) cu formatul de intrare „Număr de cazuri de testare, \(n_1\) \(m_1\) , ...”:
47bb78215ee0531a787bb5034652eaf4
Apropo , toate problemele Proiectului Euler pot fi rezolvate și online pe site-ul HackerRank recomandat.