Mam takie zadanko:
Ile jest najkrótszych dróg prowadzących z punktu A do B (tzn. można iść w prawo albo do góry).
- AU
- b12cf749e8cde785m.jpg (2.83 KiB) Przejrzano 749 razy
Znajdowanie najkrótszych dróg
-
Dumel
- Użytkownik
- Posty: 2000
- Rejestracja: 19 lut 2008, o 17:35
- Płeć: Mężczyzna
- Lokalizacja: Stare Pole/Kraków
- Podziękował: 60 razy
- Pomógł: 202 razy
Znajdowanie najkrótszych dróg
każda droga jest najkrótsza. 8 razy idziesz w prawo i 4 razy do góry. ciąg ruchów (P,P,G,P,G...) itp możesz wyznaczyć przez wybranie pozycji dla G, więc masz \(\displaystyle{ {12 \choose 4}}\) sposobów
-
abc666
Znajdowanie najkrótszych dróg
Dumel, chyba nie powiększyłeś sobie tego obrazka. Jest tam jeszcze parę odcinków przez, które nie można przejść.
kiju, od tego co napisał Dumel musisz odjąć liczbę dróg przez, które nie da się przejść.
Oznaczmy punkt A jako (0,0) a punkt B jako (8,4)
Droga zakazana musi przechodzić przez punkt (3,4) lub (8,0). Do pierwszego możemy dojść na \(\displaystyle{ {7 \choose 3}}\) sposobów. Myślenie jest takie samo jak w poście wyżej u Dumla. Do punktu (8,0) prowadzi tylko jedna droga (mamy ciąg (P,P,P,P,P,P,P,P)). Ponieważ punkty te znajdują się na "brzegu" to po dotarciu do tych punktów mamy już tylko jedną drogę i nie trzeba już przez nic mnożyć. Ostateczna odpowiedź więc to
\(\displaystyle{ {12 \choose 4} - {7 \choose 3} - {8 \choose 0}}\)
kiju, od tego co napisał Dumel musisz odjąć liczbę dróg przez, które nie da się przejść.
Oznaczmy punkt A jako (0,0) a punkt B jako (8,4)
Droga zakazana musi przechodzić przez punkt (3,4) lub (8,0). Do pierwszego możemy dojść na \(\displaystyle{ {7 \choose 3}}\) sposobów. Myślenie jest takie samo jak w poście wyżej u Dumla. Do punktu (8,0) prowadzi tylko jedna droga (mamy ciąg (P,P,P,P,P,P,P,P)). Ponieważ punkty te znajdują się na "brzegu" to po dotarciu do tych punktów mamy już tylko jedną drogę i nie trzeba już przez nic mnożyć. Ostateczna odpowiedź więc to
\(\displaystyle{ {12 \choose 4} - {7 \choose 3} - {8 \choose 0}}\)