Proste zadanko ;>

Odpowiedz Nowy wątek
2003-10-06 14:35

Rejestracja: 17 lat temu

Ostatnio: 15 lat temu

0

Spróbujcie to rozwiązać, jeżeli w ogóle to możliwe [???] : http://www.emkej10.piwko.pl/zadanie.htm

Pozostało 580 znaków

2003-10-06 15:26

Rejestracja: 17 lat temu

Ostatnio: 1 rok temu

0

Problem sprowadza się do sprawdzenia, czy graf o o krawędziach (ciężko mi tu macierze rysować :P):
1-2
1-2
1-3
1-3
1-4
1-4
1-5
1-5
1-6
2-3
2-6
3-4
3-6
4-5
4-6
5-6
zawiera drogę Hamiltona.
Tak na oko to nie :(


Jest jeszcze jeden błąd :)
Unix is user friendly. It's just very particular about who it's friends are.

Pozostało 580 znaków

MoH
2003-10-06 16:21
MoH

Rejestracja: 17 lat temu

Ostatnio: 15 lat temu

0

Hmm już to kiedyś widziałem i jest to niemożliwe do wykonania według jakiejś zasady kogoś tam (mówiła ona coś o mostach i ich parzystości czy coś takiego). Poza tym nauczyciel matmy mojej koleżanki powiedział, że można to rozwiązać tylko przeprowadzając dwie symetryczne linie według środkowej pionowej ściany.

Pozostało 580 znaków

2003-10-06 16:56

Rejestracja: 17 lat temu

Ostatnio: 1 rok temu

0

MoH: o mostach to jest cykl Eulera. Tutaj tego raczej nie da się zastosować. Cykl Eulera jest jest wówczas, gdy przez wszystkie punkty grafu przejdzie się dokładnie raz i wróci w to samo miejsce (przy drodze nie ma tego drugiego ograniczenia).
Jeżeli za punkty grafu wziąłbyś ścianki, które ma przekroczyć, to możnaby dojść do ścianki i wrócić jeszcze w tym samym "pomieszczeniu". I akurat drogę Eulera możnaby tutaj bardzo łatwo znaleźć.
Jeżeli za wierzchołki przjąłbyś pomieszczenia, to mógłbyś pominąć niektóre ścianki przy przechodzeniu przez wierzchołki.
Dlatego właśnie trzeba ścianki oznaczyć jako krawędzie (bo tylko w jedną stronę się przechodzi) i przejść po wszystkich krawędziach dokładnie raz (czyli znaleźć drogę Hamiltona).
Jak ktoś znajdzie algorytm stwierdzający, czy w grafie jest droga (lub cykl) Hamiltona bez sprawdzania wszystkich możliwości, to niech da znać ;)


Jest jeszcze jeden błąd :)
Unix is user friendly. It's just very particular about who it's friends are.

Pozostało 580 znaków

MoH
2003-10-06 17:05
MoH

Rejestracja: 17 lat temu

Ostatnio: 15 lat temu

0

Dryobates: może i nie da sie tego zastosować, ale i tak wiem, że tego sie chyba nie da rozwiązać

Pozostało 580 znaków

2003-10-27 19:27

Rejestracja: 17 lat temu

Ostatnio: 1 rok temu

0

http://vogel.iglu.cz/bonus/images/zad1.jpg

//Coś Ci się rozlała czerwona farbka po lewej [rotfl] - m.M


Life is just a dream, you know...
[Cowboy Bebop]

Pozostało 580 znaków

Odpowiedz

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