Project Euler - бул кызыктуу программалоонун бир катар маселелери, көбүнчө математикалык билимге ээ. Көйгөйлөр көп учурда максатка жетүү үчүн татаал алгоритмдерди иштеп чыгууга аргасыз болушат. Бүгүн биз 15- көйгөйдү чечип жатабыз : торчолордун жолдору , бул жерде сиз жөнөкөй комбинатордук каражаттар менен чечим таба аласыз.
Суроо төмөнкүдөй:
„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?“
Маселе ар башкача формулировка кылынышы мүмкүн: Бардык жолдордун топтомунун күчү керек
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Бул жөнөкөй комбинатордук маселе, анда биз urn моделин колдонобуз (алмаштырбай жана буйрукту эске албай). Азыр биз аны так ошол жыштыкта \(D\) \(R\) жана \(D\) жолдору кызыктырат. Бул бардык мүмкүн болгон айкалыштарды алып келет:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
\(n=20\) алабыз:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Маселени чарчы эмес торчолорго чейин жайылта алабыз. Төмөнкү чечим PHPде bcmath жардамы менен эсептөөнү ишке ашырат \( O(n) \) "Форматтын саны, \(n_1\) \(m_1\) , ..." \(m_1\):
47bb78215ee0531a787bb5034652eaf4
Баса, Эйлер Долбоорунун бардык көйгөйлөрүн сунушталган HackerRank сайтында онлайн режиминде да чечсе болот.