Drogi z punktu A do B
-
- Użytkownik
- Posty: 69
- Rejestracja: 29 cze 2015, o 19:50
- Płeć: Mężczyzna
- Lokalizacja: Warsaw
- Podziękował: 66 razy
Drogi z punktu A do B
Cześć, Pomógłby mi ktoś rozwiązać to zadanie ?
Ile jest na podanej kracie ulic najkrótszych dróg z A do B, które zawierają przynajmniej jeden z wydzielonych fragmentów dróg?
Wiem że używa się do tego wzoru \(\displaystyle{ {n+k\choose k}}\) ale nie wiem jak to liczyć próbowałem na sume trzech zbiorów ale to coś źle wychodzi?
Ile jest na podanej kracie ulic najkrótszych dróg z A do B, które zawierają przynajmniej jeden z wydzielonych fragmentów dróg?
Wiem że używa się do tego wzoru \(\displaystyle{ {n+k\choose k}}\) ale nie wiem jak to liczyć próbowałem na sume trzech zbiorów ale to coś źle wychodzi?
-
- Użytkownik
- Posty: 69
- Rejestracja: 29 cze 2015, o 19:50
- Płeć: Mężczyzna
- Lokalizacja: Warsaw
- Podziękował: 66 razy
Drogi z punktu A do B
No właśnie jakoś nie bardzo da się policzyć przejście przez te dwa punkty po prawej stronie
-
- Użytkownik
- Posty: 426
- Rejestracja: 29 paź 2015, o 16:26
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 21 razy
- Pomógł: 90 razy
Drogi z punktu A do B
O coś takiego chodzi tutaj ??? , bo robię pierwszy raz tego typu zadanie ?
Górna droga - X
Środkowa - Z
Dolna - Y
Kolejne składniki sumy oznaczają:
- ilość przejść tylko przez Y
- ilość przejść tylko przez X
- ilość przejść tylko przez Z
- ilość przejść tylko przez Y i X
- ilość przejść tylko przez Y i Z
\(\displaystyle{ d=\binom{1+2}{2}\left[ \binom{4+6}{6} -\binom{1+2}{2}\binom{1+3}{3}-\binom{0+1}{1}\binom{2+3}{3}\right]+\left[ \binom{4+4}{4}-\binom{1+2}{2}\binom{1+2}{2}\right]\binom{1+3}{3}+\left[ \binom{2+5}{5}-\binom{1+2}{2}\binom{0+1}{1}\right]\binom{2+3}{3}+\binom{1+2}{2}\binom{1+2}{2}\binom{1+3}{3}+\binom{1+2}{2} \binom{0+1}{1}\binom{2+3}{3}=1054}\)
Odp: Ilość najkrótszych dróg z A do B wynosi \(\displaystyle{ 1054}\).
Górna droga - X
Środkowa - Z
Dolna - Y
Kolejne składniki sumy oznaczają:
- ilość przejść tylko przez Y
- ilość przejść tylko przez X
- ilość przejść tylko przez Z
- ilość przejść tylko przez Y i X
- ilość przejść tylko przez Y i Z
\(\displaystyle{ d=\binom{1+2}{2}\left[ \binom{4+6}{6} -\binom{1+2}{2}\binom{1+3}{3}-\binom{0+1}{1}\binom{2+3}{3}\right]+\left[ \binom{4+4}{4}-\binom{1+2}{2}\binom{1+2}{2}\right]\binom{1+3}{3}+\left[ \binom{2+5}{5}-\binom{1+2}{2}\binom{0+1}{1}\right]\binom{2+3}{3}+\binom{1+2}{2}\binom{1+2}{2}\binom{1+3}{3}+\binom{1+2}{2} \binom{0+1}{1}\binom{2+3}{3}=1054}\)
Odp: Ilość najkrótszych dróg z A do B wynosi \(\displaystyle{ 1054}\).
-
- Użytkownik
- Posty: 22210
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Drogi z punktu A do B
Trudno zweryfikować poprawność tych rachunków bez ich uzasadnienia. Generalnie uwielbiam wprost, gdy ktoś w rozwiązaniu zadania kombinatorycznego wypisuje ciąg znaczków składający się z silni i dwumianów Newtona.
- kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
Drogi z punktu A do B
Wyniku nie sprawdzam, ale zapis bardzo by się uprościł, gdybyś liczył
\(\displaystyle{ wszystkie \ najkrotsze \ drogi \ przez \ X \ + \ wszystkie \ przez \ Y\ + \ wszystkie \ przez \ Z \ - \ wszystkie \ przez \ YX \ - \ wszystkie \ przez \ YZ}\)
\(\displaystyle{ wszystkie \ najkrotsze \ drogi \ przez \ X \ + \ wszystkie \ przez \ Y\ + \ wszystkie \ przez \ Z \ - \ wszystkie \ przez \ YX \ - \ wszystkie \ przez \ YZ}\)
- arek1357
- Użytkownik
- Posty: 5748
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Drogi z punktu A do B
Zasada włączeń i wyłączeń w tym zadaniu jest potrzebna ale nie demonizujmy jej.
Bardziej powinniśmy stworzyć sobie koncepcję do tego zadania.
Najpierw może oznaczmy sobie:
\(\displaystyle{ A_{1}B_{1}}\) - początek i koniec lewej dolnej łamanej
\(\displaystyle{ A_{2}B_{2}}\) - początek i koniec prawej dolnej łamanej
\(\displaystyle{ A_{3}B_{3}}\) - początek i koniec górnej łamanej.
I teraz ustalmy:
1). przechodzimy tylko przez \(\displaystyle{ A_{1}B_{1}}\)
Z \(\displaystyle{ A}\) do \(\displaystyle{ B_{1}}\) - jest tyle dróg co z \(\displaystyle{ A do A_{1}}\)
Teraz liczymy drogi z \(\displaystyle{ B_{1}}\) do\(\displaystyle{ B}\)
Z \(\displaystyle{ B_{1} do B}\) (ale bez przejścia przez pozostałe łamane) jest tyle dróg co:
\(\displaystyle{ d(B_{1},B)=w(B_{1},B)-w(B_{1},A_{2}) \cdot w(B_{2},B)-w(B_{1},A_{3}) \cdot w(B_{3},B)}\)
\(\displaystyle{ d}\)- to drogi, które nas interesują
\(\displaystyle{ w}\)- wszystkie drogi
Pokazałem jak obliczyć ilość dróg przechodząc tylko przez pierwszą łamaną.
Podobnie liczymy przez drugą łamaną i trzecią a potem przez:
pierwszą i drugą
oraz:
pierwszą i trzecią.
I stosujemy włączania i wyłączania zasadę.
Zauważmy również, że przejście przez wszystkie łamane jest niemożliwe...
Bardziej powinniśmy stworzyć sobie koncepcję do tego zadania.
Najpierw może oznaczmy sobie:
\(\displaystyle{ A_{1}B_{1}}\) - początek i koniec lewej dolnej łamanej
\(\displaystyle{ A_{2}B_{2}}\) - początek i koniec prawej dolnej łamanej
\(\displaystyle{ A_{3}B_{3}}\) - początek i koniec górnej łamanej.
I teraz ustalmy:
1). przechodzimy tylko przez \(\displaystyle{ A_{1}B_{1}}\)
Z \(\displaystyle{ A}\) do \(\displaystyle{ B_{1}}\) - jest tyle dróg co z \(\displaystyle{ A do A_{1}}\)
Teraz liczymy drogi z \(\displaystyle{ B_{1}}\) do\(\displaystyle{ B}\)
Z \(\displaystyle{ B_{1} do B}\) (ale bez przejścia przez pozostałe łamane) jest tyle dróg co:
\(\displaystyle{ d(B_{1},B)=w(B_{1},B)-w(B_{1},A_{2}) \cdot w(B_{2},B)-w(B_{1},A_{3}) \cdot w(B_{3},B)}\)
\(\displaystyle{ d}\)- to drogi, które nas interesują
\(\displaystyle{ w}\)- wszystkie drogi
Pokazałem jak obliczyć ilość dróg przechodząc tylko przez pierwszą łamaną.
Podobnie liczymy przez drugą łamaną i trzecią a potem przez:
pierwszą i drugą
oraz:
pierwszą i trzecią.
I stosujemy włączania i wyłączania zasadę.
Zauważmy również, że przejście przez wszystkie łamane jest niemożliwe...
-
- Użytkownik
- Posty: 426
- Rejestracja: 29 paź 2015, o 16:26
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 21 razy
- Pomógł: 90 razy
Drogi z punktu A do B
Zapis np. \(\displaystyle{ AX1}\) oznacza ilość wszystkich możliwie najkrótszych dróg przejść od punktu \(\displaystyle{ A}\) do \(\displaystyle{ X1}\).
Teraz zapiszę wyjaśnienie w tej samej kolejności co moje poprzednie obliczenia.
\(\displaystyle{ d=AY1 \cdot \left[ Y2B-Y2X1 \cdot X2B-Y2Z1 \cdot Z2B\right]+\left[ AX1-AY1 \cdot Y2X1\right] \cdot X2B+\left[ AZ1-AY1 \cdot Y2Z1 \right] \cdot Z2B +AY1 \cdot Y2X1 \cdot X2B+AY1 \cdot Y2Z1 \cdot Z2B}\)
- kropka+
- Użytkownik
- Posty: 4389
- Rejestracja: 16 wrz 2010, o 14:54
- Płeć: Kobieta
- Lokalizacja: Łódź
- Podziękował: 1 raz
- Pomógł: 787 razy
Drogi z punktu A do B
W ten sposób dostajecie tego samego "tasiemca" co kilka postów wyżej. Zamiast zastosować zasadę włączeń i wyłączeń jeden raz, wolicie ją stosować trzykrotnie, a potem dodawać to samo co już dwukrotnie odjęliście.
Ostatnio zmieniony 11 lut 2016, o 17:27 przez kropka+, łącznie zmieniany 1 raz.
-
- Użytkownik
- Posty: 426
- Rejestracja: 29 paź 2015, o 16:26
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 21 razy
- Pomógł: 90 razy
Drogi z punktu A do B
\(\displaystyle{ d=AY1 \cdot Y2B+ AX1 \cdot X2B+ AZ1 \cdot Z2B -AY1 \cdot Y2X1 \cdot X2B - AY1 \cdot Y2Z1 \cdot Z2B}\)
O to chodziło ?
O to chodziło ?