From: ala_24 @ xxx.pl
To: zylla @ 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 @ 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ą.
|