"Эйлер долбоору" - бул көбүнчө математикалык билимге ээ болгон кызыктуу программалоо маселелеринин сериясы. Маселелер көбүнчө максатка акылга сыярлык убакыттын ичинде жетүү үчүн татаал алгоритмдерди иштеп чыгууну талап кылуучудай кылып иштелип чыгат. Бүгүн биз 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 сайтында онлайн режиминде да чечсе болот.