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

Iz MaFiRaWiki


1. naloga

Na tvoje povabilo je prišla na obisk v Slovenijo skupina japonskih turistov (kot vemo, imajo vsi japonski turisti s seboj tudi fotoaparate in z njimi navdušeno fotografirajo). Ker si prijazen gostitelj, boš poskrbel za vse njihove stroške. Skrbijo te predvsem stroški izdelave fotografij. Po katerih poteh jih boš peljal na oglede slovenskih znamenitosti, če veš, da vsak kilometer po Sloveniji, pritisne vsak izmed turistov natanko n-krat na sprožilec fotoaparata. Upoštevaj, da si bodo ogledali vsako znamenitost natanko enkrat, da gredo na pot vedno vsi turisti, da se vedno odpravijo iz kraja D in vrnejo v kraj D (npr. v ponedeljek si bodo ogledali znamenitost G, zato se odpravijo iz kraja D do kraja G in nazaj v D), da fotografirajo le na poti do znamenitosti (kljub temu, da se morda vozijo po poti, po kateri so se že peljali), na poti nazaj pa ne, ter da boš moral izdelati vse posnete fotografije. Pri tem so znamenitsoti oddaljene

A B C D E F G
A 0 10 - - - - -
B - 0 - - - 30 -
C 15 35 0 7 40 - 20
D - 44 10 0 20 - 9
E 3 - - - 0 - -
F 12 - - - - 0 16
G - - 11 - 55 60 0

kilometrov. Znak "-" pomeni, da ni neposredne cestne povezave med krajema. Koliko fotografij boš moral izdelati, če je skupina sestavljena iz m turistov?

(/Rešitev 1. naloge)

2. naloga

Poišči vsa optimalna dvojiška iskalna drevesa in izračunaj pričakovano število primerjav za podatke:
a = (x,y,z,w)
p= \frac{1}{100}(18,9,5,11)
q= \frac{1}{100}(14,7,28,3,5)

(/Rešitev 2. naloge)

3. naloga

S pomočjo dinamičnega programiranja reši naslednjo nalogo. Za dano zaporedje n celih števil S=(a_{1}, a_{2}, \ldots, a_{n}) poišči najdaljše podzaporedje (ne nujno strnjeno!), katerega vsota je deljiva s 3. Natančno opiši algoritem in analiziraj časovno zahtevnost. Delovanje algoritma pokaži na primeru S = (1,3,6,1,2,11,5,2). Poskusi doseči časovno zahtevnost O(n).
Če ne želiš reševati primera na roke, velja tudi program v poljubnem programskem jeziku.

(/Rešitev 3. naloge)

4. naloga

Z metodo hitrega urejanja uredi od najmanjšega do največjega naslednje zaporedje števil:
10, 8, 2, 14, 6, 5, 3, 4, 15, 9, 1, 13, 7, 12, 11.
Pivotne elemente lahko izbereš poljubno (vendar opiši postopek po katerem si jih izbral in označi, katere si izbral).

(/Rešitev 4. naloge)

5. naloga (Dodatna naloga)

Ugotovi kaj vrne funkcija KajNaredim za različne vrednosti parametrov s in b. Predpostavi, da v seznamu s dobiš podana nenegativna cela števila.

KajNaredim[b_, s_List]/;Max[s]<b:=Fold[(#2+#1*b)&,0,s]

Namig: Kaj vrnejo naslednji klici:
(a) KajNaredim[2, {1}],
(b) KajNaredim[2, {0, 1}],
(c) KajNaredim[2, {1, 0}],
(d) KajNaredim[3, {1, 1, 2, 2}]?

(/Rešitev 5. naloge)

Osebna orodja