Osnovni matematički algoritmi

Algoritam je opis koraka koje treba slediti da bi se neki problem rešio u konačnom broju koraka. Algoritmi su veoma bliski računarskim programima i ponekad se s njima poistovećuju, ali se algoritmom mogu opisati i postupci koji se nikada neće izvršavati na računaru.

Mnogi algoritmi koji se danas koriste u programima nastali su mnogo pre računara. Poznat primer je Euklidov algoritam za određivanje najvećeg zajedničkog delioca (NZD) dva cela broja:

Treba naći najveći zajednički delilac celih brojeva m i n, odnosno najveći broj koji deli oba broja bez ostatka. Ako je m > n, podelimo m sa n i neka je r ostatak. Ako je r = 0, rešenje je n; inače isti postupak ponovimo sa n i r.

Algoritam se zasniva na činjenici da broj koji deli bez ostatka m i n deli bez ostatka i n i r, gde je r ostatak pri deljenju m sa n.

Na ovoj strani su sakupljeni matematički algoritmi koji se najčešće koriste u školskom i takmičarskom programiranju. Preporučeni redosled učenja je redosled kartica ispod.

Teorija brojeva

Fibonačijeva spirala
Početni nivo
Fibonačijev niz
Svaki član je zbir dva prethodna. Rekurzija, dinamičko programiranje i rešenje sa O(1) memorije. Fibonačijevi brojevi javljaju se i u prirodi, na primer u broju spirala suncokreta i šišarke.
Otvori lekciju →
Delioci i faktorizacija broja
Početni nivo
Prosti brojevi i faktorizacija
Provera da li je broj prost u O(√n), određivanje svih delilaca i rastavljanje broja na proste činioce.
Otvori lekciju →
Eratostenovo sito
Srednji nivo
Eratostenovo sito
Svi prosti brojevi do n u O(n log log n) i brza faktorizacija mnogo brojeva pomoću najmanjih delilaca.
Otvori lekciju →
Određivanje NZD i NZS
Srednji nivo
Euklidov algoritam — NZD i NZS
Najveći zajednički delilac i najmanji zajednički sadržalac, iterativno i rekurzivno, i prošireni Euklidov algoritam.
Otvori lekciju →

Nizovi i efikasno računanje

Maksimalna suma uzastopnog podniza
Početni nivo
Maksimalna suma uzastopnog podniza
Rešenje po definiciji i njegovo ubrzanje sa O(n³) na O(n²). Problem se često javlja u računarskoj biologiji, pri analizi DNK i proteinskih sekvenci.
Otvori lekciju →
Srednji nivo
Kadaneov algoritam
Maksimalna suma uzastopnog podniza u jednom prolazu kroz niz, složenosti O(n).
Otvori lekciju →
Takmičarski nivo
Algoritam brzog stepenovanja
Xn i (Xn) mod m u O(log n), rekurzivno i iterativno, uz primenu na zadatak Mešalica.
Otvori lekciju →

Gde dalje?

Prethodno
|<Algoritmi		 Sledeće
Fibonačijev niz>|

Članci iz oblasti matematičkih algoritama