Date: Sat, 31 Mar 2001 21:54:38 -0100 To: "michal r" < joytek @ polbox.com > From: Romek < zylla @ p.lodz.pl > Subject: Re: At 12:15 3/31/2001 +0200, you wrote: >mam problem jestem poczatkujacym programista C >zupelne podstawy c > >czytam ksiazke rozwiazuje zadania i zatrzymalem sie na wiezy hanoi >niewiem jak zaprogramowac ten problem > >bardzo prosze o pomoc >z powazaniem michal z gdyni Problem wieży Hanoi to problem rekurencji wyobraź sobie jak byś rozwiązał (algorytmicznie) ten problem jako człowiek, a potem to samo napisz w C ;) ponumerujmy krążki cyframi od góry: [1] | | [ 2 ] | | [ 3 ] | | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 1 2 3 Na razie nie martw się jak przenieść kilka krążków; przyjmij, że twoja procedura będzie to potrafić :) Podziel problem na kilka etapów: 1. przenieś krążki 1/2 z palika 1 na palik 2 | [1] | | [ 2 ] | [ 3 ] | | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 2. przenieś krążek 3 na palik 3 | [1] | | [ 2 ] | | | [ 3 ] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 3. przenieś krążki 1/2 z palika 2 na palik 3 | | [1] | | [ 2 ] | | [ 3 ] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Cały problem przeniesienia N krążków z palika 1 na palik 3 składa się z trzech kawałków. 1. przenieś (N-1) górnych krążków z palika źródłowego na palik pośredni 2. przenieś N-ty krążek na palik docelowy 3. przenieś (N-1) górnych krążków z palika pośredniego na palik docelowy. Zauważ, że etap 1 jest wywołaniem tej samej procedury opisanej w punktach 1, 2 i 3 tyle że dotyczy N-1 krążków i palikiem docelowym jest palik pośredni. Zauważ, że etap 3 jest wywołaniem tej samej procedury opisanej w punktach 1, 2 i 3 tyle że dotyczy N-1 krążków ale tym razem palikiem docelowym jest palik docelowy. Wystarczy teraz w nagłówku procedury napisać parametry: ( skąd, dokąd, ile_krążków ) i problem prawie zrobiony. Uwaga: w procedurze musi być zabezpieczenie, które mówi że, jeśli liczba krążków do przeniesienia jest 0 to oczywiście nie należy wołać kolejny raz tej procedury. Teraz sztuczka, na która czasami ciężko wpaść. Zauważ że, jeśli: krążkiem źródłowym jest 1 a docelowym 3 to pośredni jest 2 krążkiem źródłowym jest 1 a docelowym 2 to pośredni jest 3 krążkiem źródłowym jest 2 a docelowym 3 to pośredni jest 1 krążkiem źródłowym jest 2 a docelowym 1 to pośredni jest 3 krążkiem źródłowym jest 3 a docelowym 1 to pośredni jest 2 krążkiem źródłowym jest 3 a docelowym 2 to pośredni jest 1 jaki jest algorytm wyliczania numeru palika pośredniego na podstawie numerów źródłowego i docelowego ? Pomyśl trochę i zaproponuj jakiś sprytny algorytm. Algorytm powinien być prosty i nie być dłuższy niz 3 linijki :) Jeśli nie wpadniesz na to, to zobacz na końcu listu. A propos; mój algorytm zastosowany w Wieży Hanoi w JavaScipt nie jest typowy. Jego celem było rozwiązywanie problemu mnicha, który przychodzi na kolejną zmianę do przestawiania tych krążków. Musi obejrzeć aktualny stan (położenie różnych krążków na palikach) i musi podjąć szybką decyzje który krążek w tym momencie gdzie przenieść. Algorytm był pierwotnie napisany w Basicu-ext na minikomputer MERA 400. Ten komputer miał 64 KB pamięci operacyjnej (nie 640 KB jak w starym Pececie) tylko 64. W tej pamięci mieścił się system operacyjny dla wielu użytkowników i interpreter języka BASIC. Na początku program był symulatorem pozwalającym człowiekowi klawiszami sterować kolejnymi ruchami krążków. wpisanie z klawiatury cyfr 13 oznaczało przeniesienie krążka ze szczytu palika 1 na palik 3. Program przyjmował także dłuższe serie cyfr. Na przykład kompletne przeniesienie trzech krążków z palika pierwszego na trzeci można było zrobić przez wpisanie serii cyfr 113123213212313 i naciśnięcie Enter. Oczywiście program musiał śledzić kolejne ruchy, nie pozwalać na ruchy zabronione (większy na mniejszy) i oczywiście pokazywać aktualny stan wież na terminalu tekstowym. W miarę wciągania się w problem postanowiliśmy dorobić rodzaj trybu demo, w którym komputer będzie robić ruchy za człowieka i pokazywać na ekranie animację. Animacja nie za bardzo była elegancka ale mój kolega zauważył, że kolejne ruchy układają się według pewnego schematu. Jako były perkusista amator złapał ten rytm i potrafił palcami lewej ręki stukać kolejne cyfry i jednocześnie z nami sensownie rozmawiać. :) Wieże wysokości 10 potrafił przerzucić w ciągu około 50 minut. On też próbował napisać program, który dla dowolnej wielkości wieży wygeneruje ciąg cyfr sterujących do kompletnego przerzucenia stosu. Niestety długość ciągu była (dla wysokości 10) tak długa, że nie mieściła się w pamięci operacyjnej komputera. Wtedy ja zaproponowałem zamiast rekurencyjnego rozwiązanie iteracyjne. W ten sposób nie trzeba było rekurencyjnie wywoływać funkcji lub procedury. Oczywiście z teorii algorytmów wiadomo, że każdy algorytm rekurencyjny można przekształcić w algorytm iteracyjny (ostatnio o tym przeczytałem), ale dla mnie osobiście to było moje własne odkrycie :) Napisany przeze mnie program mieścił się w pamięci i w dodatku prawidłowo mógł wyliczyć dla dowolnego ułożenia krążków ile jeszcze ruchów należy wykonać. Przez porównanie z rzeczywistą liczbą ruchów zrobionych przez człowieka można było podać ile ruchów było błędnych. W kolejnej wersji program został przepisany na BASIC dla Commodore VIC 20 (wcześniejsza wersja Commodore 64) z 16KB RAM. Program pracował już w kolorach i animacja mogła być prawie płynna mimo, że nadal to był tylko tryb tekstowy. Potem była długa przerwa. Pewnego razu surfując w internecie zauważyłem, że w JavaSkrypcie można robić podmiany obrazków. Przez odpowiednie zaprogramowanie obrazów tła i pierwszego planu można zrobić animacje. I wtedy wyciągnąłem z zabytkowej szuflady wydruk starego programu. Spotkany gdzieś w internecie algorytm zamiany obrazków przerobiłem do swoich potrzeb, procedury z BASICa przerobiłem na składnie JavaScryptu i tak powstała gra Hanoi. A teraz obiecany algorytmik: pośredni = 6 - źródłowy - docelowy; -- . __ ~~~~~~~~~~~~~~~~~~ Romek Zylla ~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~ |