Vodič · Algoritmi · Rekurzija i bektreking
Rekurzija i bektreking – vodič kroz lekcije
Rekurzija je tehnika u kojoj funkcija rešava problem tako što poziva samu sebe za manji problem. Na njoj se zasnivaju bektreking, pretraga grafova, „podeli pa vladaj“ i dinamičko programiranje.
Vodič ide od prvog rekurzivnog programa, preko klasičnih primera, do bektrekinga i generisanja svih rasporeda. Sve lekcije imaju zadatke sa rešenjima u C++-u.
- 7–8. razred i srednja škola
- C++
- Priprema za takmičenja
1 Osnove rekurzije
Šta je rekurzija, bazni slučaj, stek poziva i klasični primeri iz matematike.
Uvod u rekurziju
Bazni slučaj, rekurzivni korak, stek poziva, rekurzija ili petlja.
Otvori lekciju →Faktorijel, stepen i NZD
Faktorijel, brzo stepenovanje, Euklidov algoritam, Fibonači i broj poziva.
Otvori lekciju →Rekurzivni algoritmi
Stepen, Fibonači, binarni zapis, determinanta i inverzna matrica.
Otvori lekciju →Hanojske kule
Klasičan rekurzivni problem i 2ⁿ − 1 poteza.
Otvori lekciju →2 Bektreking i generisanje
Sistematsko isprobavanje mogućnosti sa vraćanjem: rasporedi, podskupovi, slagalice.
Bektreking
Šablon izaberi–istraži–poništi, podskupovi sa zbirom, N dama, lavirint.
Otvori lekciju →Permutacije i kombinacije
Generisanje permutacija, kombinacija, varijacija i podskupova; next_permutation.
Otvori lekciju →Sudoku rešavač
Kompletan rešavač i ubrzanje izborom polja sa najmanje mogućnosti.
Otvori lekciju →3 Zadaci za vežbu
Zbirke zadataka iz rekurzije i bektrekinga sa rešenjima.
Rekurzivni algoritmi – primeri
Zadaci koji se rešavaju rekurzijom.
Otvori lekciju →Bektreking i gruba sila – zadaci
N dama, Sudoku, lavirint i drugi zadaci sa rešenjima.
Otvori lekciju →Kombinatorni problemi – primeri
Generisanje varijacija, podskupova i permutacija.
Otvori lekciju →N kraljica – rešenje
Detaljno rešenje sa ispisom rasporeda.
Otvori lekciju →4 Šta dalje
Kada rekurzija počne da računa iste stvari mnogo puta, prelazi se na dinamičko programiranje.
Predloženi redosled
- Uvod u rekurziju
- Faktorijel, stepen i NZD
- Rekurzivni algoritmi
- Hanojske kule
- Bektreking
- Permutacije i kombinacije
- Sudoku rešavač
- Zadaci: bektreking i gruba sila
Korisni spoljni resursi
- Petlja – zbirke zadataka sa automatskom proverom (na srpskom)
- CSES Problem Set – odeljak „Introductory Problems“ (Permutations, Chessboard and Queens, Grid Paths)
- C++ Tutor – izvršavanje rekurzije korak po korak, sa prikazom steka poziva