Mam tabelę 20x20. Moim zadaniem jest znaleźć liczbę dróg z lewego górnego punktu do prawego dolnego (bez cofania się w górę i lewą stronę tabeli). Na razie doszedłem tylko do tego, że drogi wychodzące z najwyżej położonej poziomej krawędzi i kierujące się pionowo w dół (i zmierzające do celu) oraz te wychodzące z pionowej krawędzi z lewej strony i kierujące się do końca w prawo (i również zmierzające do celu) liczą 2n gdzie n to rozmiar tabeli. Niestety nie mam pomysłu jak policzyć wszystkie możliwości dróg w "środku" tabeli. Domyślam się że dość kiepsko to wytłumaczyłem, niestety nie wiem jak inaczej zobrazować mój problem. z góry dzięki za pomoc.
0
0
Przyjmijmy, że m[i,j] to liczba sposobów, na które można dotrzeć do pola [i,j] (powiedzmy, że i to wiersze, zaś j to kolumny).
Oczywiście m[1,1]=1. Dalej, nietrudno zauważyć, że
m[2,1]=1; m[3,1]=1; m[4,1]=1; ...; m[20,1]=1;
m[1,2]=1; m[1,3]=1; m[1,4]=1; ...; m[1,20]=1;
To znaczy do pól w pierwszej kolumnie tabeli lub pierwszym wierszu da się iść tylko w jednym kierunku, czyli tylko na jeden sposób.
Teraz możemy lecieć kolejno wierszami od lewej do prawej.
Zauważ, że do pola [i,j] możesz dotrzeć albo z komórki o pole wyżej (do tej można dotrzeć na m[i-1, j] sposobów) albo z komórki po lewej stronie (czyli m[i, j-1] sposobów). Daje to wtedy wzór m[i,j] = m[i-1,j] + m[i,j-1]. Oczywiście, jeżeli na tym polu jest przeszkoda, tzn. nie można wejść na pole, to wtedy liczba sposobów wynosi 0.
1
trochę kombinatoryki...
interpretacja:
musisz wykonać 19 kroków w prawo oraz 19 kroków w dół, czyli razem 38 kroków w pewnej kolejności
pytanie:
na ile sposobów można wybrać 19 elementów (niech ozaczają kroki w prawo) z 38 (wszystkich kolejnych kroków)?
rozwiązanie:
kombinacja bez powtórzeń http://pl.wikipedia.org/wiki/Kombinacja_bez_powtórzeń
odpowiedź:
38!/(19!*19!)
uwaga:
nie pisałeś nic o przeszkodach ani różnej ilości dróg, więc założyłem, że Twoja plansza to zwyczajna kratownica, jeśli nie - stosuj rozwiązanie mnbvcX
0
@notexists to jednak nie to, @mnbvcX wydaje się że źle mnie zrozumiałeś, chodzi mi o dojście do punktu nie pola, np. do punktu [1,1] prowadzą dwie drogi z punktu [0,0].
Może po prostu dam linka do problemu http://projecteuler.net/index.php?section=problems&id=15
Być może to ja źle opisałem problem, jeśli tak to z góry przepraszam
1
No, trochę widać zrozumiałem nieco inaczej treść, ale w rzeczywistości wyjdzie na to samo - bo jeśli masz tabelę 20x20, to przecież w każdym rzędzie jest 21 wierzchołków i w każdej kolumnie też jest po 21 wierzchołków.
Ze względu na to, że nie ma żadnych przeszkód w tym problemie, można użyć sobie wygodnego wzoru zaserwowanego przez @notexists. Tylko mała zmiana - trzeba wykonać już czterdzieści ruchów, w tym 20 w jedną stronę (prawo) i 20 w dół. Wzór będzie taki:
40! / (20! * 20!) = pewna dwunastocyfrowa liczba.
0
Ja bym opisał problem inaczej, by łatwiej było go uchwycić.
Wyobraź sobie, że przekrzywiasz ten kwadrat w rąb, obniżając każdą kolejną kolumnę o jeden w dół w porównaniu do poprzedniej kolumny.
Wtedy opis ruchu zmienia się tak, że każdy krok jest pójściem w dół i opcjonalnym przejściem w prawo (zmianą kolumny). W ten sposób dowolna kombinację ruchów możesz opisać zestawem 19 liczb określających na jakim poziomie opuszczasz daną kolumnę (poza ostatnią kolumną). Liczby te są zawsze ustawione rosnąco (nie można iść w górę).
Zakres tych liczb jest określony od 1 do 39 (lub od 0 do 38) (bo pierwsza kolumny się nie obniża).
Teraz problem sprowadza się do wybrania losowych 19 liczb spośród 39 czyli prosty symbol newtona rozwiązuje problem 39!/19!/20!.
0
@bogdans:
źle zrozumiałeś,tu nie chodzi o obrót! Tyko coś takiego (przypadek 4x4):
1 2 3 4
1: *
2: * *
3: * * *
4: * * * *
5: * * *
6: * *
7: *
Zaczynamy od pozycji 1, 1 i każdy następny ruch ma y większe o 1 a x to samo lub większe o 1.
Kombinacje ruchu od rogu do rogu można opisać współrzędnymi y ostatniego pola odwiedzonego w kolumnie (ostatnia kolumna nie ma znaczenia bo zmierzamy do rogu, więc zawsze będzie 2n-1),
Kolejne współrzędne y stanowią rosnący ciąg liczb z zakresu od 1 do 6 (=2*(n-1)) (tu miałem błąd), więc poprawny wynik to 2*(n-1) po n-1, czyli dla n=20 wynik to 38!/19!^2.
Fakt wtedy wynik jest ten sam co u notexists, ale uzasadnienie notexists jest nieco grząskie bo zawsze musisz wykonać 19 ruchów w prawo i 19 w dół, więc nie widać wyraźnie skąd nagle trzeba wybrać 19 z 38, moje rozumowanie wypełnia tylko tę lukę.
0
Dołożyłeś jeszcze jeden błąd, to co narysowałeś to nie jest romb a tym bardziej nie jest to rąb. ;)
Każdą drogę można opisać przez słowo o długości 40 zbudowane z liter 'r' i 'd', 'r' oznacza przesunięcie w prawo, 'd' oznacza przesunięcie w dół. Liter 'r' i 'd' musi być 20. Takich słów jest 40!(20!*20!). Imho, w rozumowaniu @notexits'a nie ma żadnej luki.