Tule so rešene izpitne naloge. Pri vsaki nalogi sem pokazal nekaj možnih rešitev in premislekov (razen pri tistih, ki so za to preenostavne). Pravilne pa so seveda tudi druge rešitve, ki dajo pravi rezultat. Nekatere od napisanih rešitev očitno presegajo pričakovani nivo znanja. Vsaka naloga pa je, kot boste videli, preprosto rešljiva tudi z osnovnim znanjem.

Izpit je bil v resnici lažji, kot se morda zdi. :)

Starost

Tole ni prehuda umetnost - malo spominja na domačo nalogo z mp3, malo spreminjanja nizov v števila...

Strategija bo preprosta. Najprej bomo izračunali katerega dne, meseca in leta je oseba rojena. Najprej se bomo delali, kot da je rojena leta 1xxx, torej bomo k trem števkam letnice prišteli 1000. Če bo vsota manjša od 1800, bomo dodali še 1000, ter tako poskrbeli za one, rojene po letu 2000. Starost bomo dobili tako, da bomo letnico rojstva odšteli od 2009. Za tiste, ki so rojeni januarja in to 26. ali prej, bomo k starosti dodali še 1.

def starost(EMSO): dan = int(EMSO[:2]) mesec = int(EMSO[2:4]) leto = 1000+int(EMSO[4:7]) if leto < 1800: leto += 1000 starost = 2009-leto if mesec == 1 and dan <= 26: starost += 1 return starost

Bomboni

Začnimo z najpreprostejšo rešitvijo. Recimo, da imamo štiri otroke in tisti, ki ima največ, ima osem bombonov. Ko jih bodo imeli vsi enako, jih bodo torej imeli 32. Recimo, da jih imajo sedaj 23. Koliko jim jih moramo še razdeliti? 32 - 23 = 9, ne? :)

def bomboni(s): return max(s) * len(s) - sum(s)

Kakor vidim, je edini lenuh, ki je rešil nalogo na ta nacin, Blaž Šolar. (Bravo!) Vsi drugi pa preveč radi programirate (pohvalno!) in ste nalogo rešili nekako takole.

def bomboni(s): naj = max(s) damo = 0 for i in s: damo += (naj - i) return damo

Veliko pa je tudi bolj zapletenih rešitev, ki ne uporabijo funkcije max.

Podobna beseda

Tipična rešitev, ki ste jo napisali, je videti nekako takole.

# Ta funkcija ne deluje pravino! def podobna(beseda): beseda = beseda.lower() najCrk = 0 for enaBeseda in besede: ta = 0 for c in beseda: if c in enaBeseda: ta += 1 if ta > najcrk: najBeseda = enaBeseda najCrk = ta return najBeseda

To ne deluje prav: težava je v tem, da enake črke štejemo večkrat. Najpreprostejša rešitev tega problema je uporaba množic. Število skupnih crk je kar enako preseku dveh množic; do preseka pridemo z metodo intersection ali z operatorjem &.

def podobna(beseda): bs = set(beseda) najCrk = 0 for enaBeseda in besede: skupnih = len(bs & set(enaBeseda)) if skupnih > najCrk: najCrk = skupnih najBeseda = enaBeseda return najBeseda

Gornja rešitev je nekako tisto, kar sem pričakoval. No, upal. (Niso pa napačne drugacne rešitve, če dajo pravilen rezultat.) Rokohitreci pa vedo, da ima funkcija max argument key, s katerim lahko nalogo rešijo kar takole.

def podobna(beseda): return max(besede, key=lambda x: set(beseda.lower()) & set(x))

Pari števil

Najprej poglejmo, kako dobimo vsoto števk števila. En način je, da si pripravimo pomožno funkcijo, ki kot argument dobi število in kot rezultat vrne vsoto števk, takole.

def vsotaStevk(i): v = 0 for c in str(i): v += int(c) return v

Številko smo pretvorili v niz. Ko gremo z zanko čez niz, dobivamo posamezne števke, te pretvarjamo nazaj v števila in jih seštevamo.

Gre pa tudi hitreje. Vsoto števk števila i lahko dobimo preprosto s sum(int(c) for c in str(i)) ali sum(map(int, str(i))

Preostanek je preprost: dve zanki, ena od 1 do 100, druga pa od števca prve zanke pa do 1000. Da bi spustili obe zanki do 1000, ni nobene potrebe, saj morajo imeti števila različno število mest, torej mora biti vsaj eno število 100 ali manj. (Čemu pa do 100, ne do 99? Da ne spustimo para 100, 1000! :). Za vsak par preverimo, ali imata razlicno število števk (obe števili pretvorimo v niza in primerjamo njuno dolžino) in enako vsoto. Če to drži, ju dodamo v seznam.

def pari(): p = [] for i in range(1, 101): for j in range(i+1, 1001): if len(str(i)) != len(str(j)) and vsotaStevk(i) == vsotaStevk(j): p.append((i, j)) return p

V gornjem primeru smo uporabili pomožno funkcijo vsotaStevk, enako dobro bi bilo tudi brez nje.

def pari(): p = [] for i in range(1, 1001): for j in range(i+1, 1001): if len(str(i)) != len(str(j)) and sum(int(c) for c in str(i)) == sum(int(c) for c in str(i)): p.append((i, j)) return p

Veliko hitrejše pa je, če uporabimo nekaj trikov. Pripravimo si lahko tabelo, v kateri za vsako številko vnaprej izracunamo vsoto njenih števk. Na kakšen način v spodnji rešitvi zoptimiziramo zanke, pa odkrijte sami.

def pari(): ss = [sum(map(int, str(i))) for i in range(1001)] s = [(100, 1000)] for i in range(10, 100): if ss[i] < 10: s.append((ss[i], i)) for i in range(100, 1001): if ss[i] < 10: s.append((ss[i], i)) for j in range(10, 100): if ss[i] == ss[j]: s.append((j, i)) return s

Takšna rešitev je veliko veliko hitrejša od prve, vendar pri hitrosti pridobimo predvsem po zaslugi shranjenih vsot števk, ne trikov z zankami for.

Da se bo vedelo, da se da, pa je tu še ena rešitev.

def pari(): return [(i, j) for i in range(1, 101) for j in range(i+1, 1001) if len(str(i)) != len(str(j)) and sum(map(int, str(i))) == sum(map(int, str(j)))]

Trgovinski računi

Če sem napisal, da je ves izpit lažji, kot se morda komu zdi, je to še posebej res za zadnjo nalogo. Preprosto beremo vrstice datoteke in jih splitamo s tabulatorjem. Ker sem obljubil, da se tabulator pojavlja le v vrsticah s številkami, je seznam, ki ga dobimo s split dolg en ali dva niza. Če je dolg dva niza, je drugi niz število. Ta števila seštevamo, dokler ne naletimo na vrstico, v kateri je prvi niz enak skupaj. Tedaj vrnemo True, če je vsota enaka drugi številki in False, če ni. Če besede "skupaj" ni v racunu in se zanka "izteče", pa vrnemo False.

def preveriRacun(fname): vsota = 0 for l in file(fname): s = l.split("\t") if len(s) != 2: continue if s[0] == "skupaj": return vsota == float(s[1]) else: vsota += float(s[1]) return False

To je vse.

Vse skupaj

Zberimo skupaj rešitve vseh nalog, se pravi celotnega izpita, kakršne bi lahko napisal študent, ki se ni lotil nekoliko naprednejše snovi, izpeljevanja seznamov in ki se ni domislil kakih posebnih trikov.

# Naloga 1 def starost(EMSO): dan = int(EMSO[:2]) mesec = int(EMSO[2:4]) leto = 1000+int(EMSO[4:7]) if leto < 1800: leto += 1000 starost = 2009-leto if mesec == 1 and dan <= 26: starost += 1 return starost # Naloga 2 def bomboni(s): naj = max(s) damo = 0 for i in s: damo += (naj - i) return damo # Naloga 3 def podobna(beseda): bs = set(beseda) najCrk = 0 for enaBeseda in besede: skupnih = len(bs & set(enaBeseda)) if skupnih > najCrk: najCrk = skupnih najBeseda = enaBeseda return najBeseda # Naloga 4 def vsotaStevk(i): v = 0 for c in str(i): v += int(c) return v def pari(): p = [] for i in range(1, 101): for j in range(i+1, 1001): if len(str(i)) != len(str(j)) and vsotaStevk(i) == vsotaStevk(j): p.append((i, j)) return p # Naloga 5 def preveriRacun(fname): vsota = 0 for l in file(fname): s = l.split("\t") if len(s) != 2: continue if s[0] == "skupaj": return vsota == float(s[1]) else: vsota += float(s[1]) return False

Krajša, a ne pretirano svinjska rešitev izpita pa je takšna.

# Naloga 1 def starost(EMSO): dan, mesec = int(EMSO[:2]), int(EMSO[2:4]), leto = (2000 if EMSO[4]=="0" else 1000)+int(EMSO[4:7]) return 2009 - leto + (mesec == 1 and dan <= 26) # Naloga 2 def bomboni(s): return max(s) * len(s) - sum(s) # Naloga 3 def podobna(beseda): return max(besede, key=lambda x: set(beseda.lower()) & set(x)) # Naloga 4 def pari(): p = [] for i in range(1, 1001): for j in range(i+1, 1001): if len(str(i)) != len(str(j)) and sum(int(c) for c in str(i)) == sum(int(c) for c in str(i)): p.append((i, j)) return p # Naloga 5 def preveriRacun(fname): vsota = 0 for l in file(fname): s = l.split("\t") if len(s) != 2: continue if s[0] == "skupaj": return vsota == float(s[1]) else: vsota += float(s[1]) return False
Последнее изменение: среда, 10 августа 2011, 10:20