Projekto Euler estas serio de ekscitaj programaj problemoj, ofte kun matematika fono. La problemoj ofte estas desegnitaj por postuli la disvolvon de sofistikaj algoritmoj por atingi la celon ene de akceptebla tempokadro. Hodiaŭ ni solvos Problemon 15: Kradaj vojoj , kiu povas esti solvita per simplaj kombinaj metodoj.
La demando estas jena:
„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?“
La problemo ankaŭ povas esti formulita alimaniere: Necesas la potenco de la subaro de ĉiuj vojoj
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Ĉi tio estas simpla kombina problemo, en kiu ni uzas la urnan modelon (sen anstataŭigi kaj sen konsideri la ordon). Ni nun interesiĝas ĝuste pri tiuj vojoj, por kiuj ĝi diras, ke \(R\) kaj \(D\) ĝuste kun la sama ofteco. Ĉi tio rezultigas ĉiujn eblajn kombinaĵojn:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
Por \(n=20\) ni ricevas:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Ni povas etendi la problemon al ne-kvadrataj kradoj. La sekva solvo efektivigas kalkulon en PHP kun la helpo de bcmath kun rultempa tempo de \( O(n) \) kun la eniga formato "Nombro de testkazoj, \(n_1\) \(m_1\) , ...":
47bb78215ee0531a787bb5034652eaf4
Cetere , ĉiuj problemoj de la Projekto Euler ankaŭ povas esti solvitaj interrete en la rekomendinda retejo HackerRank .