Project Euler adalah rangkaian masalah pengaturcaraan yang menarik, selalunya dengan latar belakang matematik. Masalahnya sering diajukan sedemikian rupa sehingga algoritma canggih harus dikembangkan untuk mencapai tujuan dalam masa yang wajar. Hari ini kita menyelesaikan masalah 15: Laluan kisi , di mana anda boleh mencari jalan penyelesaiannya dengan kaedah gabungan sederhana.
Soalannya adalah seperti berikut:
„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?“
Masalahnya juga dapat dirumuskan secara berbeza: Apa yang diperlukan adalah kekuatan subset dari semua jalan
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Kami berhadapan dengan masalah kombinatori sederhana di mana kami menggunakan model guci (tanpa mengganti dan tanpa memperhatikan pesanan). Kami sekarang berminat dengan tepat jalan-jalan yang menurutnya \(R\) dan \(D\) tepat dengan frekuensi yang sama. Ini menghasilkan semua kemungkinan kombinasi:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
Untuk \(n=20\) kita dapat:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Kita boleh memanjangkan masalah ini ke grid bukan segi empat sama. Penyelesaian berikut melaksanakan pengiraan dalam PHP dengan bantuan bcmath dengan runtime \( O(n) \) dengan format input "Jumlah kes ujian, \(n_1\) \(m_1\) , ...":
47bb78215ee0531a787bb5034652eaf4
By the way, semua masalah Projek Euler juga dapat diselesaikan secara dalam talian di laman HackerRank yang disyorkan.