From: Doni Pracner <quinnuendo@gmail.com>
Date: Tue, 28 Nov 2017 15:06:22 +0000 (+0100)
Subject: Pretrazivanje sa vracanjem, zadatak sa ciframa
X-Git-Url: http://svarog.pmf.uns.ac.rs/gitweb/?p=spa2-materijali.git;a=commitdiff_plain;h=f64ba7b14b889375f0be6099b673649b70413f4b

Pretrazivanje sa vracanjem, zadatak sa ciframa
---

diff --git a/PretrazivanjeSaVracanjem/Cifre/Zad0.java b/PretrazivanjeSaVracanjem/Cifre/Zad0.java
new file mode 100644
index 0000000..0c9c8f2
--- /dev/null
+++ b/PretrazivanjeSaVracanjem/Cifre/Zad0.java
@@ -0,0 +1,39 @@
+
+public class Zad0 {
+    static int[] broj;
+    
+    // Konstante koje omogucavaju laku promenu resenja
+    // kakva se generisu ovim programom
+    static final int MIN_CIFRA = 0;
+    static final int MAX_CIFRA = 9;
+
+    public static void main(String[] args) {
+        // napravimo niz trazene duzine
+        // sadrzaj niza zapravo nije bitan
+        broj = new int[] {MIN_CIFRA, MIN_CIFRA, MIN_CIFRA, MIN_CIFRA};
+        sastavibroj(broj, 0);
+    }
+
+    public static void sastavibroj(int[] broj, int pozicija) {
+
+	// trivijalan slucaj - dosli smo do kraja niza
+        if (pozicija >= broj.length) {
+	    // imamo kompletno resenje, ispisujemo na ekran
+            for (int i: broj)
+                System.out.print(i);
+            System.out.println();
+            return;
+        }
+
+	// postavimo inicijalnu vrednost
+        broj[pozicija] = MIN_CIFRA;
+
+	// inace isprobavamo sve mogucnosti na ovoj poziciji
+        while (broj[pozicija] <= MAX_CIFRA) {
+	    // probamo dalja mesta
+            sastavibroj(broj, pozicija+1);
+            broj[pozicija] = broj[pozicija]+1;
+        }
+
+    }
+}
diff --git a/PretrazivanjeSaVracanjem/Cifre/_zad0-cifre.txt b/PretrazivanjeSaVracanjem/Cifre/_zad0-cifre.txt
new file mode 100755
index 0000000..b2f71a7
--- /dev/null
+++ b/PretrazivanjeSaVracanjem/Cifre/_zad0-cifre.txt
@@ -0,0 +1,53 @@
+Zadatak 0 - rekurzivno resavanje problema
+=========================================
+
+Napisati program koji ce na ekran da ispise sve brojeve sa 4 cifre, odnosno
+sve od 0000 do 9999.
+
+0000
+0001
+0002
+0003
+0004
+...
+1000
+1001
+...
+9998
+9999
+
+
+Problem resavati pretrazivanjem sa vracanjem, a ne direktno sa nekom
+petljom od 0 do 9999.
+
+
+Ideje
+-----
+
+Razmotriti kako problem opisati rekurzivno, a ne iterativno sto bi bio
+uobicajeni pristup.
+
+Problem nekako treba razbiti na rekurzivne delove. Ovde mozemo gledati
+po duzini, tj broju cifara koje treba obraditi.
+
+Na primer za sve jedncifrene brojeve je samo potrebno probati sve mogucnosti 0-9
+i svaki put ispisati to resenje.
+
+Za dve cifre je potrebno probati sve mogucnosti za tu drugu poziciju (0-9) i za
+svaku od tih mogucnosti probati sve mogucnosti za jednu cifru.
+
+Odnosno za bilo koji broj cifara, treba da isprobavamo jednu koju trenutno
+gledamo, i za svaku od tih mogucnosti generisanje svih resenja sa manjim
+brojem cifara.
+
+Kod rekurzivnog resavanja problema je uvek neophodno definisati "trivijalne"
+izlaze, tj izvrsavanja metoda u kojima nece biti novih rekurzivnih poziva.
+Bitno je da se ceo postupak u nekom momentu zavrsi.
+
+Kod ovog resavanja se to tipicno resava tako sto se rekurzivno uvek ide na
+jednu stranu (s leva na desno, ili s desna na levo), a trivijalni pozivi su
+kad se stigne na kraj niza ili "ispadne" iz njega (skroz desno, tj skroz
+levo).
+
+Povratak unazad se desava pri povratku iz rekurzije, a ne eksplicitnim
+pozivima.
\ No newline at end of file