Project Euler është një seri problemesh emocionuese të programimit, shpesh me një sfond matematikor. Problemet shpesh paraqiten në mënyrë të tillë që algoritme të sofistikuar duhet të zhvillohen në mënyrë që të arrihet qëllimi në një kohë të arsyeshme. Sot ne zgjidhim problemin 15: Shtigjet e rrjetave , ku mund ta gjeni zgjidhjen me mjete të thjeshta kombinuese.
Pyetja është si më poshtë:
„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?“
Problemi gjithashtu mund të formulohet ndryshe: Ajo që nevojitet është fuqia e nëngrupit të të gjitha shtigjeve
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Ky është një problem i thjeshtë kombinator në të cilin ne përdorim modelin e urnës (pa zëvendësuar dhe pa marrë parasysh renditjen). Tani na interesojnë pikërisht ato shtigje për të cilat qëndron se \(R\) dhe \(D\) saktësisht \(D\) të njëjtën frekuencë. Kjo rezulton në të gjitha kombinimet e mundshme:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
Për \(n=20\) marrim:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Ne mund ta shtrijmë problemin në rrjetet jo katrore. Zgjidhja e mëposhtme zbaton një llogaritje në PHP me ndihmën e bcmath me një kohë ekzekutimi të \( O(n) \) me formatin e hyrjes "Numri i rasteve të provës, \(n_1\) \(m_1\) , ...":
47bb78215ee0531a787bb5034652eaf4
Nga rruga, të gjitha problemet e Projektit Euler gjithashtu mund të zgjidhen në internet në faqen e rekomanduar HackerRank .