Rješavanje rekurzivnih algoritama koristeći stog
1.Kod problema Hanojevih tornjeva potrebno je napraviti rekurzivni algoritam i algoritam za stog, te algoritam koji će prevoditi iz jednog u drugi i obratno. Moj problem je shvaćanje što je to algoritam za stog (engl. stack)?
Opis Hanojevih tornjeva: imamo tri štapa, na jednom se nalaze n diskova različitih veličina od najvećeg k najmanjem i treba ih prebaciti na treći štap pomoću drugog uz uvjet da ne može veći disk ići na manji.
Pretpostavljam da
- rekurzivni algoritam prebacuje n-1 disk na pomoćni - drugi štap, da bi n-ti disk prebacili na ciljni - treći štap
!!!Sada znam djelomičan odgovor! Pogledaj dolje od 02. 06. 2005.!!!
2.Algoritam moram napraviti u programu mathematica i napravio sam takav algoritam da mi daje opis s kojeg na koji štap idem, te broj optimalnih poteza potrebnih da se to učini. Volio bih prikazati to u grafici ako je moguće.
Pozdrav
02.06.2005
Formalna pravila za uklanjanje rekurzije:
1. Na početku funkcije umetne se deklaracija stoga, inicijalno praznog. Stog služi za pohranu svih podataka vezanih uz rekurzivni poziv: argumenata, vrijednosti funkcije, povratne adrese
2. Prva izvršna naredba dobije oznaku L1.
Svaki rekurzivni poziv zamijenjen je naredbama koje obavljaju sljedeće:
3. Pohrani na stog vrijednosti svih argumenata i lokalnih varijabli.
4. Kreiraj i-tu novu oznaku naredbe Li i pohrani i na stog. Vrijednost i će se koristiti za izračun povratne adrese. U pravilu 7. je opisano gdje se u programu smješta ta oznaka.
5. Izračunaj vrijednosti argumenata ovog poziva i pridruži ih odgovarajućim formalnim argumentima.
6. Umetni bezuvjetni skok na početak funkcije
7. Oznaku kreiranu u točki 4. pridruži naredbi koja uzima vrijednost funkcije s vrha stoga. Dodaj programski kod koji tu vrijednost koristi na način opisan rekurzijom.
Ovime su uklonjeni svi rekurzivni pozivi. Umjesto svake naredbe r e t u r n dolazi:
8. Ako je stog prazan, obavi mormalnu naredbu r e t u r n.
9. Inače, uzmi vrijednost svih izlaznih argumenata i stavi ih na vrh stoga.
10. Odstrani sa stoga povratnu adresu ako je bila stavljena, i pohrani je u neku vraijablu.
11. Uzmi sa stoga vrijednosti za sve lokalne varijable i argumenta.
12. Umetni naredbe za izračun izraza koji slijedi neposredno iza naredbe r e t u r n pohrani rezultat na stog.
13. Idi na naredbu s oznakom povratne adrese.
U ovom primjeru u C++, tražimo riješenje rekurzivno, a zatim uklonjamo tu rekurziju prema ovih 13 pravila. Ta pravila prevode rekurzivni algoritam u algoritam za stog.
TRAŽENJE NAJVEĆEG ČLANA U POLJU
Određivanje indeksa najvećeg člana u polju od n članova može se riješiti rekurzivno:
int maxclan (int A[], int i, int n) {
int imax;
if (i >= n-1) return n-1;
imax = maxclan (A, i + 1, n);
if (A > A[imax]) return i;
return imax;
Nije zadovoljen princip strukturiranog programiranja da iz nekog modula vodi samo jedan izlaz! Strukturirano:
#include <stdio.h>
#include <conio.h>
#define MAXA 10
int maxclanl (int A[ ], int i, int n) {
int imax, k;
printf("i=%d, n=%d\n", i, n);
if (i < n-1) {
imax = maxclanl (A, i + 1, n);
if (A > A[imax])
k = i;
else
k = imax;
printf("i=%d, imax=%d, A=%d, A[imax]=%d, k=%d\n",
i, imax, Ali], A[imax), k) ;
} else {
k = n-1;
printf("Vraćam se s k=%d\n", k);
}
printf("i=%d, A=%d, k=%d\n", i, A, k) ;
return k;
}
void main () {
int A[MAXA], n;
FILE *fi;
int i, j;
fi = fopen ("ulaz1", "r");
if (!fi) exit (0);
n = 0;
while (n < MAXA && fscanf (fi, "%d", &A[n]) != EOF)
n++
for (j=0; j < n; j++) printf("%d. elan je %d\n",j, A[j]);
i = maxclanl(A, 0, n);
printf("Najveći clan %d'je na %d. mjestu\n", A, i);
fclose (fi);
Podaci: 70,131,92 ,123,44; (n=5)
poziv: maxclanl (A, 0, n);
i imax A A[imax] k
0
1
2
3
4 4
3 4 12 4 3
2 3 9 12 3
1 3 13 12 1
0 1 7 13 1
Uklanjanje rekurzije u strukturiranom programu za traženje indeksa najvećeg člana u polju, prema pravilima:
#include <stdio.h>
#define MAXA 10
int maxclan2 (int A[ ], int i, int n) {
int imax, k, adresa, vrh, *stog;
stog = (int *) malloc (2 * n * sizeof(int)) ;
vrh = -1; //Pravilo 1
L1: //Pravilo 2
if (i < n-1) {
vrh++; stog[vrh] = i; //Pravilo 3
vrh++; stog[vrh] = 2; //Pravilo 4
i++; //Pravilo 5
goto L1; //Pravilo 6
L2: //Pravilo 7
imax = stog[vrh]; vrh--;
if (A > A[imax] ) {
k = i;
} else {
k = imax ;
}
} else {
k = n-1;
}
if (vrh = = -1) { //Pravilo 8
free (stog);
return k;
} else { //Pravilo 9
adresa = stog[vrh]; vrh --; //Pravilo 10
i = stog[vrh]; vrh --; //Pravilo 11
vrh++; stog[vrh] = k ; //Pravilo 12
if (adresa= =2)goto L2; //Pravilo 13
}
}
void main () {
int A[MAXA], n;
FILE *fi;
int i, j;
fi = fopen ("ulazi", "r");
if (!fi) exit (0) ;
n = 0;
while(n < MAXA && fscanf(fi,"%d", &A[n]) != EOF) n++;
for (j=0; j < n; j++) printf("%d. clan je %d\n", j, A[j] );
i = maxclan2 (A, 0, n) ;
printf("Najveći clan %d je na %d . mjestu\n", A, i);
fclose (fi);
}
Doslovnom primjenom pravila dobije se nerekurzivni progam koji je semantički jednak rekurzivno. Ako ga se analizira, u konkretnom slučaju moguća su pojednostavnjenja.
Na stogu nije potrebno pohraniti povratnu adresu jer postoji samo jedno mjesto na koje se procedura vraća. Ostaje za pohranu samo vrijednost funkcije. U istom času postoji samo jedna vrijednost funkcije, tj. Indeks člana s maksimalnom vrijednosti. Prema tome tu vrijednost može se pohraniti u običnu varijeblu i tako ukloniti stog. Ukloni se naredba goto LI zamijanivši je petljom while. Varijabla i se postavi na n-1, a u varijabli imax se pohrani trenutni indeks maksimalnog člana.
Tip maxclan3 (tip A[], int n){
int i, imax;
i = n-1;
imax = n-1;
while (i > 0) {
i--;
if (A > A[imax]) imas =i;
}
return imax;
}
ili samo za n>0 (za n==0 daje neispravan rezultat):
tip maxclan4 (tip A[], int n) {
int i, imax = 0;
for (i = 1; i<n; i++) if (A > A[imax]) imax = i;
return imax;
}
Ako je poziv rekurzivne funkcije na kraju, umjesto poziva navedu se naredbe za izračun i slijedi bezuvjetni skok na početak.
Primjer za Euklidov algoritam tj. postupak za pronalaženje najveće zajedničke mjere dva nenegativna cijela broja:
ako je b=0
nzm=a
inače
nzm=najvećazajednička mjera od b i ostatka dijeljenja a sa b
Prikazano rekurzivno:
#include <stdio.h>
#include <conio.h>
int nzm (int a, int b) b
if(b = =0) return a;
return nzm (b, a% b);
}
void main () {
int a, b, nz;
while (1) {
prinf ("Upisite 2 cijela nenegativna broja >");
scanf ("%d %d", &a, &b);
if ((a < 0 | | b < 0) | | (a = = 0 && b = = 0)) {
printf( "Gotovo!\n" );
exit (0);
}
nz = nzm(a,b);
printf ( "Najveca zajednicka mjera brojeva %d i %d je %d\n", a, b, nz);
}
}
Sada umjesto poziva rekurzivne funkcije na kraju navodi se naredba za iračun i slijedi bezuvjetni skok na početak.
int nzm1(int a, int b) {
int t;
L1:
if(b = = 0) return a;
t=b;
b=a%b;
a=t;
goto L1;
}
Izbjegavanjem goto:
int nzm2 (int a, int b) {
int t;
while (b != 0) {
t = b;
b = a&b;
a = t;
}
return a;
}
Napomena: program funkcionira samo za nenegativne brojeve od kojih barem jedan mora biti i pozitivan. Postoji ograničenje i s gornje strane zbog ograničene veličine najvećeg cijlog broja tipa i n t. Ako se taj tip prikazuje s pomoću 2 By, onda je ta granica 32767.
Pomoću ovih 13 pravila, u slijedećem primjeru za rekurzivni algoritam tornjeva Hanoje, trebamo ukloniti tu rekurziju. Kako?
Rekurzivni algoritam za Tornjeve Hanoje:
Procedura Prebaci(n, A, B)
Ako je n = = 1 prebaci element s A na B
U suprotnom
Prebaci(n-1, A, C)
Prebaci(1, A, B)
Prebaci(n-1,C,B)
[Ovu poruku je menjao mijic dana 02.06.2005. u 21:02 GMT+1]
 |  |
 |
Re: Rješavanje rekurzivnih algoritama koristeći stog