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 ~~~~~~~~~~~~~~~~~~
            ~~~~~~~~~~~~~~~~~~
            ~~~~~~~~~~~~~~~~~~

Aktualny PageRank strony chemeng.p.lodz.pl/zylla/games/ dostarcza: Google-Pagerank.pl - Pozycjonowanie + SEO