Cześć
Mam do napisania program rozwiązujący problem Wilk-Koza-Kapusta.
Opis problemu:
Na jednym brzegu rzeki jest wilk, koza i kapusta. Rolnik dysponuje łodzią o pojemności 2 (jest miejsce dla rolnika+jedno dodatkowe). Rolnik musi przewieźć na drugą stronę rzeki cały swój inwentarz. Nie może jednak dopuścić do sytuacji, gdy na brzegu zostanie para Wilk-Koza lub Koza-Kapusta (wilk zje kozę, koza zje kapustę).
Podstawowe rozwiązanie tego problemu jest powszechnie znane i trywialne. Moim zadaniem natomiast jest zaprojektowanie algorytmu generującego różne możliwe rozwiązania tego problemu dla zwielokrotnionych danych oraz drugiego programu weryfikującego prawidłowość wygenerowanych rozwiązań. Przykładowo może być więcej niż jeden wilk, więcej niż jedna koza lub więcej niż jedna kapusta. Na dodatek może być więcej niż jedno wolne miejsce w łódce.
Pierwszy pomysł jaki mi przyszedł do głowy, uogólnienie tego problemu do teorii grafów.
Weźmy na przykład graf (reprezentujący lewy brzeg rzeki) L(V,E) w którym zbiór wierzchołków V={Wilk, Koza, Kapusta...} natomiast zbiór krawędzi E={{Wilk,Koza}, {Koza,Kapusta}...}.
Przedstawiając odpowiednią sekwencję ruchów musimy utworzyć graf (reprezentujący prawy brzeg rzeki) P(V',E'). Należy to zrobić w taki sposób aby za każdym razem gdy rolnik na łodzi opuszcza brzeg, pozostały na nim same wilki albo same kapusty albo same kozy albo wilki i kapusty. W innym przypadku zawsze coś zostanie zjedzone.
Podsumowując, poszukuję propozycji algorytmów (wydaje mi się, że z teorii grafów, ale być może lepsze będą jakieś inne...) rozwiązujących problem usuwania poszczególnych wierzchołków grafu (drzewa?). W zasadzie w tym miejscu moje pomysły się kończą
Dzięki za pomoc
Pozdrawiam
Proszę, zgodnie z regulaminem pkt 11.1, o usunięcie słów PROBLEM lub/i POMOC z tytułu. Prośba dotyczy także wszelkich wariacji typu: kłopot, pomocy, problemy itd.
Równocześnie proszę o uściślenie, o jaki język programowania koledze chodzi.
- arnoldziq
Mam do napisania program rozwiązujący problem Wilk-Koza-Kapusta.
Opis problemu:
Na jednym brzegu rzeki jest wilk, koza i kapusta. Rolnik dysponuje łodzią o pojemności 2 (jest miejsce dla rolnika+jedno dodatkowe). Rolnik musi przewieźć na drugą stronę rzeki cały swój inwentarz. Nie może jednak dopuścić do sytuacji, gdy na brzegu zostanie para Wilk-Koza lub Koza-Kapusta (wilk zje kozę, koza zje kapustę).
Podstawowe rozwiązanie tego problemu jest powszechnie znane i trywialne. Moim zadaniem natomiast jest zaprojektowanie algorytmu generującego różne możliwe rozwiązania tego problemu dla zwielokrotnionych danych oraz drugiego programu weryfikującego prawidłowość wygenerowanych rozwiązań. Przykładowo może być więcej niż jeden wilk, więcej niż jedna koza lub więcej niż jedna kapusta. Na dodatek może być więcej niż jedno wolne miejsce w łódce.
Pierwszy pomysł jaki mi przyszedł do głowy, uogólnienie tego problemu do teorii grafów.
Weźmy na przykład graf (reprezentujący lewy brzeg rzeki) L(V,E) w którym zbiór wierzchołków V={Wilk, Koza, Kapusta...} natomiast zbiór krawędzi E={{Wilk,Koza}, {Koza,Kapusta}...}.
Przedstawiając odpowiednią sekwencję ruchów musimy utworzyć graf (reprezentujący prawy brzeg rzeki) P(V',E'). Należy to zrobić w taki sposób aby za każdym razem gdy rolnik na łodzi opuszcza brzeg, pozostały na nim same wilki albo same kapusty albo same kozy albo wilki i kapusty. W innym przypadku zawsze coś zostanie zjedzone.
Podsumowując, poszukuję propozycji algorytmów (wydaje mi się, że z teorii grafów, ale być może lepsze będą jakieś inne...) rozwiązujących problem usuwania poszczególnych wierzchołków grafu (drzewa?). W zasadzie w tym miejscu moje pomysły się kończą
Dzięki za pomoc
Pozdrawiam
Proszę, zgodnie z regulaminem pkt 11.1, o usunięcie słów PROBLEM lub/i POMOC z tytułu. Prośba dotyczy także wszelkich wariacji typu: kłopot, pomocy, problemy itd.
Równocześnie proszę o uściślenie, o jaki język programowania koledze chodzi.
- arnoldziq
No i nie używaj drzew, bo kozy wejdą na nie, zwłaszcza gdy będą pochyłe i zjedzą je z braku kapusty...
