/* veci od dva broja.

*/
max2(X,Y,X):-X>=Y,!.
max2(X,Y,Y).

/* N! */
fakt(0,1).
fakt(N,F):-N1 is N-1,fakt(N1,F1),F is N*F1.

/* N!! */
faktd(0,1).
faktd(1,1).
faktd(N,F):-N1 is N-2,faktd(N1,F1),F is N*F1.

/* Zbir parnih cifara broja. Verzija 1. */

zc(N,N):-N<10,N mod 2=:=0.
zc(N,0):-N<10,N mod 2=\=0.
zc(N,X):-N>=10,N1 is N//10,N2 is N mod 10,zc(N1,X1),zc(N2,X2),X is X1+X2.

/* Zbir parnih cifara broja. Verzija 2. */

zpc(N,N):-N<10,N mod 2=:=0.
zpc(N,0):-N<10,N mod 2=\=0.
zpc(N,X):-N>=10,B is N mod 10,B mod 2=\=0,N1 is N//10,zpc(N1,X).
zpc(N,X):-N>=10,B is N mod 10,B mod 2=:=0,N1 is N//10,zpc(N1,X1),X is X1+B.

/* Zbir parnih cifara broja. Verzija 3. */

zpm(N,N):-N<10,N mod 2=:=0.
zpm(N,0):-N<10,N mod 2=:=1.
zpm(N,X):-(N>=10,N mod 2=:=0,N1 is N//10,zpm(N1,X1),X is X1+(N mod 10));
(N>=10,N mod 2=:=1,N1 is N//10,zpm(N1,X1),X is X1).

/* Zbir brojeva deljivih sa 3. */

z3(N,0):-N=:=0;N=:=1;N=:=2.
z3(N,X):-N mod 3=\=0, N1 is N mod 3, N2 is N-N1, z3(N2,X).
z3(N,X):-N mod 3=:=0, N2 is N-3, z3(N2,X1), X is N+X1.

/* Prevesti dekadni u binarni broj. */

dec2bin(0):-!.
dec2bin(X):-Y is X mod 2,X1 is X // 2,dec2bin(X1),write(Y).

/* Prevesti dekadni broj u heksadekadni. */

hek(X):-X<10,write(X),!.
hek(X):-X>=10,X<16,(X=:=10,write('A'));(X=:=11,write('B'));
(X=:=12,write('C'));(X=:=13,write('D'));
(X=:=14,write('E'));(X=:=15,write('F')),!.
heksa(X):-X<16,hek(X),!.
heksa(X):-X>=16,X1 is X//16,B is X mod 16,heksa(X1),hek(B).

/* Apsolutna vrednost. */
abs(X,X):-X>=0,!.
abs(X,Y):-X<0,Y is -X.

/* Broj cifara celog broja. */

brcif(X,1):-X<10,!.
brcif(X,Y):-X1 is X//10,brcif(X1,Y1),Y is Y1+1.

/* Zbir cifara celog broja. */

zcif(X,X):-X<10,!.
zcif(X,Y):-X1 is X//10,C is X mod 10,zcif(X1,Y1),Y is Y1+C.
/* Broj parnih i neparnih cifara celog broja. */
pncif(0,0,0):-!.
pncif(X,P,N):-X1 is X//10,C is X mod 10,C mod 2=:=0,pncif(X1,P1,N),P is P1+1.
pncif(X,P,N):-X1 is X//10,C is X mod 10,C mod 2=\=0,pncif(X1,P,N1),N is N1+1.

/* N-ti stepen broja X. */

stepen(X,0,1):-!.
stepen(X,N,Y):-N>0,N1 is N-1,stepen(X,N1,Y1),Y is X*Y1.

/* Najveci zajednicki delilac. Euklidov algoritam. */

nzd(X,0,X):-!.
nzd(X,Y,N):-Y>0,Z is X mod Y,nzd(Y,Z,N).

/* Najmanji zajednicki sadrzalac. */

nzs(X,Y,N):-nzd(X,Y,Z),N is X*Y//Z.

/*
Utvrditi da li je zadati broj prost.
Broj je prost ako nije deljiv ni sa jednim brojem od broja 2 do
polovine zadatog broja.
*/
prost(N):-prost(N,2).
prost(N,X):-X>N//2,!.
prost(N,X):-X=<N//2,N mod X=\=0,X1 is X+1,prost(N,X1).

/*
Prikazati sve proste brojeve manje ili jednake zadatom broju. Verzija 1.
*/
prosti(X):-X>=2,prost(X),write(X),tab(2),X1 is X-1,prosti(X1).
prosti(X):-X>=2,not prost(X),X1 is X-1,prosti(X1).

/*
Prikazati sve proste brojeve manje ili jednake zadatom broju. Verzija 2.
*/
prosti(X,X):-X>=2,prost(X).
prosti(X,P):-X>=2,X1 is X-1,prosti(X1,P).

/* Prikazati koliko ima prostih brojeva manjih ili jednakih zadatom broju. */
prostin(X,0):-X<2.
prostin(X,N):-X>=2,prost(X),X1 is X-1,prostin(X1,N1),N is N1+1.
prostin(X,N):-X>=2,not prost(X),X1 is X-1,prostin(X1,N).

/* Fibonacijev niz. */
fib(1,1):-!.
fib(2,1):-!.
fib(N,K):-N>2,N1 is N-1,fib(N1,K1),N2 is N1-1,fib(N2,K2),K is K1+K2.

/* Suma prvih N clanova Fibonacijevog niza. */

fibs(1,1):-!.
fibs(N,S):-fib(N,K),N1 is N-1,fibs(N1,S1),S is S1+K.

/* Clan liste. */
clan([X|_],X).
clan([_|Y],X):-clan(Y,X).

/* Duzina liste. */
duzlis([],0).
duzlis([_|R],N):-duzlis(R,M), N is M+1.
/* Zbir elemenata liste. */
zbirellis([],0).
zbirellis([G|R],Z):-zbirellis(R,Z1),Z is Z1+G.

/* Zbir neparnih elemenata liste. */

znep([],0).
znep([G|R],Z):-G mod 2=\=0,znep(R,Z1),Z is G+Z1.
znep([G|R],Z):-G mod 2=:=0,znep(R,Z).

/* Maksimalni element liste. */

maxl([G],G):-!.
maxl([X,X],X):-!.
maxl([X,Y],X):-X>Y,!.
maxl([X,Y],Y):-Y>X,!.
maxl([G|R],M):-maxl(R,X),(G>X, M is G; M is X),!.

/* Broj pozitivnih i negativnih elemenata liste. */

brojpn([],0,0).
brojpn([G|R],P,N):-G>0,brojpn(R,P1,N),P is P1+1.
brojpn([G|R],P,N):-G<0,brojpn(R,P,N1),N is N1+1.
brojpn([G|R],P,N):-G=:=0,brojpn(R,P,N).

/* Suma pozitivnih i suma negativnih elemenata liste celih brojeva. */

sumapn([],0,0).
sumapn([G|R],P,N):-G>=0,sumapn(R,P1,N),P is P1+G.
sumapn([G|R],P,N):-G<0,sumapn(R,P,N1),N is N1+G.

/* Spajanje dve liste. */

spoj([],X,X).
spoj([G|R],L,[G|R1]):-spoj(R,L,R1).

/* Obrtanje liste. */
obrni([],[]).
obrni([G|R],X):-obrni(R,Y),spoj(Y,[G],X).

/* Dodavanje elementa na pocetak liste. */

dodelpoc(X,[],[X]):-!.
dodelpoc(X,[G|R],[X|R1]):-dodelpoc(G,R,R1).

/* Dodavanje elementa na kraj liste. Varijanta 1. */

dodelkraj1(X,[],[X]).
dodelkraj1(X,P,L):-obrni(P,L1),dodelpoc(X,L1,L2),obrni(L2,L).

/* Dodavanje elementa na kraj liste. Varijanta 2. */

dodelkraj(X,[],[X]).
dodelkraj(X,[G|R],[G|R1]):-spoj(R,[X],R1).

/* Lista prvih N faktorijela. */

fakt(0,1).
fakt(X,N):-X>0,X1 is X-1,fakt(X1,N1),N is X*N1.
lisfakt(0,[]).
lisfakt(N,L):-N>0,N1 is N-1,lisfakt(N1,L1),fakt(N,F),dodelkraj(F,L1,L).

/* Na osnovu liste brojeva formirati listu parnih. */

par([],[]).
par([G1|R1],L2):-G1 mod 2=:=0,par(R1,L3),spoj([G1],L3,L2).
par([G1|R1],L2):-G1 mod 2=\=0,par(R1,L2).

/* Na osnovu liste slova formirati listu koja se sastoji od samoglasnika. */

sam([],[]).
sam([G|R],L):-(G==a;G==e;G==i;G==o;G==u),sam(R,X),spoj([G],X,L).
sam([G|R],L):-not (G==a;G==e;G==i;G==o;G==u),sam(R,L).

/* Na osnovu liste slova formirati listu koja se sastoji od suglasnika. */

sug([],[]).
sug([G|R],L):-not (G==a;G==e;G==i;G==o;G==u),sug(R,X),spoj([G],X,L).
sug([G|R],L):-(G==a;G==e;G==i;G==o;G==u),sug(R,L).

/* Poslednji element liste. Varijanta 1. */

poslel1([],_):-write('Lista koju ste uneli je prazna!'),nl,fail.
poslel1([X],X):-!.
poslel1([G|R],P):-poslel1(R,P).

/* Poslednji element liste. Varijanta 2. */

poslel([],_):-fail.
poslel([X],X):-!.
poslel([G|R],P):-poslel(R,P).

/* Proveriti da li su dva data elementa uzastopni clanovi liste. */

uzastopna2([X,Y],X,Y):-!.
uzastopna2([G1,G2|R],X,Y):-G1=X,G2=Y,!.
uzastopna2([G|R],X,Y):-G\=X,uzastopna2(R,X,Y).

/* Proveriti da li su tri data elementa uzastopni clanovi liste. */

uzastopna3([X,Y,Z],X,Y,Z):-!.
uzastopna3([G1,G2,G3|R],X,Y,Z):-G1=X,G2=Y,G3=Z,!.
uzastopna3([G|R],X,Y,Z):-G\=X,uzastopna3(R,X,Y,Z).

/* Zamena mesta prvom i poslednjem elementu liste. */

zamppel([],[]):-!.
zamppel([X],[X]):-!.
zamppel([X,Y],[Y,X]):-!.
zamppel([G|R],L):-obrni(R,[P|R1]),obrni(R1,R2),spoj([P],R2,X),spoj(X,[G],L).

/* Zamena mesta drugom i pretposlednjem elementu liste. */

zam2p(L,L):-duzlis(L,N),N<4,!.
zam2p([G|[D|R]],L):-obrni(R,[P|[PP|R1]]),obrni(R1,R2),
spoj([G,PP],R2,L1),spoj(L1,[D,P],L).

/* Odrediti poslednja tri elementa liste. */

poslednja3([X,Y,Z],X,Y,Z):-!.
poslednja3([_|R],X,Y,Z):-poslednja3(R,X,Y,Z).

/*
Ispitati da li svi elementi liste imaju odredjenu osobinu.
Na primer: da li su svi elementi liste pozitivni.
*/
osobina_liste([]).
osobina_liste([G|R]):-osobina(G),osobina_liste(R).
osobina(X):-X>0.

/* Obrisati prvu pojavu zadatog elementa u listi. */

brisi_jednom([],_,[]).
brisi_jednom([G|R],G,R):-!.
brisi_jednom([G|R],X,[G|R1]):-brisi_jednom(R,X,R1).

/* Obrisati sve pojave zadatog elementa u listi. */

brisi_sve([],_,[]).
brisi_sve([X|R],X,L):-!,brisi_sve(R,X,L).
brisi_sve([G|R],X,[G|R1]):-brisi_sve(R,X,R1).

/* Napraviti listu razlicitih elemenata na osnovu zadate liste. */

razliciti([],[]).
razliciti([G|R],L):-clan(R,G),razliciti(R,L),!.
razliciti([G|R],[G|R1]):-razliciti(R,R1),!.

/*
Iz date liste izbaciti prvih N elemenata a od preostalih formirati listu.
U suprotnom, prikazati odgovarajucu poruku.
*/
izbaci_n(L,0,L):-!.
izbaci_n(L,N,_):-duzlis(L,M),M<N,write('Lista je kraca nego sto treba!'),!,fail.
izbaci_n([G|R],N,L):-N>0,M is N-1,izbaci_n(R,M,L).

/*
Iz date liste izbaciti poslednjih N elemenata a od preostalih formirati listu.
U suprotnom, prikazati odgovarajucu poruku.
*/
izbaci_np(L,N,L1):-obrni(L,LL),izbaci_n(LL,N,L2),obrni(L2,L1).

/* Odrediti poslednjih N elemenata liste. */

poslednjih_n(L,N,L1):-duzlis(L,M),K is M-N,izbaci_n(L,K,L1).

/* Odrediti prvih N elemenata liste. */

prvih_n(L,N,L1):-duzlis(L,M),N=<M,K is M-N,izbaci_np(L,K,L1),!.
prvih_n(L,N,L):-duzlis(L,M),N>M.

/* Napraviti listu koja se sastoji od cifara zadatog celog broja. */

liscif(X,[X]):-X<10,!.
liscif(X,L):-X>10,C is X mod 10,Y is X // 10,liscif(Y,L1),spoj(L1,[C],L).

/*
Brise sve pojave zadatog elementa iz liste ali tako da brise samo jednu
pojavu elementa.
*/
brisi([G|R],G,R).
brisi([G|R],X,[G|R1]):-brisi(R,X,R1).

/* Generisati sve permutacije elemenata date liste. */

perm1([],[]).
perm1([G|R],P):-perm1(R,P1),brisi(P,G,P1).

perm2([],[]).
perm2(L,[G|R]):-brisi(L,G,L1),perm2(L1,R).

/* Generisati sve kombinacije elemenata date liste bez ponavljanja. */

komb(X,0,[]).
komb([G|R],N,[G|R1]):-N>0,N1 is N-1,komb(R,N1,R1).
komb([G|R],N,L):-N>0,komb(R,N,L).

/* Generisati varijacije bez ponavljanja elemenata date liste. */

var(X,0,[]).
var(L,N,[G|R]):-N>0,brisi(L,G,V),N1 is N-1,var(V,N1,R).

/* Clan liste. */
clan([X|_],X).
clan([_|Y],X):-clan(Y,X).
/* Generisati varijacije sa ponavljanjem elemenata date liste. */
varp(X,0,[]).
varp(L,N,[G|R]):-N>0,clan(L,G),N1 is N-1,varp(L,N1,R).

/* Umetanje broja u sortiranu listu. */

umetni(X,[G|R],[G|P]):-G<X,!,umetni(X,R,P).
umetni(X,L,[X|L]).

/* Sortiranje sa umetanjem. */
stu([],[]).
stu([G|R],S):-stu(R,L),umetni(G,L,S).

/* Bubble sort. */
bubble(L1,L2):-spoj(X,[A,B|R],L1),B<A,!,spoj(X,[B,A|R],L3),bubble(L3,L2).
bubble(L,L).

/* Spajanje dve sortirane liste sa sortiranjem. */

spojs([],X,X):-!.
spojs(X,[],X):-!.
spojs([G1|R1],[G2|R2],[G1|R]):-G1<G2,spojs(R1,[G2|R2],R),!.
spojs([G1|R1],[G2|R2],[G2|R]):-spojs([G1|R1],R2,R),!.

/* Clan stabla. */
clan(X,s(L,X,D)):-!.
clan(X,s(L,Y,D)):-clan(X,L),!.
clan(X,s(L,Y,D)):-clan(X,D).

/* Broj cvorova stabla. */

brcvor(nil,0).
brcvor(s(L,K,D),N):-brcvor(L,N1),brcvor(D,N2), N is N1+N2+1.

/* Dubina binarnog stabla. */

dubbs(nil,0).
dubbs(s(L,K,D),N):-dubbs(L,N1),dubbs(D,N2),max2(N1,N2,N3), N is N3+1.

/* Ubacivanje u listu svih cvorova binarnog stabla po inorder redosledu. */

inorder(nil,[]).
inorder(s(L,K,D),Lis):-inorder(L,Lis1),inorder(D,Lis2),spoj(Lis1,[K|Lis2],Lis).

/* Dodavanje u uredjeno binarno stablo. */

ubacis(nil,X,s(nil,X,nil)).
ubacis(s(L,X,D),X,s(L,X,D)).
ubacis(s(L,K,D),X,s(L1,K,D)):-X<K,ubacis(L,X,L1).
ubacis(s(L,K,D),X,s(L,K,D1)):-X>K,ubacis(D,X,D1).

/* Ubacivanje elemenata liste u uredjeno binarno stablo. */

ublisbs([],S,S).
ublisbs([G|R],S,NNS):-ubacis(S,G,NS),ublisbs(R,NS,NNS).

/* Sortiranje liste brojeva. */

sortlis(L,L1):-ublisbs(L,nil,S),inorder(S,L1).

/* Brisanje elementa iz uredjenog binarnog stabla. */

brisi(s(nil,X,D),X,D):-!.
brisi(s(L,X,nil),X,L):-!.
brisi(s(L,K,D),X,s(L1,K,D)):-X<K,brisi(L,X,L1),!.
brisi(s(L,K,D),X,s(L,K,D1)):-X>K,brisi(D,X,D1),!.
brisi(s(L,X,D),X,s(L,Y,D1)):-brisimin(D,Y,D1).
brisimin(s(nil,X,D),X,D):-!.
brisimin(s(L,K,D),X,s(L1,K,D)):-brisimin(L,X,L1).

/* Provera brisanja. */
bris(L,X,L1):-ublisbs(L,nil,BS),brisi(BS,X,BS1),inorder(BS1,L1).

/*
Generisati listu listova binarnog stabla.
*/
listovi(L,L1):-ublisbs(L,nil,S),nadjilistove(S,L1).
nadjilistove(nil,[]):-!.
nadjilistove(s(nil,K,nil),[K]):-!.
nadjilistove(s(L,K,D),Lis):-nadjilistove(L,Lis1),nadjilistove(D,Lis2),
spoj(Lis1,Lis2,Lis).
/*
Sadrzaj K-tog cvora binarnog stabla pri obilasku levo-koren-desno.
*/
sadrzaj(S,K,X):-inorder(S,L),ktiellis(L,K,X).
ktiellis(L,K,X):-K<1,write('Nemoj da se salis!'),!,fail.
ktiellis(L,K,X):-duzlis(L,N),K>N,write(K),write('>'),write(N),fail,!.
ktiellis(L,K,X):-duzlis(L,N),K=<N,K1 is K-1,izbaciprvihn(L,K1,[X|_]).
provsadrk(L,K,X):-ublisbs(L,nil,BS),sadrzaj(BS,K,X),!.