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モデルを使用する単純な組み合わせの問題です（置換せず、順序を考慮しません）。 ここで、 \(R\)と\(D\)正確に同じ頻度で\(D\)ことが保持されているパスに正確に関心があります。 これにより、考えられるすべての組み合わせが得られます:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
\(n=20\) 、:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
問題を非正方形グリッドに拡張できます。 次のソリューションは、「テストケースの数、 \(n_1\) \(m_1\) 、...」という入力形式で実行時間\( O(n) \)のbcmathを使用してPHPで計算を実装します。:
47bb78215ee0531a787bb5034652eaf4
ちなみに、オイラープロジェクトのすべての問題は、推奨されるHackerRankサイトでオンラインで解決することもできます。