Choose jour language!

---

|

BEKTREKING I GRUBA SILA- PRIMERI

Brute Force (gruba sila)

Brute force je najjednostavniji način rešavanja problema: pokušavamo sve moguće opcije ili kombinacije dok ne pronađemo rešenje. To je kao da koristimo silu da obavimo posao – ne pokušavamo nijedan specifičan pametni trik, nego testiramo svaki mogući put. Ovakav pristup je lak za razumevanje i programiranje, jer ne zahteva komplikovane algoritamske tehnike. Brute force koristimo kada imamo mali broj mogućih rešenja ili kada nam nije važna brzina programa. Na primer, ako imamo samo nekoliko mogućih kombinacija, možemo proveriti svaku od njih.

Međutim, kod većih problema brute force može postati veoma spor. Broj mogućih kombinacija brzo raste kako se veličina problema povećava, pa isprobavanje svake opcije postaje neefikasno. Brute force tada troši mnogo vremena na nepotrebne provere.

Karakteristike brute force metode:

• Proverava sve moguće kombinacije (ili rezultate) jednog problema.
• Jednostavna je za razumevanje i implementaciju.
• Dobro radi za mali broj kombinacija, ali postaje neučinkovita za veće probleme.

Primer brute force (C++)

Na primer, da pronađemo sve parove brojeva u nizu čiji zbir je jednak određenoj vrednosti (target), možemo koristiti brute force:

int arr[] = {1, 2, 3, 4};
int n = 4;
int target = 5;
// find pairs whose sum equals target
for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        if (arr[i] + arr[j] == target) {
            cout << arr[i] << " + " << arr[j] << " = " << target << endl;
        }
    }
}

Backtracking

Backtracking je naprednija metoda pretrage rešenja koja gradi moguća rešenja korak po korak. Ideja je da u svakom koraku biramo jedan element i rekurzivno nastavimo dalje. Ako u nekom trenutku shvatimo da trenutna kombinacija ne može da dovede do rešenja (npr. neki uslov nije zadovoljen), pravimo korak unazad i menjamo izbor. Na taj način izbacujemo čitave grane pretrage za koje znamo da neće dati rešenje. Ovo znatno smanjuje broj provera u odnosu na običnu brute force pretragu.

Backtracking se često koristi kod kombinatornih problema ili slagalica sa dodatnim uslovima (npr. Sudoku, N-queens). Omogućava da brzo odbacimo nepotrebne puteve i da efikasno nađemo sva rešenja. Mana je što implementacija zahteva rekurziju i može biti složenija od prostog brute force pristupa, ali značajno ubrzava pretragu kod problema sa velikim brojem mogućnosti.

Karakteristike backtracking metode:

• Koristi rekurziju i vraćanje koraka (backtracking) kada neka kombinacija ne daje rešenje.
• Odbacuje nepotrebne puteve kako bi bila efikasnija.
• Efikasniji je od čistog brute force-a kod problema sa mnogo kombinacija, ali je kod složeniji za pisanje.

Primer backtracking (C++)

Jednostavan primer backtracking-a je generisanje svih podskupova skupa brojeva:

vector arr = {1, 2, 3};
vector current;
generateSubsets(0, arr, current);  // start recursion

void generateSubsets(int idx, vector& arr, vector& current) {
    if (idx == arr.size()) {
        for (int x : current)
            cout << x << " ";
        cout << endl;
        return;
    }
    // skip arr[idx]
    generateSubsets(idx + 1, arr, current);
    // take arr[idx]
    current.push_back(arr[idx]);
    generateSubsets(idx + 1, arr, current);
    current.pop_back();
}

Brute Force vs Backtracking

I brute force i backtracking služe za pretragu svih mogućih kombinacija rešenja, ali to rade na različite načine. Brute force doslovno isprobava svaki mogući slučaj bez ikakve optimizacije. To ga čini najjednostavnijim za implementaciju, ali brzo gubi efikasnost kada se broj kombinacija poveća. Nasuprot tome, backtracking pametno prekida nepotrebne puteve čim shvati da ne vode ka rešenju. To ga čini efikasnijim za probleme sa dodatnim uslovima i velikim brojem kombinacija, mada zahteva rekurziju u implementaciji.

U praksi, brute force se koristi kada nam je važna jednostavnost rešenja ili kada je broj slučajeva stvarno mali. Backtracking koristimo kada želimo da ubrzamo pretragu velikog prostora rešenja i možemo lako da detektujemo neuspešne puteve. Na primer, kod rešavanja sudoku slagalice, backtracking će se vratiti na prethodni korak čim detektuje da neki broj ne može da se postavi, dok bi brute force nastavio da isprobava sve druge kombinacije bez prekida.

• Brute force: Jednostavna implementacija, isprobava sve mogućnosti, ali može biti veoma spora za veće probleme.
• Backtracking: Rekurzivna metoda koja odbacuje nepotrebne puteve, efikasnija za kombinatorne probleme sa puno uslova, ali kod je složeniji za pisanje.

1. Put kroz lavirint

Napisati program koji ispituje da li se u pravougaonom lavirintu može stići od gornjeg levog do donjeg desnog ugla.

Ulaz:
Sa standardnog ulaza se učitavaju dimenzije lavirinta m i n razdvojene razmakom, a zatim m redova po n znakova. Polja kroz koja se može proći su označena karakterom ., a prepreke karakterom x.

Izlaz:
Ispisati da ako put postoji, odnosno ne ako put ne postoji.

Primer 1:

Ulaz
8 8
.x.....x
.x.x.x.x
.x.x.x.x
.x.x.x.x
.x.x.x.x
.x.x.x.x
.x.x.x.x
...x.x..
Izlaz
da
  

Primer 2:

Ulaz
8 8
.x..x..x
.x.x.x.x
.x.x.x.x
.x.x.x.x
.x...x.x
.x.x.x.x
.x.x.x.x
...x.x..
Izlaz
ne
  

Prikaži uputstvo Prikaži rešenje

Uputstvo za rešavanje:

1. Pročitaj m i n, pa magistruj matricu grid dimenzija m×n.
2. Napraviti pomoćnu matricu visited[m][n] inicijalno sa false.
3. Implementirati rekurzivnu funkciju bool dfs(int i, int j) koja:
   • Proverava da li su (i,j) unutar granica i da je grid[i][j]=='.' i da nije već posećeno.
   • Ako je i==m-1 && j==n-1, vraća true (stigli smo do cilja).
   • Obeležava visited[i][j]=true i rekurzivno poziva samu sebe za četiri susedna polja (gore, dole, levo, desno).
   • Ako bilo koji poziv vrati true, propagira true nagore.
   • Inače vraća false.
4. U main() pozvati dfs(0,0) i na osnovu rezultata ispisati da ili ne.

Rešenje 1: jednostavan DFS

#include <bits/stdc++.h>
using namespace std;

int m, n;
vector<string> grid;
vector<vector<bool>> visited;

// Pomoćna funkcija: proverava da li postoji put od (i,j) do (m-1,n-1)
bool dfs(int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n)
        return false;
    if (grid[i][j] == 'x' || visited[i][j])
        return false;

    if (i == m-1 && j == n-1)
        return true;

    visited[i][j] = true;

    if (dfs(i+1, j)) return true;
    if (dfs(i-1, j)) return true;
    if (dfs(i, j+1)) return true;
    if (dfs(i, j-1)) return true;

    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    grid.resize(m);
    for (int i = 0; i < m; i++)
        cin >> grid[i];

    visited.assign(m, vector<bool>(n, false));

    bool postoji = dfs(0, 0);
    cout << (postoji ? "da" : "ne") << endl;
    return 0;
}
  

Rešenje 2: DFS sa backtracking-om

Ovaj primer vraća posećenost na false nakon ispitivanja svih puteva iz ćelije, kako bi se videlo i alternativne puteve.

#include <bits/stdc++.h>
using namespace std;

// Dimenzije lavirinta
int m, n;
// Sama mapa lavirinta
vector<string> lavirint;
// Matrica posećenosti
vector<vector<bool>> poseceno;

// Pravci kretanja: enum za četiri smera (narandzasta)
int di[4] = {-1, 1, 0, 0};
int dj[4] = {0, 0, -1, 1};

bool dfs(int i, int j) {
    if (i < 0 || i >= m || j < 0 || j >= n)
        return false;
    if (lavirint[i][j] == 'x' || poseceno[i][j])
        return false;

    if (i == m-1 && j == n-1)
        return true;

    poseceno[i][j] = true;

    for (int dir = 0; dir < 4; dir++) {
        int ni = i + di[dir];
        int nj = j + dj[dir];
        if (dfs(ni, nj))
            return true;
    }

    poseceno[i][j] = false;
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n;
    lavirint.resize(m);
    for (int i = 0; i < m; i++)
        cin >> lavirint[i];

    poseceno.assign(m, vector<bool>(n, false));

    bool postojiPut = dfs(0, 0);
    cout << (postojiPut ? "da\n" : "ne\n");
    return 0;
}
  

Objašnjenje

dfs(i,j) prvo proveri da li je (i,j) validna i prolazna ćelija. Ako jeste i ako je to cilj (m-1,n-1), vraća true.

Zatim obeleži tu ćeliju kao posećenu i rekurzivno pozove sebe za susedne ćelije. Ako neki od tih poziva vrati true, odmah propagira true nadole. Ako nijedan ne uspe, vrši backtracking (može da poništi oznaku posećeno) i vraća false.

Ovako implementirana DFS koristi princip backtrackinga da proba sve moguće puteve sve dok ne nađe uspešan, ili obidje ceo prostor i zaključi da puta nema.

---

2. Stepenasti nizovi

Napisati program koji ispisuje sve stepenaste nizove dužine n u leksikografskom poretku. Niz je stepenast ako počinje brojem 1 i svaki naredni element niza je ili jednak prethodnom ili za jedan veći od njega.

Ulaz:
Sa standardnog ulaza unosi se jedan ceo broj n (1 ≤ n ≤ 18).

Izlaz:
Ispisati sve stepenaste nizove dužine n, svaki u posebnom redu, elemente razdvojiti razmakom.

Primer:

Ulaz
3

Izlaz
1 1 1
1 1 2
1 2 2
1 2 3
  

Prikaži uputstvo Prikaži rešenje

Uputstvo za rešavanje:

1. Napraviti rekurzivnu funkciju koja gradi niz dužine n postepeno.
2. Prvi element mora biti 1. Za svaku narednu poziciju pokušati prvo da ponovimo poslednju vrednost, pa da je uvećamo za 1 (ako ne prelazi indeks+1).
3. Kada dođemo do pozicija == n, štampati ceo niz i vratiti se.

Rešenje: Stepenasti nizovi (rekurzija)

// #include 
// #include 
// using namespace std;

// Rekurzivna funkcija:
// n        – željena dužina niza
// trenutni – vektor u kome gradimo trenutni niz
// pozicija – indeks na kome smo sada (0-based)
// poslednji – poslednja vrednost ubačena u niz
void generisiStepenasti(int n,
    vector<int>& trenutni,
    int pozicija,
    int poslednji)
{
    if (pozicija == n) {
        for (int x : trenutni) cout << x << ' ';
        cout << '\n';
        return;
    }
    // zadrži istu vrednost
    trenutni[pozicija] = poslednji;
    generisiStepenasti(n, trenutni, pozicija+1, poslednji);

    // pokušaj vrednost +1 ako ne prelazi pravilo
    if (poslednji + 1 <= pozicija + 1) {
        trenutni[pozicija] = poslednji + 1;
        generisiStepenasti(n, trenutni, pozicija+1, poslednji+1);
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> niz(n);
    // po definiciji, prvi je 1
    niz[0] = 1;
    generisiStepenasti(n, niz, 1, 1);
    return 0;
}
      

---

3. Redosledi koraka robota

Robot je iz početnog položaja napravio a koraka nadesno i b koraka naviše (gledano na mapi), ali ne znamo kojim redom. Napisati program koji ispisuje sve moguće redoslede koraka robota. Ako postoji više od 1000 različitih redosleda, ispisati samo prvih 1000.

Ulaz:
U prvom i jedinom redu se nalaze dva cela nenegativna broja, razdvojena jednim razmakom: a (i broj koraka DESNO) i b (i broj koraka GORE), oba ≤ 100.

Izlaz:
Ispisati tražene redoslede koraka, svaki u zasebnom redu. Svaki redosled prikazati kao niz reči DESNO i GORE, razdvojenih razmakom, u leksikografskom poretku (DESNO < GORE).

Primer 1:

Ulaz
3 2

Izlaz
DESNO DESNO DESNO GORE GORE
DESNO DESNO GORE DESNO GORE
DESNO DESNO GORE GORE DESNO
DESNO GORE DESNO DESNO GORE
DESNO GORE DESNO GORE DESNO
DESNO GORE GORE DESNO DESNO
GORE DESNO DESNO DESNO GORE
GORE DESNO DESNO GORE DESNO
GORE DESNO GORE DESNO DESNO
GORE GORE DESNO DESNO DESNO
  

Primer 2:

Ulaz
0 6

Izlaz
GORE GORE GORE GORE GORE GORE
  

Prikaži uputstvo Prikaži rešenje

Uputstvo za rešavanje:

1. Koristiti rekurziju (ili backtracking) da postepeno gradimo niz od ukupno a+b koraka.
2. U svakom pozivu znamo koliko preostalih koraka DESNO (d_rem) i GORE (g_rem) smemo još da stavimo.
3. Prvo pokušati da dodamo DESNO (ako d_rem>0), zatim GORE (ako g_rem>0). Time je zagarantovan leksikografski redosled.
4. Kad d_rem==0 && g_rem==0, ispisati niz i prekinuti ako smo dostigli limit od 1000 ispisa.

Rešenje: Redosledi koraka (backtracking)

// #include <iostream>
// #include <vector>
// using namespace std;

const int MAKS_IZLAZA = 1000;   // maksimalan broj redosleda za ispis
int ispisano = 0;               // brojač već ispisanih
vector<int> redosled;      // ovde gradimo niz: 0=DESNO, 1=GORE

// Rekurzivna funkcija koja gradi i ispisuje redoslede
void pretrazi(int d_rem, int g_rem) {
    if (ispisano >= MAKS_IZLAZA) return;
    if (d_rem==0 && g_rem==0) {
        // ispisujemo trenutni
        for (int i=0; i<redosled.size(); ++i) {
            if (i) cout << ' ';
            cout << (redosled[i]==0? "DESNO":"GORE");
        }
        cout << '\n';
        ++ispisano;
        return;
    }
    // prvo DESNO (jer "DESNO" < "GORE")
    if (d_rem>0) {
        redosled.push_back(0);
        pretrazi(d_rem-1, g_rem);
        redosled.pop_back();
    }
    if (ispisano >= MAKS_IZLAZA) return;
    // zatim GORE
    if (g_rem>0) {
        redosled.push_back(1);
        pretrazi(d_rem, g_rem-1);
        redosled.pop_back();
    }
}

int main() {
    int a, b;
    cin >> a >> b;
    pretrazi(a, b);
    return 0;
}
      

---

4. Binarni nizovi bez previše ponavljanja

Binarni niz je dosadan ako se u njemu pojavljuje više od k istih cifara uzastopno. Niz je interesantan ako nije dosadan. Napisati program koji ispisuje sve interesantne binarne nizove dužine n u leksikografskom poretku.

Ulaz:
Jedan red sa dva broja n i k (1 ≤ n ≤ 20, 1 ≤ k ≤ n).

Izlaz:
Sve interesantne binarne nizove dužine n, svaki u posebnom redu, bez razmaka između cifara.

Primer:

Ulaz
3 2

Izlaz
001
010
011
100
101
110
  

Prikaži uputstvo Prikaži rešenje

Uputstvo za rešavanje:

1. Koristiti rekurzivnu funkciju generisi(i, poslednja, duzina, niz, n, k) koja popunjava poziciju i.
2. Stanje:
• poslednja – vrednost prethodnog bita (0 ili 1),
• duzina – koliko puta uzastopno se poslednja pojavila do sada.
3. Na svakoj poziciji pokušati prvo bit 0, pa 1 (tako da nizovi budu u leksikografskom redu).
4. Dodavanje istog bita dozvoljeno samo ako duzina < k; promena bita uvek resetuje duzina = 1.
5. Kad i == n, ispisati niz i vratiti se (base case).

Rešenje: Generisanje interesantnih nizova

#include <bits/stdc++.h>
using namespace std;

// Rekurzivna funkcija koja gradi niz:
//  i        – tekuca pozicija (0..n-1)
//  poslednja– vrednost prethodnog bita (0 ili 1)
//  duzina   – koliko puta uzastopno se 'poslednja' ponovila
//  niz      – vektor dužine n gde čuvamo trenutni niz
//  n, k     – duzina niza i maksimum dozvoljenih ponavljanja
void generisi(int i, int poslednja, int duzina,
              vector& niz, int n, int k) {
    if (i == n) {
        // ispisali smo ceo niz
        for (int b : niz) cout << b;
        cout << "\n";
        return;
    }
    // Pokušaj da dodamo 0
    if (poslednja != 0) {
        // menja se bit → reset dužine ponavljanja
        niz[i] = 0;
        generisi(i+1, 0, 1, niz, n, k);
    } else if (duzina < k) {
        // isti bit, ali poništavamo prevelika ponavljanja
        niz[i] = 0;
        generisi(i+1, 0, duzina+1, niz, n, k);
    }
    // Pokušaj da dodamo 1
    if (poslednja != 1) {
        niz[i] = 1;
        generisi(i+1, 1, 1, niz, n, k);
    } else if (duzina < k) {
        niz[i] = 1;
        generisi(i+1, 1, duzina+1, niz, n, k);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector niz(n);

    // Pošto leksikografski ide '0...' pa '1...', prvo startujemo sa 0, pa sa 1
    niz[0] = 0;
    generisi(1, 0, 1, niz, n, k);

    niz[0] = 1;
    generisi(1, 1, 1, niz, n, k);

    return 0;
}
      

---

5. Nizovi ispravno uparenih zagrada

Napisati program koji ispisuje sve nizove korektno uparenih zagrada, dužine n i dubine najviše d, u leksikografskom rastućem poretku.

Ulaz:
U prvom redu standardnog ulaza je paran broj n (1≤n≤30), a u drugom prirodan broj d (1≤d≤7). Zadata su tako da ukupno ima manje od 2000 rešenja.

Izlaz:
Ispisati sve tražene nizove zagrada u leksikografskom rastućem poretku, svaki u zasebnom redu.

Primer:

Ulaz
6
2

Izlaz
(()())
(())()
()(())
()()()
  

Prikaži uputstvo Prikaži rešenje

Uputstvo za rešavanje:

1. Ustanoviti da niz mora da sadrži n/2 otvarajućih i n/2 zatvarajućih zagrada.
2. Pratiti tri stanja pri generisanju:
   • otv – koliko otvorenih “(” smo stavili;
   • zat – koliko zatvorenih “)” smo stavili;
   • dub = otv − zat – trenutna dubina;
3. Rekurzivno popunjavati niz na poziciji poz:
   • dodati “(” ako otv < n/2 i dub+1 ≤ d;
   • dodati “)” ako zat < otv;
4. Prvo pokušati granu sa “(” pa zatim “)” da bi se obezbedio leksikografski poredak.
5. Prekinuti dalje grananje čim ispisanih nizova dostigne 2000.

Rešenje: Generisanje sa ograničenjem dubine

// uključujemo sve standardne zaglavlja
#include <bits/stdc++.h>
using namespace std;

// Maksimalan broj nizova (zadato < 2000)
const int MAKS_NIZOVA = 2000;

// Ukupna dužina niza (paran broj) i dozvoljena dubina
int n, d;
// Vektor za trenutno generisani niz zagrada
vector<char> niz_zagrada;
// Brojač ispisanih nizova
int ispisano = 0;

/**
 * Rekurzivna funkcija:
 * @param poz  – trenutna pozicija u nizu (0..n-1)
 * @param otv  – broj otvorenih '(' do sada
 * @param zat  – broj zatvorenih ')' do sada
 * @param dub  – trenutna dubina = otv - zat
 */
void generisi(int poz, int otv, int zat, int dub) {
    if (ispisano >= MAKS_NIZOVA) return;       // prekid ako smo već ispisali limit
    if (poz == n) {                           // ako smo popunili ceo niz
        for (char c : niz_zagrada) cout << c;
        cout << "\n";
        ++ispisano;
        return;
    }
    // Pokušaj da dodamo '(' ako nije dostignut n/2 i dubina+1 ≤ d
    if (otv < n/2 && dub+1 <= d) {
        niz_zagrada[poz] = '(';
        generisi(poz+1, otv+1, zat, dub+1);
    }
    // Pokušaj da dodamo ')' ako ima više otvorenih nego zatvorenih
    if (zat < otv) {
        niz_zagrada[poz] = ')';
        generisi(poz+1, otv, zat+1, dub-1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Učitavamo n i d
    cin >> n >> d;
    niz_zagrada.resize(n);

    // Pokrećemo rekurziju od početka niza
    generisi(0, 0, 0, 0);
    return 0;
}
/*
Objašnjenje:
- n mora biti paran (po pola '(' i ')').
- d ograničava maksimalnu razliku (otvoreni - zatvoreni) u bilo kom trenutku.
- Grana sa '(' se bira prva da bi leksikografski nizovi sa '(' redom bili pre onih sa ')'.
- Brojač ispisano sprečava prelazak 2000 rešenja.
*/
      

---