Project Euler: Kafes yolları

Project Euler , genellikle matematiksel bir arka plana sahip bir dizi heyecan verici programlama problemidir. Sorunlar genellikle makul bir zamanda hedeflerine ulaşmak için gelişmiş algoritmaların geliştirilmesi gerektiği şekildedir. Bugün, çözümün basit kombinatoryal yöntemlerle bulunabileceği 15: Kafes yollarını çözüyoruz .


Soru şudur:

"2x2 ızgarasının sol üst köşesinden başlayıp yalnızca sağa ve aşağıya hareket edebilmek için sağ alt köşeye tam olarak 6 yol var. 20 × 20 ızgarada bu kadar kaç yol var? "

Sorun farklı şekilde de formüle edilebilir: Tüm yolların alt kümesinin kalınlığını arıyoruz

$$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 (geri koymadan ve siparişi göz ardı etmeden). Şimdi \(R\) ve \(D\) tam olarak aynı sayıda \(D\) yollarla ilgileniyoruz. Bu, tüm olası kombinasyonlarla sonuçlanır:

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

\(n=20\) şunu elde ederiz:

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

Sorunu kare olmayan ızgaralara genişletebiliriz. PHP'de aşağıdaki çözüm, "Test \(n_1\) sayısı, \(n_1\) \(m_1\) , ..." girdi biçimini kullanarak bir hesaplama yapmak için \( O(n) \) çalışma zamanı ile bcmath kullanır :

47bb78215ee0531a787bb5034652eaf4

Bu arada, Euler Projesi'nin tüm sorunları tavsiye edilen HackerRank sayfasında çevrimiçi olarak da çözülebilir.

Geri