Mashruuca Euler: Waddooyinka Lattice

Mashruuca 'Euler' waa taxane mashaakil barnaamijyo xiise leh, oo badanaa leh asal xisaabeed. Dhibaatooyinka badanaa waxaa loo soo qaadaa si algorithms casri ah loo sameeyo si loo gaaro hadafka waqti macquul ah. Maanta waxaan xallineynaa dhibaatada 15: Waddooyinka Lattice , halkaas oo aad xalka uga heli karto qaab fudud oo isku dhafan.


Su’aashu waa sida soo socota:

„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?“

Dhibaatada sidoo kale waxaa loo qaabeyn karaa si ka duwan: Waxa loo baahan yahay waa awooda hoosaadka dhammaan waddooyinka

$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$

Tani waa dhibaato isku dhafan oo fudud oo aan u isticmaalno qaabka urn (annaga oo aan beddelin oo aan tixgelin siinin). Waxaan hadda xiiseyneynaa dhab ahaan waddooyinka ay u maleyneyso in \(R\) iyo \(D\) si isku mid ah. Tani waxay keenaysaa dhammaan isku-darka suurtagalka ah:

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

Wixii \(n=20\) waan helaynaa:

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

Waxaan u kordhin karnaa dhibaatada shabakadaha aan laba jibaaran. Xalka soo socda ayaa fulinaya xisaabinta PHP iyadoo la kaashanayo bcmath iyadoo la ordayo \( O(n) \) iyadoo la adeegsanayo qaabka la gelinayo "Tirada kiisaska imtixaanka, \(n_1\) \(m_1\) , ...":

47bb78215ee0531a787bb5034652eaf4

By habka, dhammaan dhibaatooyinka Euler Mashruuca sidoo kale waxaa lagu xallin karaa khadka tooska ah ee lagula taliyay goobta HackerRank .

Dib u laabo