[ mijic @ 21.05.2005. 13:41 ] @
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] |