Naloga predstavlja nadaljevanje prve naloge s prejšnjega izpita (glej rešitve).
Epidemije prihajajo v valovih. V neki državi se je število okuženih po dnevih spreminjalo tako:
= [1, 6, 5, 0, 0, 0, 2, 8, 5, 3, 0, 5, 8, 0, 0, 0, 5, 1, 1] okuzbe
Tule vidimo štiri valove. Zanimajo nas vrhunci valov. V prvem valu je
to drugi dan od treh (2, 3), v drugem prvi od štirih (1, 4), v tretjem
drugi od dveh (2, 2), v četrtem prvi od treh (1, 3). Od obeh števil
odštejemo 1 in ju delimo: tako izvemo, da so vrhovi ob
[1 / 2, 1 / 3, 1 / 1, 0 / 3]
. Tako odštevanje lepše opiše,
kje se nahaja vrh: to se najlepše vidi v prvem valu, ko je vrh na
polovici.
Če je val dolg 1, je vrh na položaju 0.
Na začetku in koncu seznama je lahko še poljubno število ničel. Med dvema valovoma je vsaj ena ničla.
Napiši funkcijo vrhovi(okuzbe)
, ki za podani seznam
dnevnih okužb vrne položaje vrhov valov. Klic
vrhovi([1, 6, 5, 0, 0, 0, 2, 8, 5, 3, 0, 5, 8, 0, 0, 0, 5, 1, 1])
torej vrne [0.5, 0.333, 1, 0]
.
Tu so bili v rahli prednosti študenti, ki so si že prej ogledali rešitve prejšnjega izpita. Logika funkcije je namreč enake, tako da jo lahko kar hitro predelamo - a le, če jo razumemo. Če ne, pa ne. :)
def vrhovi(s):
= []
v_valovih = -1
dan = 0
naj # Spredaj in zadaj dodamo 0, da se ni potrebno ukvarjati z začetkom in koncem
for x in [0] + s + [0]:
if x > 0: # Val se nadaljuje
# Pogledamo, ali je število višje od najvišjega in v tem primeru
# zabeležimo število okuženih in dan
if x > naj:
= x
naj = dan
najdan += 1
dan else: # Vala je konec
if naj > 0: # Če ni bil prazen...
if dan > 1:
/ (dan - 1))
v_valovih.append(najdan else: # Poseben primer, ko se je potrebno izogniti deljenju z 0
0)
v_valovih.append(= 0
naj = 0
najdan = 0
dan return v_valovih
vrhovi(okuzbe)
[0.5, 0.3333333333333333, 1.0, 0.0]
Nekaterih - mogoče celo vsi, ki so se naloge lotili in jo uspešno rešili - so raje nabrali cel val v seznam ter nato poiskali indeks maksimalnega elementa ter ga delili z dolžino seznama. Seveda gre tudi tako.
Seve virusov primerjajo glede na markerje. Recimo, da bomo uporabljali naslednje markerje (vendar naj vaša rešitev deluje za poljuben nabor markerjev, ne le te, ki so v testih!)
= {"ATTA", "GGT", "TTG", "TCCCTC"} markerji
V genskem materialu vzorca virusa je vsak od teh markerjev prisoten ali pa ne. (Ali je prisoten enkrat ali večkrat, ne igra vloge). Podobnost sevov opazujemo glede na to, v koliko markerjih se ujemata.
Vzemimo, recimo
= {"ATTA", "GGT", "TTG", "TCCCTC"}
markerji = "GCGCATTAGCGGTCCCTCAAAGGT" # 1 1 0 1
vzorec = "ATTAATTAATTAATTA" # 1 0 0 0 => 2 sev4
Njuno ujemanje je 2: oba vsebujeta ATTA in oba ne vsebujeta TTG. (Glede preostalih dveh markerjev pa se razlikujeta.)
Napiši funkcijo najpodobnejsi(vzorec, sevi, markerji)
,
ki prejme nek vzorec, množico znanih sevov in množico markerjev. Vrniti
mora tistega izmed znanih sevov, ki je najbolj podoben vzorcu. Če je
enako podobnih več, naj vrne poljubnega izmed njih.
V testih je naštetih več sevov, v komentarjih pa so na enak način kot v gornjem primeru zapisane podobnosti.
Tu je bilo zelo zanimivo - morda bi moral napisati tudi nekoliko žalostno opazovati izdelke študentov. Pravilna rešitev gre prek vseh sevov in poišče tistega, ki se po markerjih najbolj ujema z vzorcem, torej
...for sev in sevi:
for marker in markerji:
...
Namesto tega so mnogi, morda celo večina, pisali
...for marker in markerji:
for sev in sevi:
...
Tako se stvar zelo zaplete; tisti, ki so uspeli priti po tej poti do cilja, so se iz jame, ki so si jo skopali, izvlekli s slovarji. Če zanki razporedimo pravilno, pa je rešitev preprosta.
def najpodobnejsi(vzorec, sevi, markerji):
= -1
naj_podobnost = 0
naj_sev for sev in sevi:
= 0
podobnost for marker in markerji:
if (marker in vzorec) == (marker in sev):
+= 1
podobnost if podobnost > naj_podobnost:
= podobnost
naj_podobnost = sev
naj_sev return naj_sev
Pogoj, ki preverja, ali oba vsebujeta ali ne vsebujeta markerja, je
eleganten: to ali drži marker in vzorec
mora biti enako
temu, ali drži marker in sev
. Oboje True
ali
oboje False
. Brez tega bi pisali (in večina študentov tudi
je pisala)
(marker in vzorec and marker in sev) or (marker not in vzorec and marker not in sev)
,
ali pa je napisala celo dva if
-a. Bolj žalostno, in tudi
nedelujoče, pa je pisati marker in sev and vzorec
. To
deluje v angleščini, v Pythonu pa ne.
= 0
podobnost for marker in markerji:
if (marker in vzorec) == (marker in sev):
+= 1 podobnost
lahko nadomestimo z
= sum((marker in vzorec) == (marker in sev) for marker in markerji) podobnost
Odtod hitro pridemo do
def najpodobnejsi(vzorec, sevi, markerji):
return max(sevi,
=lambda sev: sum((marker in sev) == (marker in vzorec)
keyfor marker in markerji))
V datoteki obcine.txt
je seznam občin s številom
prebivalcev in regijo, ki ji občina pripada. Podatki so ločeni z
vejicami.
Moravče, 5354, Osrednjeslovenska
Ljubljana, 288832, Osrednjeslovenska
Koper, 51828, Primorska
Kočevje ob gozdu, 16549, Južnoslovenska
Piran, 17613, Primorska
Kamnik, 13768, Osrednjeslovenska
V datoteki okuzbe.txt
je dnevno število okužb po
občinah, v takšni obliki:
Kamnik: 80
Kočevje ob gozdu: 50
Ljubljana: 90
Vse občine iz druge datoteke se pojavijo tudi v prvi. Obratno ni nujno: če nekje ni novih okužb, te občine v drugi datoteki ni.
Napiši funkcijo stanje_regij()
, ki prebere tidve
datoteki in vrne slovar, katerega ključi so vse regije, ki se
pojavijo v prvi datoteki, pripadajoča vrednost pa je delež
okuženih. V gornjem primeru ključu "Osrednjeslovenska"
pripada vrednost (80 + 90) / (5354 + 288832 + 13768)
(število okuženih v občinah iz te regije, deljeno s število prebivalcev
v vseh občinah te regije). Ključu "Primorska"
pa
0
, ker v primorskih občinah ni bilo okužb.
(Datoteke niso priložene, ker se sestavijo kar znotraj testov.)
Naloga združuje dve veščini: branje datotek in uporabo slovarjev. Sicer pa je precej rutinska.
from collections import defaultdict
def stanje_regij():
= {}
regije = defaultdict(int)
populacija for vrstica in open("obcine.txt"):
= vrstica.strip().split(", ")
ime, prebivalcev, regija = regija
regije[ime] += int(prebivalcev)
populacija[regija]
= dict.fromkeys(populacija, 0)
okuzenost for vrstica in open("okuzbe.txt"):
= vrstica.split(":")
obcina, okuzenih += int(okuzenih)
okuzenost[regije[obcina]]
for regija in okuzenost:
/= populacija[regija]
okuzenost[regija]
return okuzenost
Komentarja je vreden klic dict.fromkeys(populacija, 0)
.
Ta sestavi slovar, katerega ključi so iz seznama/terke/ključev
slovarja/niza/...česarkoli populacija
, vse vrednosti pa so
0. Če te funkcije ne poznamo, takšen slovar pač sestavimo z
= {}
okuzenost for regija in populacija:
= 0 okuzenost[regija]
Tipična napaka, ki so jo nekateri delali pri reševanju, je, da so delili število okuženih v regiji s skupnim številom prebivalcev občin, ki so imele vsaj eno okužbo, namesto s populacijo regije. Tega nisem kaznoval preveč strogo, kaznovati pa sem vendarle moral. Če ne bi imeli testov, bi lahko rekli, da niste dovolj natančno brali navodil; glede na to, da so testi povedali, da je nekaj narobe, pa bi morali odkriti, v čem je problem.
Variacija na prvo nalogo. Tokrat imamo le seznam za en val. Zanima nas, na kateri dan je bilo največ okužb in koliko.
Napiši rekurzivno funkcijo argmax(s)
,
ki za podani neprazni seznam vrne indeks in vrednost
največjega elementa. Klic argmax([5, 4, 7, 8, 5, 1])
vrne
(3, 8)
, ker se največji element, 8, pojavi na indeksu 3. Če
je največjih elementov več, vrne indeks prvega od njih.
Funkcija mora biti "prava rekurzivna funkcija": razen sebe naj ne
kliče drugih funkcij, razen len
, poleg tega naj ne vsebuje
zank.
Če ima seznam le en element, se največji element nahaja na indeksu 0, in sicer je to kar ničti element.
Sicer poizvemo, kje se nahaja in kakšen je največji element ostanka. Če je večji od prvega, vrnemo le-tega, a z 1 večjim indeksom (ker je potrebno upoštevati še prvi element). Če je prvi element večji, pa je največji, očitno, prvi element.
def argmax(s):
if len(s) == 1:
return 0, s[0]
= argmax(s[1:])
naj_idx, naj if naj > s[0]:
return naj_idx + 1, naj
else:
return 0, s[0]
5, 4, 7, 8, 5, 1]) argmax([
(3, 8)
Napiši razred Sledilnik
, ki ima
nov_dan
, ki kot argument sprejme število
novookuženih v tekočem dnevu; predstavljaj si, da jo pokličemo vsak dan,
ko vlada sporoči sveže podatke.Poleg tega naj ima atribute
naj_dnevnih
vsebuje največje doslej zabeleženo število
dnevnih okužb,tekoce_brez_okuzb
pove, koliko zadnjih dni že ni bilo
nobene okužbe,naj_brez_okuzb
pove, kako dolgo je bilo najdaljše
zaporedje dni brez okužb.Razen teh naj razred nima nobenih drugih atributov.
Poleg tega napiši razred Sledilnik2
, ki je izpeljan iz
razreda Sledilnik
in doda še atribut
skupno_okuzenih
, ki shranjuje skupno število
okuženih.Sledilnik2
naj smiselno uporabi oz. spreminja podedovane
metode in doda čim manj kode.
Recimo, da izvedemo naslednji program.
= Sledilnik2()
s 10)
s.nov_dan(15)
s.nov_dan(0)
s.nov_dan(0)
s.nov_dan(0)
s.nov_dan(0)
s.nov_dan(2)
s.nov_dan(0)
s.nov_dan(0) s.nov_dan(
Po tem je s.naj_dnevnih
enak 15
,
s.tekoce_brez_okuzb
je 2
,
s.naj_brez_okuzb
je 4
. Ker gre za
Sledilnik2
, je s.skupno_okuzb
enak
27
.
Če bi program nadaljevali z
s.nov_dan(3)
je s.naj_dnevnih
še vedno 15
,
s.tekoce_brez_okuzb
je 0
,
s.naj_brez_okuzb
je še vedno 4
in
s.skupno_okuzb
enak 30
.
class Sledilnik:
def __init__(self):
self.naj_dnevnih = 0
self.naj_brez_okuzb = 0
self.tekoce_brez_okuzb = 0
def nov_dan(self, okuzenih):
if okuzenih > 0:
self.tekoce_brez_okuzb = 0
if okuzenih > self.naj_dnevnih:
self.naj_dnevnih = okuzenih
else:
self.tekoce_brez_okuzb += 1
if self.tekoce_brez_okuzb > self.naj_brez_okuzb:
self.naj_brez_okuzb = self.tekoce_brez_okuzb
V konstruktorju nastavimo tri atribute na ustrezne začetne vrednosti.
V nov_dan
nas zanima, ali kdo okužen. Če je tako, je
tekoče število dni brez okužb enako 0, poleg tega pa preverimo, ali gre
morda celo za dnevni rekord.
Če okuženih ni, povečamo tekoče število dni brez okužb, potem pa preverimo, ali je to slučajno rekord števila dni brez okužb.
Drugi del naloge je preverjal, ali znate iz tega razreda izpeljati preprost razred in pravilno klicati podedovane metode.
class Sledilnik2(Sledilnik):
def __init__(self):
super().__init__()
self.skupno_okuzenih = 0
def nov_dan(self, okuzenih):
super().nov_dan(okuzenih)
self.skupno_okuzenih += okuzenih