hanoi, uklanjanje rekurzije

hanoi, uklanjanje rekurzije 10.03.2006. u 15:08 · pre 251 mesec #1

Cao,
imam jedan mali problemcic. Zadatak je isprogramirati hanojske kule ali sa ogranicenjem da se ne moze vrsiti direktno prebacivanje sa prvog na drugi stap.
I isprogramirala sam.
Iduci dio je ukloniti rekurziju. Ja imam tri rekurzivna poziva. Uklonila sam dvije, ali onu trecu ne mogu nikako. Ne znam sta da radim sa njom. Molim za vasu pomoc.

Inace, programiranje je vrseno u C++.

stack<int> s;
X: while (N!=0) {

Hanoi(N-1,A,B);
cout<<"Sa "<<A<<" na "<<A+B<<endl;

s.push(N); s.push(A); s.push(B);
N--;pom=B;B=A;A=pom;
goto X;

}
if(!s.empty()) {
B=s.top(); s.pop();
A=s.top(); s.pop();
N=s.top(); s.pop();
cout<<"Sa "<<A+B<<" na "<<B<<endl;
N--;
goto X;
}
}

Re: hanoi, uklanjanje rekurzije 10.03.2006. u 16:14 · pre 251 mesec #2

offtopic: nemoj toliko koristiti goto naredbu ... u stvari, izbegavaj da je koristis, jer sve to si mogla i bez nje cisto i lepo :)

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Re: hanoi, uklanjanje rekurzije 10.03.2006. u 16:55 · pre 251 mesec #3

Dobro, hvala,
to je drugi dio zadatka. Ukloniti go to naredbe.
Medjutim to i dalje ne rješava moj problem kako ukloniti onaj prvi poziv rekurzije.

Re: hanoi, uklanjanje rekurzije 11.03.2006. u 11:44 · pre 251 mesec #4

U stvari mi nije jasno stavljanje povratne adrese na stack, sto ovdje vjerovatno trebam ciniti. Moze li mi neko detaljnije objasniti kako se to radi?

Re: hanoi, uklanjanje rekurzije 13.06.2006. u 17:03 · pre 248 meseci #5

EVO RESENJJA

mala napomena.
kod je pisan u MODULA2 jeziku koa sto vidis sintaksa naredbi je veoma slicna turbo paskalu.... Nadam se da to nije ptoblem. U svakom slucaju ideja se vidi.
Malo cu iskomentarisati kod. Bar ono sto je specificno za modulu...

MODULE Okt296_1;

FROM UniStack IMPORT Stack, MakeStack, MakeNull, Empty, Push, Pop;(* uvoz procedura iz nekog modula za rad sa stekom*)
FROM IO IMPORT WrStr, WrInt, WrLn; (*uvoz procedura za ispis*)

PROCEDURE Han(n,a,b,c: INTEGER);(*originalna rekurzivna procedura, dakle polazni problem*)
BEGIN
IF n=1 THEN
WrInt(a,10); WrInt(b,10); WrLn;
ELSE
Han(n-1,a,c,b);
Han(1,a,b,c);
Han(n-1,c,b,a)
END
END Han;

TYPE LocalV = RECORD
n,a,b,c,callid: INTEGER;
END;

PROCEDURE HanI(nn,aa,bb,cc: INTEGER);(*nerekurzivno resenje*)
VAR s: Stack;
lv: LocalV;
tmp: INTEGER;
BEGIN
MakeStack(s,SIZE(lv),TRUE);
lv.n:=nn; lv.a:=aa; lv.b:=bb; lv.c:=cc; lv.callid:=0;
Push(s,lv);
WITH lv DO
REPEAT
CASE callid OF
0: IF n=1 THEN
WrInt(a,10); WrInt(b,10); WrLn;
Pop(s,lv);
ELSE
callid:=1;
Push(s,lv);
DEC(n); tmp:=b; b:=c; c:=tmp; callid:=0;
END; |
1: callid:=2;
Push(s,lv);
n:=1; callid:=0; |
2: callid:=3;
Push(s,lv);
DEC(n); tmp:=a; a:=c; c:=tmp; callid:=0; |
3: Pop(s,lv); |
END
UNTIL Empty(s);
END (* WITH *)
END HanI;(*kraj nerekurzivne procedure*)

VAR n: INTEGER;

BEGIN(*telo glavnog programa*)
n:=3;
WrStr('Rezultat rekurzivne procedure je:'); WrLn; Han(n,1,2,3); WrLn;
WrStr('Rezultat iterativne procedure je:'); WrLn; HanI(n,1,2,3); WrLn;
END Okt296_1.

ps. nadam se da ti je pomoglo.

Ovaj problem mozes resiti i sa 2 petlje. REPEAT petljom unutar jedne WHILE petlje (dakle bez CASE).
.....

Forum kao aplikacija na telefonu

Srodne teme