liczba dróg do punktu

Odpowiedz Nowy wątek
2011-07-24 14:21
0

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.

Pozostało 580 znaków

2011-07-24 15:08
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.


Not Found
The requested URL /wypasiona_sygnaturka.txt was not found in this brain.
-----
Human/1.0.00 (Earth) Server at Poland Port 65535

Pozostało 580 znaków

2011-07-24 15:12

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

edytowany 1x, ostatnio: notexists, 2011-07-24 15:15

Pozostało 580 znaków

2011-07-24 15:54
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

edytowany 2x, ostatnio: Markness, 2011-07-24 16:14

Pozostało 580 znaków

2011-07-24 16:59
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.


Not Found
The requested URL /wypasiona_sygnaturka.txt was not found in this brain.
-----
Human/1.0.00 (Earth) Server at Poland Port 65535
dzięki wielkie za pomoc! - Markness 2011-07-24 17:16

Pozostało 580 znaków

2011-07-27 17:27
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!.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2011-07-27 17:29
Mylisz się językowo (po obrocie kwadratu uzyskamy romb) i matematycznie. Musimy wykonać 20 przesunięć w prawo i 20 w dół. Wzór podany przez @mnbvcX 40!(20!*20!) jest poprawny. - bogdans 2011-07-27 18:23

Pozostało 580 znaków

2011-07-27 22:22
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ę.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2011-07-27 22:24

Pozostało 580 znaków

2011-07-28 12:37
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.


To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0