Vodič · Primeri algoritama

Primeri algoritama – vodič kroz zadatke

Zadaci u kojima nije dovoljno samo „napisati program“, već treba smisliti dobar postupak: matematički algoritmi, ubrzanje programa formulom, rekurzija, generisanje kombinatornih objekata i pretraga sa vraćanjem (bektreking).

Pre ovih zadataka treba da sigurno rešavaš zadatke iz osnovnih primera – posebno petlje, nizove i funkcije.

  • 7–8. razred i srednja škola
  • C++
  • Priprema za okružno i državno takmičenje
Saveti: pre pisanja koda proceni koliko operacija program radi za najveći ulaz iz ograničenja. Oko 108 jednostavnih operacija je otprilike sekunda – ako je tvoj postupak sporiji, traži formulu ili bolji algoritam.

1 Matematički algoritmi i složenost

NZD i NZS, prosti brojevi, faktorizacija i kako sporu petlju zameniti formulom.

Algoritmi: NZD i prosti brojevi

Faktorizacija, parovi prostih brojeva, duplikati, bar-kodovi.

Otvori lekciju →

Poboljšanje složenosti

Aritmetički trougao, nedostajući broj, podstringovi.

Otvori lekciju →

2 Rekurzija

Funkcija koja poziva samu sebe: stepen, Fibonačijev niz, binarni zapis, inverzna matrica.

Rekurzivni algoritmi

Rekurzivno rešavanje i brzo stepenovanje.

Otvori lekciju →

3 Kombinatorika i bektreking

Kako sistematski nabrojati sve mogućnosti i kako odbaciti one koje ne vode rešenju.

Kombinatorni problemi

Varijacije, podskupovi, permutacije, particije.

Otvori lekciju →

Bektreking i gruba sila

Lavirint, zagrade, N dama, Sudoku.

Otvori lekciju →

4 Lekcije uz ove zadatke

Teorija koju vredi pročitati pre ili tokom rešavanja.

Algoritmi – vodič

Sve lekcije o algoritmima na jednom mestu.

Otvori lekciju →

Zamena iteracija formulom

Složenost algoritma na primerima.

Otvori lekciju →

Rekurzivni algoritmi

Kako rekurzija radi i kada je koristiti.

Otvori lekciju →

Brzo stepenovanje

Stepen u log n koraka.

Otvori lekciju →

Rekurzija i dinamičko programiranje

Sledeći korak posle rekurzije.

Otvori lekciju →

5 Dalje

Zadaci sa takmičenja po nivoima.

Takmičenja

Kvalifikacije, okružno i državno takmičenje.

Otvori lekciju →

Predloženi redosled

  1. Algoritmi: NZD i prosti brojevi
  2. Poboljšanje složenosti
  3. Rekurzivni algoritmi
  4. Kombinatorni problemi
  5. Bektreking i gruba sila

Korisni spoljni resursi

  • Petlja – zbirke „Napredni algoritmi“ i zadaci sa takmičenja sa automatskom proverom
  • CSES Problem Set – klasični algoritamski zadaci (na engleskom), poglavlja Introductory i Complete Search
  • VisuAlgo – animacije algoritama: rekurzija, sortiranje, pretraga