From: ala_24 @ xxx.pl
To: zylla @ wipos.p.lodz.pl
Subject: Wieże z Hanoi
Date: Thu, 23 Mar 2006 22:12:14 +0100


Dzień dobry! 
pisze bo mam mały problem z napisaniem procedury "Wież z Hanoi"
interacyjnie.. Szukałam tego w internecie i napotkałam twoją
stronę!! Mam wielką prośbę czy mógłbyś mi zmienić poniższą
procedurę rekurencyjną na interacyjną?? Będę wdzieczna za każda
pomoc:)(przesyłam cały program)Z góry dziekuję..

program Wieze_z_Hanoi; uses Crt; const max_nr_kraz = 12; type NumeryKrazkow = 0..max_nr_kraz; palik = record nr_palika : 1..3; ile : NumeryKrazkow; krazek : array [1..max_nr_kraz] of NumeryKrazkow end; var A, B, C : palik; n, i : integer; x_palika : array [1..3] of integer; y_podstawa_palika : integer; znak : char; ile : integer; czekaj : boolean; procedure wyswietl_paliki; var i, j : integer; begin ClrScr; y_podstawa_palika := 19; x_palika[1] := 13; x_palika[2] := 40; x_palika[3] := 67; textcolor(yellow); for i := 1 to 3 do begin gotoxy(x_palika[i] - 12,y_podstawa_palika); for j := 1 to 25 do write('Ü'); end; for i := 1 to 3 do for j := y_podstawa_palika - max_nr_kraz-2 to y_podstawa_palika-1 do begin gotoxy(x_palika[i], j); write('Ű'); end; textcolor(lightgray); gotoxy (x_palika[1], y_podstawa_palika+2); write('A'); gotoxy (x_palika[2], y_podstawa_palika+2); write('B'); gotoxy (x_palika[3], y_podstawa_palika+2); write('C'); textcolor(white); gotoxy(5,24); write(' + wyswietlanie krok po kroku ', '(po nacisnieciu klawisza), '); gotoxy(5,25); write('- wyswietlanie automatyczne'); textcolor(lightgray); end; {wyswietl_paliki} procedure wyswietl_krazek (nr, y, rozmiar :integer); var i : integer; begin textcolor(rozmiar); gotoxy (x_palika[nr]-rozmiar,y_podstawa_palika-y); for i := 1 to 2*rozmiar+1 do write('Ű'); textcolor(lightgray); end; {wyswietl_krazek} procedure usun_krazek (nr, y, rozmiar : integer); var i : integer; begin textcolor(lightgray); gotoxy(x_palika[nr]-rozmiar,y_podstawa_palika-y); for i := 1 to rozmiar do write(' '); textcolor(yellow); write('Ű'); for i := 1 to rozmiar do write(' '); textcolor(lightgray); end; {usun_krazek} procedure przenies_krazek (var X, Y : palik); var krazek : NumeryKrazkow; begin if KeyPressed then begin znak := ReadKey; if ord(znak) = 0 then znak := ReadKey; end; if znak = '-' then czekaj := false; if znak = '+' then czekaj := true; if czekaj then begin znak := ReadKey; if ord(znak) = 0 then znak := ReadKey; end else delay(200); krazek := X.krazek[X.ile]; usun_krazek (X.nr_palika , X.ile, krazek); X.ile := X.ile - 1; Y.ile := Y.ile + 1; Y.krazek[Y.ile] := krazek; wyswietl_krazek (Y.nr_palika, Y.ile,krazek); ile := ile + 1; gotoxy(65,2); textcolor(lightred); write(ile:7); textcolor(lightgray); end; {przenies_krazek} procedure Hanoi ( n : integer; var A, B, C :palik); begin if n > 0 then begin Hanoi (n-1, A, C, B); przenies_krazek (A,B); Hanoi(n-1,C , B, A); end; end; {Hanoi} begin {Wieze_z_Hanoi} ile := 0; czekaj := true; textcolor(lightgray); ClrScr; znak := '+'; write(' Podaj liczbe krazkow (max ',max_nr_kraz, '): '); readln(n); A.nr_palika := 1; B.nr_palika := 2; C.nr_palika := 3; A.ile := n; B.ile := 0; C.ile := 0; wyswietl_paliki; for i := 1 to n do begin A.krazek[i] := n - i + 1; wyswietl_krazek (1, i, n-i+1); end; Hanoi(n, A, B, C); end.
========================================================================== Date: Mon, 27 Mar 2006 00:00:39 +0200 From: Romek Zylla <zylla @ wipos.p.lodz.pl> To: ala_24 @ xxx.pl Subject: Re[2]: Wieze z Hanoi Witam, No więc z algorytmem iteracyjnym wież Hanoi jest pewien kłopot nomenklaturowy :) Według pewnego twierdzenia każdy algorytm rekurencyjny można zamienić na równoważny mu algorytm iteracyjny. I z pewnością można zamienić twój algorytm na iteracyjny ale ... wielu autorów uważa za algorytm iteracyjny taki algorytm, który rozwiązuje to samo zadanie ale nie jest rekurencyjny. Zobaczmy; E.W. Dijkstra w swojej pracy z 1971 roku The Short Introduction to the Art of Programming http://www.cs.utexas.edu/~EWD/ewd03xx/EWD316.PDF albo http://www.cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD316.html#towers_of_hanoi podaje (niestety po angielsku) taki kawałek - i)znów niestety program jaki podaje jest napisany w Algolu i jak spróbowałem go przerobić na Pascal i wstawiłem do Twojego programu to nie działa prawidłowo (jako procedura wewnątrz twojego programu).
begin integer k; integer array n, from, via, to[1:2*N-1]; n[1]:= N; from[1]:=1; via[1]:=2; to[1]:=3; k:=1; repeat if n[k]= 1 then else begin n[k+2]:= n[k]-1; from[k+2]:= from[k]; via[k+2]:= to[k]; to[k+2]:= via[k]; n[k+1]:=1; from[k+1]:= from[k]; to[k+1]:=to[k]; n[k]:= n[k+2]; from[k]:= to[k+2]; via[k]:=from[k+2]; to[k]:= via[k+2]; k := k + 2 end until k = 0 end
Co ciekawe Dijkstra podaje go jako pierwszy, a potem dopiero pokazuje że jak się napisze program rekurencyjny to jest on bajecznie prosty :) Z kolei Maciej M. Sysło w swojej ksiązce "Algorytmy" (WSiP 1997) podaje dwa rozwiązania - rekurencyjne i iteracyjne, ale iteracyjne nie jest wcale przekształceniem rekurencyjnego albowiem opiera się na kilku "spostrzeżeniach" co do kolejności ruszania sie krażków. Słowny opis jego (ale został już dawno "odkryty" przez innych) algorytmu jest taki: Uwaga: Paliki A, B i C traktujemy tak, jakby były ustawione w kółko, zgodnie z ruchem wskazówek zegara, zatem dla każdego palika jest określony następny palik w tym porządku. Krok 1 Przenieś najmniejszy krążek z palika, na którym się znajduje, na następny palik. Jeśli wszystkie krążki są ułożone na jednym paliku, to zakończ algorytm. Krok 2 Wykonaj jedyne możliwe przeniesienie krążka, który nie jest najmniejszym krążkiem i wróć do kroku 1. Odpowiedni program będzie zaraz, ale najpierw uwaga: ten algorytm został opublikowany przez Raoul Olive, patrz (N. Klaus, 1884) - tak - 122 lata temu. Ten algorytm ma w tej postaci taką wadę, że dla N parzystych krążki w końcu lądują na paliku C, natomiast dla N nieparzystych lądują na paliku B. Można temu zaradzić jeśli w Kroku 1 ruch wykona się odwrotnie do kierunku wskazówek zegara. Ale o tym Sysło nie wspomina. Poniżej jego implementacja algorytmu "iteracyjnego"
procedure HanoiIter(n:integer); {Iteracyjne rozwiazanie zagadki Wiez Hanoi, p.8.2.1. W programie glownym nalezy zdefiniowac typ danych: Tablica0n13 = array[0..n,1..3] of integer. } var i,j,k,Maly:integer; Gora :array[1..3] of integer; A :Tablica0n13; procedure Przenies(Z,Na:integer); {Przeniesienie krazka z palika Z na palik Na.} begin writeln('Przenies ',A[Gora[Z],Z],' z ',Z,' na ',Na); Gora[Na]:=Gora[Na]+1; A[Gora[Na],Na]:=A[Gora[Z],Z]; Gora[Z] :=Gora[Z] -1 end; {Przenies} begin for i:=n downto 1 do A[n-i+1,1]:=i; Gora[1]:=n; for i:=1 to 3 do A[0,i]:=n+1; Gora[2]:=0; Gora[3]:=0; Maly:=1; repeat i:=Maly+1; if i>3 then i:=i-3; Przenies(Maly,i); Maly:=i; if Gora[i]<>n then begin {Krok 2 algorytmu.} j:=i+1; if j>3 then j:=j-3; k:=i+2; if k>3 then k:=k-3; if A[Gora[j],j]<A[Gora[k],k] then Przenies(j,k) else Przenies(k,j) end {Koniec Kroku 2.} until (Gora[1]=n) or (Gora[2]=n) or (Gora[3]=n) end; {HanoiIter}
powodzenia i napisz jak ostatecznie rozwiązałaś to zadanie i na jaka ocenę :) ================================================================= Algorytm Dijkstry po przeróbce na paskal działa ale generuje ciag symboli typu AC AB BC i nie można go poprostu wstawić do twojego programu zamiast twojej procedury. Troche twój program poprzerabialem i jeszcze troche przerobię to się będzie nadawał do podmiany. Na moje oko to struktury danych jakie zastosowałaś trochę nie pasują do problemu i stąd kłopot w przeróbce. Poniżej przerobiony Twój program z przerobionymi strukturami danych i wmontowanym algorytmem iteracyjnym według Dijkstry.
program WiezeHanoi_iteracyjne; { E.W.Dijkstra "A Short Introduction to the Art of Programming" http://www.cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD316.html } uses CRT; const Nmax = 12; type str80 = string[80]; const x_palika : array [1..3] of integer=(13,40,67); y_podstawa : integer=19; var uklad : array[1..Nmax+1,1..3] of integer; wys : array[1..3] of integer; N, i, ile, krazek : integer; znak : char; czekaj : Boolean; procedure WriteXY( x, y:byte; sss : str80 ); begin GotoXY(x,y); write( sss ); end; function MulStr( nn: integer; sss:str80):str80; var ii:integer; ss:str80; begin ss:=''; for ii:= 1 to nn do ss:= ss + sss; MulStr:= ss; end; procedure WyswietlPlansze; var i, j : integer; begin ClrScr; TextColor(yellow); for i := 1 to 3 do WriteXY(x_palika[i] - 12, y_podstawa, MulStr( 25, #220) ); for i := 1 to 3 do for j := y_podstawa -Nmax-2 to y_podstawa do WriteXY(x_palika[i], j, #219); TextColor(LightGray); writeXY(x_palika[1], y_podstawa+2, 'A'); writeXY(x_palika[2], y_podstawa+2, 'B'); writeXY(x_palika[3], y_podstawa+2, 'C'); TextColor(white); writeXY(5,24,' + wyswietlanie krok po kroku (po nacisnieciu klawisza),'); writeXY(5,25,' - wyswietlanie automatyczne'); TextColor(LightGray); end; {wyswietl_paliki} procedure WyswietlKrazek (x, y, rozmiar : integer); begin TextColor(rozmiar mod 2 + 1); WriteXY( x_palika[x]-rozmiar, y_podstawa-y, MulStr( 2*rozmiar+1, #219) ); TextColor(LightGray); end; {wyswietl_krazek} procedure UsunKrazek (x, y : integer); begin gotoXY(13,1); write( 'usun:', x:3,y:3 ); krazek := uklad[wys[x],x]; TextColor(LightGray); writeXY( x_palika[x]-krazek, y_podstawa -y, MulStr(2*krazek+1,' ')); TextColor(yellow); writeXY( x_palika[x], y_podstawa -y, #219 ); TextColor(LightGray); uklad[wys[x],x] := 0; wys[x] := wys[x] - 1; end; {usun_krazek} procedure PrzeniesKrazek ( X, Y : integer ); begin gotoXY(1,1); write( X:3,#32#26,Y:2 ); if KeyPressed then begin znak:= ReadKey; if (znak = #0) then znak:= ReadKey; end; if znak = '-' then czekaj:= false; if znak = '+' then czekaj:= true; if czekaj then begin znak:= ReadKey; if (znak = #0) then znak:= ReadKey; end; Delay(200); krazek := uklad[wys[X],X]; UsunKrazek(X, wys[X] ); wys[Y] := wys[Y] + 1; uklad[wys[Y],Y] := krazek; WyswietlKrazek (Y, wys[Y], krazek); ile := ile + 1; TextColor(LightRed); GotoXY(65,2); write(ile:7); TextColor(LightGray); end; {przenies_krazek} (* procedure Hanoi ( n : integer; var A, B, C : palik); begin if n > 0 then begin Hanoi(n-1, A, C, B); PrzeniesKrazek( A, B ); Hanoi(n-1, C, B, A); end; end; {proc Hanoi} *) procedure Hanoi2( N:integer; A,B,C: integer ); var k : integer; nr, from, via, nato : array[1..2*Nmax-1] of integer; const kod : string[3]='ABC'; begin FillChar(nr, SizeOf(nr ),0); FillChar(from,SizeOf(from),0); via := from; nato:= from; nr[1]:= N; from[1]:= A; via[1]:= B; nato[1]:= C; k := 1; repeat if (nr[k] = 1) then begin PrzeniesKrazek( from[k], nato[k] ); { write( kod[from[k].nr_palika],#26, kod[nato[k].nr_palika],' '); } k:= k - 1; end else begin nr [k+2]:= nr[k]-1; from[k+2]:= from[ k ]; via[k+2]:= nato[k]; nato[k+2]:= via [ k ]; nr [k+1]:= 1; from[k+1]:= from[ k ]; nato[k+1]:= nato[k]; nr [ k ]:= nr[k+2]; from[ k ]:= nato[k+2]; via[ k ]:= from[k+2]; nato[ k ]:= via [k+2]; k := k + 2 end until (k = 0) end; begin {Wieze_Hanoi} ile := 0; czekaj := true; FillChar( uklad, SizeOf(uklad), 0); TextColor(LightGray); write(' '); ClrScr; znak := '+'; write(' Podaj liczbę krążków (max ', Nmax, '): '); repeat readln( N ); until (N>=1) AND (N<=Nmax); wys[1]:= N; wys[2]:=0; wys[3]:=0; WyswietlPlansze; for i:=1 to N do begin uklad[i,1]:= N+1-i; WyswietlKrazek( 1, i, N+1-i ); end; GotoXY(1,22); Hanoi2( N, 1, 2, 3 ); GotoXY(1,25); ClrEol; GotoXY(1,24); ClrEol; TextAttr:=$31; ClrEol; write(' Naciśnij Enter by zakończyć '); repeat until KeyPressed; znak:= ReadKey; if (znak = #0) then znak:= ReadKey; TextAttr:=07; write(' '); end.
-- pozdrawiam, Romek

Jakiś czas po tej korespondencji natrafiłem na wykład z informatyki na temat procedur rekurencyjnych i iteracyjnych autorstwa K. Molendy z WSEI. Jest tam ładny teoretyczny i praktyczny wykład o zamianie rekurencyjnej procedury Wieży Hanoi na procedurę iteracyjną.