Pāhana Euler: Nā ala latike

ʻO Project Euler kahi moʻo o nā pilikia hoʻonaninani hoʻonāukiuki, pinepine me kahi kāʻei makemakika. Hoʻokomo pinepine ʻia nā pilikia i kahi ala e hoʻomohala ʻia ai nā algorithms sophisticated e hoʻokō i ka pahuhopu i kahi manawa kūpono. I kēia lā, hoʻonā mākou i ka pilikia 15: Nā ala Lattice , kahi e hiki ai iā ʻoe ke loaʻa ka hopena me nā mea hoʻohui maʻalahi.


Penei ka nīnau:

„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?“

Hiki ke hana ʻokoʻa ʻia ka pilikia: ʻo ka mea e pono ai ka mana o ka subset o nā ala āpau

$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$

He pilikia kombinatorial maʻalahi kēia a mākou e hoʻohana ai i ka urn model (me ka hoʻololi ʻole a me ka noʻonoʻo ʻole i ke kauoha). Makemake mākou i kēia manawa i kēlā mau ala no ka mea e paʻa ai ia \(R\) a me \(D\) pololei me ka pinepine like. Loaʻa kēia i nā hui like āpau:

$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$

No \(n=20\) loaʻa iā mākou:

$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$

Hiki iā mākou ke hoʻolōʻihi i ka pilikia i nā grids square ʻole. Hoʻokomo ka hopena aʻe i kahi helu ma PHP me ke kōkua o bcmath me kahi manawa holoʻokoʻa o \( O(n) \) me ke ʻano hoʻokomo "Ka helu o nā hihia hoʻāʻo, \(n_1\) \(m_1\) , ...":

47bb78215ee0531a787bb5034652eaf4

Ma ke ala, hiki i nā pilikia āpau o ka Euler Project ke hoʻonā ʻia ma ka pūnaewele ma ka pūnaewele HackerRank i ʻōlelo ʻia .

Hope