From: Doni Pracner Date: Mon, 25 May 2015 15:34:59 +0000 (+0200) Subject: Simulacija rekurzije, primeri sa prvog casa X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa1-materijali.git;a=commitdiff_plain;h=eb83afc07f85d2482f740eb600ff5da88628529c Simulacija rekurzije, primeri sa prvog casa --- diff --git a/kodovi/simulacija-rekurzije/Faktorijel.java b/kodovi/simulacija-rekurzije/Faktorijel.java new file mode 100644 index 0000000..097f2b5 --- /dev/null +++ b/kodovi/simulacija-rekurzije/Faktorijel.java @@ -0,0 +1,48 @@ +/** + * Primer veoma jednostavne rekurzivne funkcije u kojoj se pozivi linearno + * spuštaju do trivijalnog uslova i potom se direktno vraćaju do originalnog + * poziva. Pri tome ne postoje ni nikakve dodatne promenljive ili pozivi. + */ +public class Faktorijel { + + /** + * Originalna funkcija koja će biti simulirana + */ + static int faktorijelR(int n) { + if (n <= 1) + return 1; + else + return n * faktorijelR(n - 1); + } + + /** + * Simulirana verzija rekurzivne funkcije + */ + static int faktorijelS(int n) { + Stek s = new Stek(100); + + // rekurzivni pozivi do trivijalnog slučaja + while (n > 1) { + s.stavi(n); + n--; + } + + // trivijalni slučaj + int rez = 1; + + // povratak iz rekurzije + while (!s.jePrazan()) { + n = s.skiniVrh(); + rez = rez * n; + } + return rez; + } + + public static void main(String[] args) { + int n = Svetovid.in.readInt("n = ?"); + System.out.print("n! = "); + System.out.print(faktorijelR(n)); + System.out.print(" = "); + System.out.println(faktorijelS(n)); + } +} \ No newline at end of file diff --git a/kodovi/simulacija-rekurzije/Fib.java b/kodovi/simulacija-rekurzije/Fib.java new file mode 100644 index 0000000..04a48aa --- /dev/null +++ b/kodovi/simulacija-rekurzije/Fib.java @@ -0,0 +1,68 @@ +public class Fib { + + /** + * Originalna funkcija koja će biti simulirana + */ + static int fibR(int n) { + if (n <= 1) + return n; + else + return fibR(n - 1) + fibR(n - 2); + } + + private static class InfoTip { + int n, prviSab, adr; + } + + /** + * Simulirana verzija rekurzivne funkcije + */ + static int fibS(int n) { + int prviSab, rez; + InfoTip el; + Stek s = new Stek(100); + + do { + // rekurzivni spust + while (n > 1) { + el = new InfoTip(); + el.n = n; + el.adr = 1; + s.stavi(el); + n = n - 1; + } + + // trivijalni slucaj + rez = n; + + // povratak iz rekurzije + boolean nemaPoziva = true; + while (!s.jePrazan() && nemaPoziva) { + el = s.skiniVrh(); + n = el.n; + if (el.adr == 1) { + prviSab = rez; + el.n = n; + el.adr = 2; + el.prviSab = prviSab; + s.stavi(el); + n = n - 2; + nemaPoziva = false; + } else { + prviSab = el.prviSab; + rez = prviSab + rez; + } + } + + } while (!s.jePrazan()); + return rez; + } + + public static void main(String[] args) { + int n = Svetovid.in.readInt("n = ?"); + System.out.print("F(n) = "); + System.out.print(fibR(n)); + System.out.print(" = "); + System.out.println(fibS(n)); + } +} \ No newline at end of file diff --git a/kodovi/simulacija-rekurzije/Stek.java b/kodovi/simulacija-rekurzije/Stek.java new file mode 100644 index 0000000..a3e07c9 --- /dev/null +++ b/kodovi/simulacija-rekurzije/Stek.java @@ -0,0 +1,143 @@ +/** + * Tip podataka stek, koji omogućava skladištenje podataka u skladu sa principom + * "poslednji unutra, prvi napolje". + * + *

+ * Implementacija koristi niz, te je u skladu sa tim ograničena veličina steka + * koji se koristi i moguće je da će operacija za dodavanje elemenata baciti + * izuzetak ukoliko nema mesta. + *

+ * + * @version v1.0.0 + * + * @param + * Tip podataka koji će se čuvati u konkretnoj instanci steka. + */ +public class Stek { + /** + * Separator vrednosti u {@code toString} metodu: {@value} . + */ + public static final String SEPARATOR = ", "; + + // indeks prvog slobodnog elementa na steku + private int popunjeno; + + // niz u kome se skladiste elementi + private T[] elementi; + + /** + * Veličina stekova za koje nije prosledjen parametar o veličini ({@value} + * ). + */ + public static final int PODRAZUMEVANA_VELICINA = 100; + + /** + * Kreira novi Stek podrazumevane veličine {@value #PODRAZUMEVANA_VELICINA}. + */ + public Stek() { + this(PODRAZUMEVANA_VELICINA); + } + + /** + * Kreira nov Stek zadate velicine. + * + * @param n + * maksimalan broj elemenata koji će ovaj stek moći da primi. + */ + // pozeljno koristiti Suppress da kompajliranje ne prijavljuje upozorenja + @SuppressWarnings("unchecked") + public Stek(int n) { + popunjeno = 0; + elementi = (T[]) (new Object[n]); + } + + /** + * Vraća da li je stek prazan. + * + * @return da li je stek prazan + */ + public boolean jePrazan() { + return popunjeno == 0; + } + + /** + * Vraća da li je stek pun. + * + * @return da li je stek pun + */ + public boolean jePun() { + return popunjeno == elementi.length; + } + + /** + * Vraća vrednost elementa na vrhu steka. Ukoliko je stek prazan baca + * izuzetak. + * + * @return vrednost elementa na vrhu steka + */ + public T vrh() { + if (jePrazan()) { + throw new IllegalStateException("Stek je prazan"); + } else + return elementi[popunjeno - 1]; + } + + /** + * Skida element sa vrha steka i vraća ga. Ukoliko je stek prazan baca se + * izuzetak. + * + * @return vrednost elementa koji je bio na vrhu steka + */ + public T skiniVrh() { + if (jePrazan()) { + throw new IllegalStateException("Stek je prazan"); + } else + popunjeno--; + return elementi[popunjeno]; + } + + /** + * Ubacuje prosleđeni element na vrh steka. Ukoliko je stek već pun baca se + * izuzetak. + * + * @param x + * element koji će biti ubačen na vrh steka + */ + public void stavi(T x) { + if (jePun()) { + throw new IllegalStateException("Stek je pun"); + } else { + elementi[popunjeno] = x; + popunjeno++; + } + } + + /** + * Vraća String reprezentaciju ovog Steka. Reprezentacija će sadržati + * najviše 4 elementa sa steka, tačnije najviše prva dva i poslednja dva, + * razdvojenih sa {@value #SEPARATOR}, a ukoliko ima više od 4 elementa biće + * dodato i "..." između prvih i poslednjih elemenata. + */ + public String toString() { + String rez = "Stek: "; + if (jePrazan()) { + rez += "prazan"; + } else { + rez += elementi[popunjeno - 1]; + if (popunjeno > 1) { + int sledeci = popunjeno - 2; + rez += SEPARATOR + elementi[sledeci]; + if (popunjeno > 2) { + if (popunjeno > 4) { + rez += SEPARATOR + "..."; + } + if (popunjeno > 3) { + rez += SEPARATOR + elementi[1]; + } + rez += SEPARATOR + elementi[0]; + } + } + } + return rez; + } +} \ No newline at end of file diff --git a/kodovi/simulacija-rekurzije/Stepenovanje.java b/kodovi/simulacija-rekurzije/Stepenovanje.java new file mode 100644 index 0000000..7417032 --- /dev/null +++ b/kodovi/simulacija-rekurzije/Stepenovanje.java @@ -0,0 +1,76 @@ +public class Stepenovanje { + + static double kvadrat(double y) { + return y * y; + } + + /** + * Originalna funkcija koja će biti simulirana + */ + static double naStepenR(double x, int n) { + if (n <= 0) + return 1; + else if (n % 2 != 0) + return x * kvadrat(naStepenR(x, n / 2)); + else + return kvadrat(naStepenR(x, n / 2)); + } + + private static class InfoTip { + double x; + int n; + int adr; + } + + /** + * Simulirana verzija rekurzivne funkcije + */ + static double naStepenS(double x, int n) { + InfoTip el; + Stek s = new Stek(100); + + // rekurzivni silaz + while (n > 0) { + if (n % 2 != 0) { + el = new InfoTip(); + el.x = x; + el.n = n; + el.adr = 1; + s.stavi(el); + } else { + el = new InfoTip(); + el.x = x; + el.n = n; + el.adr = 2; + s.stavi(el); + } + n = n / 2; + } + + // trivijalni slucaj + double rez = 1.0; + + // povratak iz rekurzije + while (!s.jePrazan()) { + el = s.skiniVrh(); + x = el.x; + n = el.n; + if (el.adr == 1) + rez = x * kvadrat(rez); + else + rez = kvadrat(rez); + } + return rez; + } + + public static void main(String[] args) { + System.out.print("x = "); + double x = Svetovid.in.readDouble(); + System.out.print("n = "); + int n = Svetovid.in.readInt(); + System.out.print("x^n = "); + System.out.print(naStepenR(x, n)); + System.out.print(" = "); + System.out.println(naStepenS(x, n)); + } +} \ No newline at end of file