szukanie zaawansowane
 [ Posty: 11 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 10 lut 2016, o 18:20 
Użytkownik

Posty: 76
Lokalizacja: Warsaw
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?

Obrazek

Wiem że używa się do tego wzoru {n+k\choose k} ale nie wiem jak to liczyć próbowałem na sume trzech zbiorów ale to coś źle wychodzi?
Góra
Mężczyzna Offline
PostNapisane: 10 lut 2016, o 22:50 
Użytkownik

Posty: 9836
Lokalizacja: Bydgoszcz
Użyj zasady włączeń i wyłączeń.

Q.
Góra
Mężczyzna Offline
PostNapisane: 11 lut 2016, o 02:58 
Użytkownik

Posty: 76
Lokalizacja: Warsaw
No właśnie jakoś nie bardzo da się policzyć przejście przez te dwa punkty po prawej stronie
Góra
Mężczyzna Offline
PostNapisane: 11 lut 2016, o 04:06 
Użytkownik

Posty: 430
Lokalizacja: Wrocław
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

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 1054.
Góra
Mężczyzna Offline
PostNapisane: 11 lut 2016, o 09:37 
Użytkownik

Posty: 15817
Lokalizacja: Bydgoszcz
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.
Góra
Kobieta Offline
PostNapisane: 11 lut 2016, o 13:22 
Użytkownik
Avatar użytkownika

Posty: 4419
Lokalizacja: Łódź
Wyniku nie sprawdzam, ale zapis bardzo by się uprościł, gdybyś liczył

wszystkie \  najkrotsze \ drogi \  przez \ X \ + \ wszystkie \ przez \ Y\ + \ wszystkie \ przez \ Z \ - \ wszystkie  \ przez \ YX \ - \ wszystkie \ przez \ YZ
Góra
Mężczyzna Offline
PostNapisane: 11 lut 2016, o 13:56 
Użytkownik
Avatar użytkownika

Posty: 3469
Lokalizacja: blisko
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:

A_{1}B_{1} - początek i koniec lewej dolnej łamanej

A_{2}B_{2} - początek i koniec prawej dolnej łamanej

A_{3}B_{3} - początek i koniec górnej łamanej.

I teraz ustalmy:

1). przechodzimy tylko przez A_{1}B_{1}


Z A do B_{1} - jest tyle dróg co z A do A_{1}

Teraz liczymy drogi z B_{1} doB

Z B_{1} do B (ale bez przejścia przez pozostałe łamane) jest tyle dróg co:

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)

d- to drogi, które nas interesują

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...
Góra
Mężczyzna Offline
PostNapisane: 11 lut 2016, o 14:24 
Użytkownik

Posty: 430
Lokalizacja: Wrocław
Obrazek

Zapis np. AX1 oznacza ilość wszystkich możliwie najkrótszych dróg przejść od punktu A do X1.

Teraz zapiszę wyjaśnienie w tej samej kolejności co moje poprzednie obliczenia.

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
Góra
Kobieta Offline
PostNapisane: 11 lut 2016, o 16:08 
Użytkownik
Avatar użytkownika

Posty: 4419
Lokalizacja: Łódź
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.
Góra
Mężczyzna Offline
PostNapisane: 11 lut 2016, o 16:25 
Użytkownik

Posty: 430
Lokalizacja: Wrocław
d=AY1 \cdot Y2B+ AX1 \cdot X2B+ AZ1 \cdot Z2B -AY1 \cdot Y2X1 \cdot X2B - AY1 \cdot Y2Z1 \cdot Z2B

O to chodziło ?
Góra
Kobieta Offline
PostNapisane: 11 lut 2016, o 17:18 
Użytkownik
Avatar użytkownika

Posty: 4419
Lokalizacja: Łódź
tak
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 11 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Na ile sposobów można dotrzeć do punktu w n ruchach  Makier  6
 Możliwe drogi na planszy  Empeg  0
 m dyskretna - ile jest dróg z punktu ...  torbol  5
 Ilość dróg z punktu (0,0) do (4,4).  mike_1729_  4
 Pokojowa demonstracja oraz drogi  marttyna  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl