Project Euler , genellikle matematiksel bir altyapıya sahip, heyecan verici bir dizi programlama problemidir. Problemler genellikle, makul bir zaman dilimi içinde hedefe ulaşmak için karmaşık algoritmaların geliştirilmesini gerektirecek şekilde tasarlanmıştır. Bugün, basit kombinatoryal yöntemler kullanılarak çözülebilen 15. Problem olan Kafes Yolları'nı çözeceğiz.
Soru aşağıdaki gibidir:
„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?“
Sorun ayrıca farklı şekilde formüle edilebilir: İhtiyaç duyulan şey, tüm yolların alt kümesinin gücüdür.
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Bu, urn modelini kullandığımız basit bir kombinatoryal problemdir (değiştirmeden ve sırayı dikkate almadan). Şimdi, \(R\) ve \(D\) tam olarak aynı frekansta \(D\) iddia ettiği yollarla ilgileniyoruz. Bu, tüm olası kombinasyonlarla sonuçlanır:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
\(n=20\) için:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Sorunu kare olmayan ızgaralara genişletebiliriz. Aşağıdaki çözüm, PHP'de "Test durumlarının sayısı, \(n_1\) \(m_1\) , ..." girdi biçimiyle \( O(n) \) çalışma zamanıyla bcmath kullanarak bir hesaplama uygular.:
47bb78215ee0531a787bb5034652eaf4
Bu arada, Euler Projesi'nin tüm sorunları, önerilen HackerRank sitesinde çevrimiçi olarak da çözülebilir.