Wieża hanoi na 4 palach

[nertos]

Witam!

Czy znacie może jakąś stronę albo książkę gdzie będzie opisane jak
napisać program w c/c++ wieży hanoi na 4 palach. Na 3 palach to jest
normalnie ale na 4 to jest sztuka.

THX za wszelką pomoc

--
nertos | ***@o2.pl |
poznan.linux.org.pl |

[Maciek]

Post by nertos
Witam!
Czy znacie może jakąś stronę albo książkę gdzie
będzie opisane jak napisać program w c/c++
wieży hanoi na 4 palach. Na 3 palach to jest
normalnie ale na 4 to jest sztuka.

Hyhy :-)

Skoro na trzech jest normalne, to wybierz dowolne
trzy pale z danych czterech, i rozwiąż zadanie na
nich. Wystarczy do fazy, gdy jeden z nich zostaje
pusty. W tym momencie usuwasz z dalszych rozwazań
opróżniony pal, za to dołączasz czwarty - i znowu
masz zadanie na trzech palach, czyli "normalne".



Maciek

[nertos]

Post by Maciek

Post by nertos
Witam!
Czy znacie może jakąś stronę albo książkę gdzie
będzie opisane jak napisać program w c/c++
wieży hanoi na 4 palach. Na 3 palach to jest
normalnie ale na 4 to jest sztuka.

Hyhy :-)
Skoro na trzech jest normalne, to wybierz dowolne
trzy pale z danych czterech, i rozwiąż zadanie na
nich. Wystarczy do fazy, gdy jeden z nich zostaje
pusty. W tym momencie usuwasz z dalszych rozwazań
opróżniony pal, za to dołączasz czwarty - i znowu
masz zadanie na trzech palach, czyli "normalne".
Maciek

Czesc

Źle się zrozumieliśmy przy układaniu też wieży należy korzystać ze
wszystkich pali, a twoim sposobem to ja mogę zrobić wieże hanoi na 'n' palach.


--
nertos | ***@o2.pl |
poznan.linux.org.pl |

[Maciek]

Post by nertos

Post by Maciek

(....) jak napisać program w c/c++
wieży hanoi na 4 palach. Na 3 palach to jest
normalnie ale na 4 to jest sztuka.

Skoro na trzech jest normalne, to wybierz dowolne
trzy pale z danych czterech, i rozwiąż zadanie na
nich. Wystarczy do fazy, gdy jeden z nich zostaje
pusty. W tym momencie usuwasz z dalszych rozwazań
opróżniony pal, za to dołączasz czwarty - i znowu
masz zadanie na trzech palach, czyli "normalne".
(...)

Źle się zrozumieliśmy

Dlaczego...? Rozwiązanie spełnia zadane krytaria.

Post by nertos
przy układaniu też wieży należy
korzystać ze wszystkich pali,

Proszę bardzo:
1. pierwszy - najmniejszy - krążek przekładam
na dowolny wybrany pal (byle nie docelowy),
2. rozwiązuję pozostałymi krążkami standardowe
zadanie na pozostałych (trzech) palach,
3. przekładam najmniejszy krążek na miejsce.

Ewentualnie jeśli jest więcej niż cztery pale,
najmniejszy - a w zasadzie dowolny krążek w dowolnie
wybranej fazie rozwiązania, gdy na niego właśnie
przypada ruch - przekładam po kolei przez wszystkie
pale.

Post by nertos
a twoim sposobem to ja mogę zrobić wieże hanoi na
'n' palach.

No. :-)
To jest sprowadzenie problemu do wersji już rozwiązanej.
Może nie optymalne, ale na pewno skuteczne. :-D


Maciek

[qfel]

Pewnie chodzilo o optymalne (pod wzgledem ilosci ruchow) rozwiazanie na 4
palach;
Chociaz o ile pamietam to takiego dla dowolnej ilosci krazkow jeszcze nikt
nie odkryl?

[Przemek Biecek]

Post by nertos
Źle się zrozumieliśmy przy układaniu też wieży należy korzystać ze
wszystkich pali, a twoim sposobem to ja mogę zrobić wieże hanoi na 'n' palach.

nie napisales ze zalezy Ci na algorytmie gwarantujacym najmniejsza
liczbe krokow

ja optymalnego rozwiazania nie znam,
,,standardowe'' rozwiazanie (zdejmij ile sie da klockow, przenies
kolejny na upatrzony pal, przeniesc znow ile sie da klockow) mozna
przyspieszyc wykorzystujac w kazdym kroku wszystkie n-1 pali do
przekladania tych ,,ilu sie da'' (metnie opisane, ale jak na kartce
sobie rozrysujesz jakis prosty przyklad to zobaczysz o co chodzi)

Przemek

[Antek Laczkowski]

Post by nertos

Post by Maciek
Skoro na trzech jest normalne, to wybierz dowolne
trzy pale z danych czterech, i rozwiąż zadanie na
nich. Wystarczy do fazy, gdy jeden z nich zostaje
pusty. W tym momencie usuwasz z dalszych rozwazań
opróżniony pal, za to dołączasz czwarty - i znowu
masz zadanie na trzech palach, czyli "normalne".
Maciek

Źle się zrozumieliśmy przy układaniu też wieży należy korzystać ze
wszystkich pali, a twoim sposobem to ja mogę zrobić wieże hanoi na 'n' palach.

Oczywiście, że możesz. Pytanie, czy dołączenie dodatkowych pali
zmniejszy liczbę koniecznych ruchów. Rekurencyjna metoda
Maćka nic o tym nie mówi, może sformułujmy jedno z 2 zadań:
(oba dla n pali)
1) przełożyć krążki z pala #1 na konkretny pal #n.
2) j/w na pal #k; 1<k<=n
1) i 2) są identyczne, bo pale możesz przenumerować.
Dodajmy warunek, że każdy z pali musi być użyty.
Pytanie: czy wprowadzenie dodatkowych pali
przyspiesza rozwiązanie ? Czy odwrotnie -
wymóg użycia wszystkich pali zwiększa ilość
potrzebnych przesunięć krążków Hanoi ?
Spróbuj jakieś 4-5 krążków na 4 palach.
Antek

[A.L.]

On 18 Jul 2005 07:00:01 GMT, nertos

Post by nertos
Witam!
Czy znacie może jakąś stronę albo książkę gdzie będzie opisane jak
napisać program w c/c++ wieży hanoi na 4 palach. Na 3 palach to jest
normalnie ale na 4 to jest sztuka.
THX za wszelką pomoc

Patrz

http://www.exocortex.org/toh/

Dokladny algorytm i odnosniki do literatury sa tutaj

http://www.scs.carleton.ca/research/tech_reports/2004/TR-04-10.pdf

Na googlu nazezy szkuac pod haslem: hanoi tower 4-peg

A.L.

[studnentka infy]

Post by nertos
Witam!
Czy znacie może jakąś stronę albo książkę gdzie będzie opisane jak
napisać program w c/c++ wieży hanoi na 4 palach. Na 3 palach to jest
normalnie ale na 4 to jest sztuka.
Ja musialam w Adzie napisac dla 3, 4 i 5 oraz dla n-pali.

Spox - udalo sie i zaliczylam na 5 ;)