Računalništvo (FMF)/Vaje/1. kolokvij 2005-2006

Iz MaFiRaWiki


1. naloga

Konstruiraj končni avtomat, ki bo razpoznaval rimske številke do 1000.

(/Rešitev 1. naloge)

2. naloga

Množica vseh anagramov (permutacij) besede w = ada je množica A = aad,ada,daa.
(a) Napiši program Anagrami[w], ki konstruira množico vseh anagramov (permutacij) besede w.
(b) Opiši časovno zahtevnost tega programa.
(c) Kako hitro ta program najde anagram besede aaaaaaaaaaaaaa?
Jasno razloži katere osnovne operacije uporabljaš in kakšna je njihova časovna zahtevnost.

(/Rešitev 2. naloge)

3. naloga

Nariši
(a) kopico, ki jo dobiš, če v prazno kopico vstaviš elemente 5, 2, 6, 1, 3, 4, 7, 8 (v tem vrstnem redu). Elementi prihajajo po vrsti.
(b) kopico, ki jo dobiš, če v prazno kopico vstaviš elemente 5, 2, 6, 1, 3, 4, 7, 8 (v tem vrstnem redu). Elementi so dani vnaprej.
(c) Iz obeh kopic odstrani pet elementov.

(/Rešitev 3. naloge)

4. naloga

Opiši aksiome in implementacijo podatkovne strukture Rat za pozitivna racionalna števila.
Operacije naj vključujejo
\bullet Kvocient: Nat \times Nat \rightarrow Rat
\bullet Seštej: Rat \times Rat \rightarrow Rat
\bullet Množi: Rat \times Rat \rightarrow Rat
\bullet Odštej: Rat \times Rat \rightarrow Rat
\bullet Deli: Rat \times Rat \rightarrow Rat
\bullet Enak: Rat \times Rat \rightarrow Boolean
Znani sta strukturi Nat in Boolean. Pazi na deljeneje z 0!

(/Rešitev 4. naloge)

Osebna orodja