Էյլերի նախագիծը հետաքրքիր ծրագրավորման խնդիրների շարք է, որոնք հաճախ մաթեմատիկական ծագում ունեն։ Խնդիրները հաճախ նախագծված են այնպես, որ պահանջեն բարդ ալգորիթմների մշակում՝ նպատակին հասնելու համար ողջամիտ ժամկետում։ Այսօր մենք կլուծենք 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 \}.$$
Սա պարզ կոմբինացիոն խնդիր է, որում մենք օգտագործում ենք ուրանի մոդելը (առանց փոխարինելու և առանց կարգը հաշվի առնելու): Մեզ հիմա հետաքրքրում են հենց այն ուղիները, որոնց համար պնդում է, որ \(R\) և \(D\) ճիշտ նույն հաճախականությամբ: Սա հանգեցնում է բոլոր հնարավոր համադրությունների:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
Համար \(n=20\) մենք ստանում ենք:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Մենք կարող ենք խնդիրը տարածել ոչ քառակուսի ցանցերի վրա: Հետևյալ լուծումը իրականացնում է հաշվարկ PHP- ում ` bcmath- ի միջոցով \( O(n) \) գործարկման եղանակով` «Փորձնական դեպքերի քանակը, \(n_1\) \(m_1\) , ...» մուտքագրման ձևաչափով::
47bb78215ee0531a787bb5034652eaf4
Ի դեպ, Euler Project- ի բոլոր խնդիրները կարող են լուծվել նաև առցանց `առաջարկվող HackerRank կայքում: