Uvod u računarstvo 22.4.2002.

Studenti koji su odslušali kolegij u ovoj akademskoj godini rješavaju zadatke 3-7, dok svi ostali studenti rješavaju zadatke 1-5. Daljnje napomene mogu se naći na kraju testa.

1. Nadite sve prirodne brojeve koji u binarnom sustavu imaju točno 5 znamenaka, a u sustavu s bazom 3 zapis im se sastoji samo od nula i jedinica. Rezultat zapišite u dekadskom sustavu.

Napomena. Kao rješenje priznat će se i program u pseudojeziku koji traži takve brojeve.

2. Sastavite konačni automat koji prepoznaje jezik (bu^{+}ba^{∗} + ba^{+}bu^{+})^{∗}.

3. Napišite formulu računa sudova (koja se sastoji samo od operatora ”ili” i negacije) koja za ulaz x = (x_{2}x_{1}x_{0})_{2} provjerava da li je x nultočka funkcije f(x) = x^{3} − x^{2} − 4x + 4.

4. Napišite program koji učitava prirodan broj n i ispisuje ”tablicu” množenja od 1 ∗ 1 do n ∗ n. Ispis ne mora biti u obliku tablice, nego može biti i u nekom drugom obliku, npr.

\begin{matrix}1 ∗ 1 = 1 \\ 1 ∗ 2 = 2 \\ ⋯ \\ 5 ∗ 7 = 35 \\ ⋯ \\ n ∗ n = n^{2} \end{matrix}

5. Napišite program koji učitava prirodan broj n i ispisuje sve prirodne k takve da vrijedi: 2^{k} − 3 < n. Napomena: pseudo jezik ne sadrži funkciju za potenciranje (a^{x}).

6. Definirajte zapis komarac koji kao komponente sadrži ime komarca, količinu popijene krvi i duljinu nosa. Napišite program koji će sortirati niz zapisa tipa komarac silazno po količini popijene krvi. [Možete pretpostaviti da je niz već unešen.]

7. Napišite funkciju koja kao argument uzima pointer na početak vezane liste koja sadrži zapise tipa brojevi, a kao izlaz vraća pointer na početak novokreirane vezane liste zapisa multiskup. Podaci u zapisu multiskup sadrže broj iz liste br i koliko se puta taj broj pojavio. Novokreirana vezana lista treba biti sortirana padajuće prema broju pojavljivanja koliko puta. Lista ne smije sadržavati članove kojima je element koliko puta jednak nuli.

zapis brojevi
[ \begin{matrix}int broj \\ brojevi ∗ sljedeci \end{matrix}

zapis multiskup
int br
int koliko puta
multiskup ∗ sljedeci

Napomena: Dozvoljena je upotreba Bronštejnovog priručnika, jednog A-4 papira sa formulama i kalkulatora. Programe umjesto u pseudojeziku možete pisati u programskim jezicima C, Pascal ili Perl, ali će se tada uzeti u obzir eventualne sintaktičke pogreške. Na zadaći obavezno napisati broj indeksa, ak. godinu u kojoj ste slušali kolegij i ime predavača.

Rezultati: srijeda, 24. travnja u 13:00

Vedran Šego