[Algorytmy] ProjectEuler 15 - liczba dróg w siatce

[MichalProg]

Dzień dobry.

Mam takie pytanie: próbuję rozwiązać problem 15 z

Kod: Zaznacz cały

https://projecteuler.net/problem=15

. Rozrysowałem sobie siatkę dla 2x2 i 3x3. Przy 3x3 sprawa jeszcze jest do ogarnięcia przeze mnie. Ale powiem najpierw o swoich wnioskach.

Dla siatki 2x2 mamy wzór:

Kod: Zaznacz cały

3 + 2 + 1 = 6

Dla siatki 3x3 mamy wzór:

Kod: Zaznacz cały

[(4 + 3 + 2 + 1) + (3 + 2 + 1) + (2 + 1) + (1)] + 
[(3 + 2 + 1) + (2 + 1) + (1)] +
[(2 + 1) + (1)] +
[(1)] =
= 10 + 6 + 3 + 1 + 6 + 3 + 1 + 3 + 1 + 1 = 20 + 10 + 4 + 1 = 35

Dla większych siatek już nie jest tak łatwo, gdyż zwiększa się liczba rzędów i powielają się sumy wielokrotnie, te same.

Nie proszę o rozwiązanie, a o wskazówkę. Czy jest jakiś aparat matematyczny, aby to rozgryźć, czy trzeba zbudować pętlę 21

Kod: Zaznacz cały

for

'ów? (C++)

Dzięki
Michał

[kerajs]

3x3:
Droga składa się z trzech odcinków w prawo (P) i trzech w dół (D)
Ilość dróg to ilość permutacji między nimi:
\(\displaystyle{ il_{3 \times 3}= \frac{6!}{3!3!}=20}\)
NxN:
\(\displaystyle{ il_{N \times N}= \frac{(2N)!}{(N!)^2}}\)

[MichalProg]

Ok, skąd taki wzór i jak do tego dojść? Z jakiej wiedzy korzystałeś? Dzięki Michał

Faktycznie, tyle wychodzi, sprawdziłem krok po kroku. Ale skąd taki wzór?



Ps.

Tego raczej nie da się obliczyć z tego wzoru, bezpośrednio, gdyż \(\displaystyle{ 40!}\) nie zmieści się, bez przybliżenia, w zmiennej.

[mortan517]

Więc pomyśl, co zrobić, żeby nie musieć liczyć \(\displaystyle{ 40!}\).

[kerajs]

Ok, skąd taki wzór i jak do tego dojść?

Odpowiedzi na te pytania napisałem w poprzednim poscie. Może je rozwinę: droga w siatce 3x3 składa się z 3 odcinków w prawo (P, P, P) i trzech odcinków w dół (D, D, D). Zamiast rysować po siatce mogę wypisywać te drogi:
PPPDDD
PPDPDD
PPDDPD
PPDDDP
PDPPDD

PDPDPD
PDPDDP
PDDPPD
PDDPDP
PDDDPP

DPPPDD
DPPDPD
DPPDDP
DPDPPD
DPDPDP

DPDDPP
DDPPPD
DDPPDP
DDPDPP
DDDPPP

Takie wypisywanie dróg, choć skuteczne (jest 20 dróg) jest jednak mało efektywne.

Z jakiej wiedzy korzystałeś?

Z takim przestawianiem literek spotkałeś się na pierwszej lekcji z kombinatoryki w szkole średniej przy okazji wprowadzania pojęcia permutacji. Poznałeś wtedy także stosowne wzorki które tu wykorzystałem.
\(\displaystyle{ il_{3 \times 3}= \frac{\red 6!}{\blue 3! \green 3!}}\)
Sześć elementów permutuje (zamienia się miejscami) na 6! sposobów.
Jednak ruchy w prawo (litery P) są nierozróżnialne więc wynik dzielę przez ilość permutacji miedzy nimi.
Analogicznie ruchy w dół (litery D) są nierozróżnialne więc wynik dzielę przez permutację miedzy nimi.

Tego raczej nie da się obliczyć z tego wzoru, bezpośrednio, gdyż \(\displaystyle{ 40!}\) nie zmieści się, bez przybliżenia, w zmiennej.

\(\displaystyle{ \frac{ 6!}{ 3! 3!}= \frac{1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6}{1 \cdot 2 \cdot 3 \cdot 1 \cdot 2 \cdot 3} =\frac{ 4 \cdot 5 \cdot 6}{ 1 \cdot 2 \cdot 3} =4 \cdot 5}\)