Proyek Euler kuwi seri masalah pemrograman sing nyenengake, asring nganggo latar mburi matematika. Masalah kasebut asring dirancang kanggo mbutuhake pangembangan algoritma canggih kanggo nggayuh tujuan sajrone wektu sing cukup. Dina iki kita bakal ngrampungake Masalah 15: Jalur kisi , sing bisa dirampungake nggunakake metode kombinatorial sing prasaja.
Pitakonane kaya ing ngisor iki:
„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?“
Masalah kasebut uga bisa dirumusake kanthi beda: Sing dibutuhake yaiku kekuatan subset kabeh jalur
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Iki minangka masalah kombinatorial sederhana sing nggunakake model urn (tanpa ngganti lan tanpa ngelingi urutane). Saiki kita kepincut kanthi tepat dalan kasebut sing nggawe \(R\) lan \(D\) frekuensi sing padha. Iki nyebabake kabeh kombinasi sing mungkin:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
Kanggo \(n=20\) kita entuk:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Kita bisa nggedhekake masalah menyang kisi non-alun. Solusi ing ngisor iki ngetrapake pitungan ing PHP kanthi pitulung bcmath kanthi runtime \( O(n) \) kanthi format input "Jumlah kasus uji coba, \(n_1\) \(m_1\) , ...":
47bb78215ee0531a787bb5034652eaf4
Mangkene, kabeh masalah Proyek Euler uga bisa ditanggulangi kanthi online ing situs HackerRank sing disaranake.