\documentclass[a4paper]{article}
\usepackage[cm]{fullpage}
\usepackage[serbian]{babel}

\def\d{{\fontencoding{T1}\selectfont\dj}}
\def\D{{\fontencoding{T1}\selectfont\DJ}}

\newtheorem{z}{Zadatak}

\title{Blok 1 - Rekurzija i Pretraga sa vra\'canjem}
\date{}

\begin{document}
\maketitle

\emph{Napomena:} U svim narednim zadacima, redosled rezultata u prikazanim test primerima nije od va\v{z}nosti, tj. u va\v{s}im realizacijama problema redosled ne mora biti identi\v{c}an. Zadatke raditi u bilo kom jeziku, a preporu\v{c}uje se konzolni re\v{z}im rada s obzirom da je naglasak na algoritmima.

\section{Rekurzija}


\begin{z}  (1 poen) Napisati rekurzivnu funkciju koji prebrojava sva pojavljivanja cifre C u zadatom broju N. Test primer:
\end{z}

\begin{verbatim}
5927417 7
2
\end{verbatim}

\begin{z} 
(2 poena) Napisati rekurzivnu funkciju koji razbija uneti broj N na proste \v{c}inioce. Njie neophodno \v{c}uvati proste \v{c}inioce u nizu, dovoljno je samo ispisati ih. Test primer:
\end{z}

\begin{verbatim}
156
2 2 3 13
\end{verbatim}

\begin{z}  (3 poena) Napisati rekurzivnu funkciju koja za dati ceo broj N i du\v{z}inu D odredjuje podbrojeve broja n du\v{z}ine d. Test primer:
\end{z}

\begin{verbatim}
23456 2
56
45
34
23
\end{verbatim}

\begin{z}  (3 poena) Napisati i testirati rekurzivnu funkciju kojom se formira broj dobijen od broja N tako \v{s}to se izbaci svaka cifra na neparnoj poziciji počev od cifre jedinica. Test primer:
\end{z}

\begin{verbatim}
3282383
228
\end{verbatim}

\begin{z}  (4 poena) Napisati rekurzivnu funkciju koji za zadati String S, vraca novi String S' u kojem su sva pojavljivanja uzastopnih jednakih karaktera razdvojena karakterom '*'. Test primer:
\end{z}

\begin{verbatim}
abcaabb_**fds3fds2kkdaA
abca*ab*b_***fds3fds2k*kdaA
\end{verbatim}

\begin{z}  (4 poena) Korisnik unosi niz re\v{c}i u jednom redu. Re\v{c}i su razdvojene praznim mestima. Napisati rekurzivnu funkciju koja ra\v{c}una najve\'cu razliku po pitanju broja karaktera unetih re\v{c}i. Nije dozvoljeno kori\v{s}\'cenje dve rekurzivne funkcije, npr. za ra\v{c}unanje najdu\v{z}e i najkra\'{c}e re\v{c}i. Test primer:
\end{z}

\begin{verbatim}
jedan dva tri dvadeset otorinolaringolog laptop
15
\end{verbatim} 

\begin{z}  (4 poena) Korisnik unosi dve re\v{c}i. Ispitati rekurzivno, koliko puta se druga re\v{c} pojavljuje u prvoj (dozvoljena su preklapanja, pogledati poslednja dva pojavljivanja u test primeru). Pritom zanemariti razliku izmedju malih i velikih slova. Test primer:
\end{z}

\begin{verbatim}
abcdaaabAdABabAdefgbCBababA aba
5
\end{verbatim}

\begin{z}  (5 poena) Napisati rekurzivnu funkciju koja proverava da li su u datom String-u zagrade pravilno uparene. Kao rezultat ispisuje "da" u slu\v{c}aju da jesu, ina\v{c}e ne. Test primer 1:
\end{z}

\begin{verbatim}
(()()(()()))
da
\end{verbatim}

Test primer 2:

\begin{verbatim}
())(
ne
\end{verbatim}

\begin{z} (4 poena) Implementirati rekurzivno funkciju stepenovanja nekog broja. Korisnik unos realan broj koji stepenuje A, i stepen N. Kako se svodi ovaj problem na potproblem, da li sa dimenzije N na dimenziju N-1 ili mo\v{z}e br\v{z}e?. Test primer:
\end{z}

\begin{verbatim}
3 17
129140163
\end{verbatim}

\begin{z} (3 poena) Napisati rekurzivnu funkciju koja elimini\v{s}e sve uzastopne karaktere duplikate iz String-a. Test primer:
\end{z}

\begin{verbatim}
axxbcDdfgahhhhadiiijk33423
axbcDdfgahadijk3423
\end{verbatim}

\section{Pretraga sa vra\'canjem}

\begin{z}  (5 poena) Implementirati program koji gener\v{s}e sve binarne nizove dimenzije N, takve da je broj jedinica koji se u njemu pojavljuje  manji ili jednak od broja K. Korisnik unosi N i K, nije potrebno \v{c}uvati binarne nizove, dovoljno je samo ispisati ih. Test primer:
\end{z}

\begin{verbatim}
5 2
00001
00010
...
10000
00011
00101
...
\end{verbatim}

\begin{z}  (6 poena) Napisati rekurzivnu funkciju koja ispisuje sve N-tocifrene brojeve u sistemu osnove 3 koji ne sadrže dve iste uzastopne cifre.
\end{z}

\begin{verbatim}
3
010
020
101
202
...
210
\end{verbatim}

\begin{z} (5 poena)  Data je matrica polja dimenzije M x N (korisnik unosi M - broj redova i N - broj kolona). Napisati program koji ispisuje sve puteve iz gornjeg levog ugla te matrice ka donjem desnom uglu. Ograni\v{c}enje je da se sme i\'ci samo desno ili dole. Rezultat ispisati kori\v{s}cenjem oznake polja matrice (numeracija polja po\v{c}inje od 0). Test primer:
\end{z}

\begin{verbatim}
4 3
(0,0) (1,0) (2,0) (3,0) (3,1) (4,1) (4,2) (4,3)
...
\end{verbatim}

\begin{z} (10 poena) Napisati program koji pronalazi i ispisuje sva re\v{s}enja magi\v{c}nog kvadrata dimenzije N = 3. Rezultat se ispisuje u formi matrice. Nakon svakog re\v{s}enja program se zaustavlja, i tek nakon \v{s}to korisnik unese \emph{ENTER}, prikazuje se slede\'ce mogu\'ce re\v{s}enje. Test primer:
\end{z}

\begin{verbatim}
2 7 6 
9 5 1
4 3 8
ENTER
...
\end{verbatim}

\end{document}

