Rešitve kolokvija

Primerjanje seznamov

Napišite funkcijo primerjaj(s, t) k primerja dva (neprazna) seznama. Če sta seznama enako dolga in so vsi elementi s manjši od istoležnih elementov t, naj vrne True, sicer False.

Prva, najbolj preprosta (v ne nujno najboljšem pomenu besede - recimo "nesofisticirana" ;) rešitev je takšna.

def primerjaj(s, t): if len(s) != len(t): return False for i in range(len(s)): if s[i] >= t[i]: return False return True

Ko programiramo, zelo pogosto uporabljamo tale vzorec: z zanko gremo prek nečesa (seznama, niza, ali česa drugega, kar bomo spoznali v tem semestru), dokler ne naletimo na tisto, kar iščemo (ali, kot v tem primeru, tisto, česar nočemo). Ko se to zgodi, prekinamo zanko; če gre za funkcijo, vrnemo, kar smo našli, ali pa True (kot znak, da tisto, kar hočemo, obstaja) ali, v tem konkretnem primeru, False (kot znak, da smo našli tisto, česar nočemo). Če tistega ne najdemo, vrnemo privzeto vrednost ali kaj takšnega.

V zanki, ki smo jo napisali zgoraj, se namreč dogaja tole: z i štejemo od 0 do toliko, kolikor elementov ima seznam. V vsakem koraku primerjamo i-ti element prvega in drugega seznama (s[i] in t[i]) in če se zgodi, kar se ne sme zgoditi (s[i] >= t[i]) nemudoma vrnemo False. Če se prepovedana reč nikoli ne zgodi, seznama pohvalimo tako, da vrnemo True.

Pred zanko preverimo še, ali sta seznama enako dolga in vrnemo False, če nista. To je dobro iz dveh razlogov. Prvič: tako zahteva naloga in vedno je dobro storiti, kot zahteva naloga. Drugič, recimo, da sta seznama različnih dolžin - naj ima s, na primer, deset elementov in t samo pet (torej od t[0] do t[4]). Ko bi zanka for i in range(len(s)) prilezla do i = 5, bi v if s[i] >= t[i] zahtevali t[5], tega pa ni in bi dobili napako Index out of range.

Opisani vzorec - z zanko grem prek nečesa, dokler nečesa ne najdem - je tudi vzorec, na katerega smo pozorni pri učenju programiranja. Gre za enega osnovnih "gradnikov" programov. Spoznamo ga, čim imamo zanko in pogojni stavek. Po mojih izkušnjah imajo mnogi študenti - najsibo na pedagoški ali računalniški fakulteti z njim težave tudi še na izpitu. Ko predavam, ga poskušam naučiti tako, da s študenti izvajamo igro, v kateri, recimo, govorim števila, oni pa mi morajo povedati, ali je bilo med povedanimi števili tudi kakšno sodo. "Algoritem", ki ga izvajamo, ko rešujemo to nalogo, je natančno gornji vzorec.

Tipična napaka, ki jo delajo tisti, ki se še učijo programiranja, je tale:

# Ta zanka ne deluje pravilno! for i in range(len(s)): if s[i] >= t[i]: return False else: return True

Tako napisana zanka že za prvi element vrne False ali True. Drugega in naslednjih sploh ne pogleda. Napaka najbrž izvira iz tega, da učenec razmišlja o "sicer", vendar ga postavi znotraj if-a, ker elsei pač nastopajo znotraj if-ov. Če hočemo to razčistiti (uspeh pa je zgolj zmeren), moramo pri poučevanju poudariti, da gre za "sicer" v smislu "če se za noben element v zanki ni zgodilo, da", ne pa "če se za i-ti element ni zgodilo, da".

Python tale, slednji besednjak celo podpira. Napišemo lahko

def primerjaj(s, t): if len(s) != len(t): return False for i in range(len(s)): if s[i] >= t[i]: return False else: return True

Razlika je - bodite pozorni! - v tem, da je zdaj else poravnan s for-om ne z if-om. Semantično (torej v smislu pomena programa) pomeni tole: koda znotraj else se izvede, če se zanka ni prekinila (zaradi return-a, break-a ali česa hujšega, česar še ne poznamo). V praksi se bo takle else po for-u vedno pojavljal, kadar imamo znotraj zanke if (in znotraj njega vedno break - kot bomo povedali v naslednjem odstavku). Konceptualno tedaj pomeni točno to, o čemer smo pisali zgoraj: to je else za vsemi if-i, da, to je else vseh if-ov v zanki. Zgodi se le, če se ni zgodil noben if.

Čeprav gornja funkcija deluje, v prvi rešitvi else-a nismo napisali, saj ni potreben. V funkciji je namreč return; če je pogoj izpolnjen, je izvajanje funkcije končano in tako ali tako ne pridemo do kode, ki se skriva v else-u. Zato je else po for (ali while) potreben le, kadar je znotraj if-a break.

Večina programskih jezikov nima else-a za zanko. Python ga ima, ker se trudi biti berljiv.

Zdaj pa dve elegantnejši rešitvi, ki temeljita na pristopih, ki jih navadno vidimo v funkcijskem programiranju. Prva uporablja funckijo zip, zadrgo, ki iz dveh seznamov naredi en seznam parov. Z zanko gremo prek tega seznama, iz njega jemljemo pare elementov in ju primerjamo.

def primerjaj(s, t): if len(s) != len(t): return False for se, te in zip(s, t): if se >= te: return False return True

Na prvi pogled rešitev ni bistveno drugačna. Tem, ki kaj dam na lepoto, je všeč, ker smo se znebili števca i in indeksiranja. Zato je tudi konceptualno jasnejša - zanka pravi, dobesedno (no, z nekoliko ustvarjalnega branja besede zip)

    za vsak par (se, te) iz seznama parov iz s in t:
        če je se večji ali enak te:
            vrni False

Prva rešitev je, če razmišljamo na ta način, veliko bolj zapletena, saj pravi, dobesedno

    za vsak i od 0 do dolžine seznama s:
        če je i-ti element s večji ali enak i-temu elementu t:
            vrni False

Koliko pomeni razlika začetniku, nimam pojma. Mogoče je potrebno razlikovati tudi med študentom, ki je koncepta indeksiranja vajen iz matematike, kjer stalno piše reči, kot je x_i, in učencem, ki česa takega še ni nikoli videl. Po drugi strani je res, da bi se tudi slednji pač moral navaditi indeksiranja, če se hoče naučiti programirati.

V funkcijskem programiranju, ki ga bomo v tem semestru bežno spoznali, se pogovarjamo odločneje, skoraj tako kot matematiki. Naloga pravi, da mora funkcija povedati, ali drži, da sta seznama enako dolga in je v vsakem paru istoležnih elementov iz s in t oni iz s-ja manjši od tistega iz t-ja. Če pravimo, da mora funkcija vrniti to, potem naj to tudi vrne:

def primerjaj(s, t): return len(s) == len(t) and all(se < te for se, te in zip(s, t))

Palindromi

Napišite funkcijo ali_palindromna(s), ki kot argument dobi seznam števil s, ter vrne True, če so vsa števila v seznamu palindromna oz. False, če je vsaj eno tako, ki ni. Število je palindromno, če se iz obeh smeri bere enako. Števila 121, 545, 112211, 8 so palindromna, medtem ko 123, 546, 112213, niso.

Ta naloga zahteva uporabo istega koncepta kot prejšnja: gremo čez seznam in za vsak element pogledamo, ali izpolnjuje določen pogoj. Če ga ne, takoj vrnemo False. Če so ga vsi izpolnjevali, vrnemo True.

Pri reševanju nam pride prav še nekaj drugega: nalogo razbijemo na podnaloge. Če hočemo za vsako število preveriti, ali je palindrom, za začetek napišemo funkcijo, ki za eno samo število pove, ali je palindromno ali ne.

Za začetek predpostavimo, da znamo malo Pythona in vemo, da lahko s funkcijo str spremenimo število v niz s tem številom. Odtod naprej bi nalogo nekoliko štorasto rešili takole.

def ali_palindromno(n): s = str(n) for i in range(len(s)): if s[i] != s[len(s) - i - 1]: return False return True

Podano število n pretvorimo v niz s, gremo z indekom i od začetka do konca in primerjamo i-ti in, uh, len(s) - i - 1-ti znak.

Tole indeksiranje je seveda zoprno in kar kliče po napakah. Da se prepričamo, da je potrebno odšteti 1, moramo prav razmisliti: če ima niz pet znakov, moram primerjati ničtega s četrtim. Če je torej i enak 0 in len(s) enak 5, bo len(s) - i enak 5, kar je za 1 preveč, zato bom pisal len(s) - i - 1. Ko se bo i povečal za 1, se bo len(s) - i - 1 zmanjšal za 1, torej je vse prav.

Ko programiramo, moramo veliko razmišljati. Misliti na veliko stvari, je težko in dobro je, če nam ni potrebno razmišljati o tako trivialnih rečeh, kot je indeksiranje. Zato pozna Python tudi indeksiranje z desne: -1 je prvi element z desne, -2 drugi in tako naprej. Enico je potrebno še vedno odštevati, a vsaj len-a smo se znebili:

def ali_palindromno(n): s = str(n) for i in range(len(s)): if s[i] != s[-i - 1]: return False return True

(Vsega so krivi matematiki. Z največjim veseljem bi lahko pisali s[-i], a kaj, ko sta leva in desna enota za seštevanje enaki, ali, po domače povedano, -0 ni bistveno manj kot 0. Zato bi takrat, ko je i enak 0, primerjali elementa s[0] in s[-0], kar je očitno narobe.)

Za lepšo rešitev, se moramo spomniti, kako v Pythonu obrnemo seznam ali niz. Če je s neka reč, ki jo lahko indeksiramo na tak način kot seznam ali niz, bomo z s[::-1] dobili isto reč z desne proti levi. (Kdor ne razume, čemu vsa ta dvopičja, naj le brž ponovi snov v zvezi z rezinami!)

def ali_palindromno(n): s = str(n) return s == s[::-1]

Zdaj, ko imamo funkcijo za preverjanje palindromnosti enega števila (dobra je katerakoli od teh treh), še enkrat poženemo zanko čez ves seznam. Če naletimo na nepalindromno število, zatulimo False, sicer potrpežljivo meljemo naprej in če se vse srečno izteče do konca, vrnemo True.

def ali_palindromna(s): for e in s: if not ali_palindromno(e): return False return True

V slogu funkcijskega programiranja, ki mu bomo posvetili kako predavanje v drugem semestru, smo ponovno jedrnati: funkcija mora povedati, ali so vsa števila palindromna:

def ali_palindromna(s): return all(str(n) == str(n)[::-1] for n in s)

Deljenje niza

Nize v Pythonu lahko pomnožimo s številom: "bla"*3 vrne "blablabla". Napišite funkcijo deli_niz(s, k), ki niz "deli" s številom k. Torej: deli_niz(s, k) mora vrniti tak niz, da bi, če ga pomnožimo s k, spet dobili s. Če niz ni sestavljen iz k ponovitev nekega niza, naj funkcija vrne None.

Kaj preverja naloga z deljenjem niza, ne vem. Naloga ni prav posrečena. (Kritizirati jo smem brez skrbi, da se komu zamerim, ker je pravzaprav moja. ;)

No, v bistvu preverja, ali znamo razmisliti, kaj pravzaprav računamo, kakšno rešite pričakujemo. Naloga ne zahteva programerskih veščin, temveč samo razmislek.

Trik je v tem, da moramo najprej predpostaviti, da je niz "deljiv". Imamo torej, recimo, niz s dolžine 12, ki ga delimo s k = 3. Če je deljiv s 3, bodo rezultat prvi štiri črke niza, s[len(s) // k] (saj se spomnimo - // pomeni celoštevilsko deljenje; 12 / 3 = 4.0 in 12 // 3 = 4).

Rezultat smo torej že izračunali. Preveriti moramo le še, ali je niz v resnici deljiv, torej, ali je sestavljen iz k ponovitev tega podniza. Spomnimo se, da lahko niz pomnožimo s k in dobimo niz sestavljen iz k ponovitev tega niza. Torej

def deli_niz(s, k): q = s[len(s) // k] if q * k == s: return q

Če smo že pri prejšnjih dveh nalogah pogledali malo naprej (a ne skrbite, funkcijskemu programiranju bo v resnici posvečeno le eno predavanje!) tudi tule poglejmo v to smer. Tole sicer nima neposredne zveze s funkcijskim slogom programiranja, razen te, da moramo pri njem vse, kar hočemo povedati, zapisati v enem samem izrazu. Tule bi radi, da funkcija vrne q, če je q * k enak s, sicer pa None. Dobesedni prevod v Python:

def deli_niz(s, k): q = s[len(s) // k] return q if q * k == s else None

To sicer še ni en sam izraz, saj predtem računamo q. Če se ga res želimo znebiti, na vsa mesta, kjer se pojavlja q vstavimo s[len(s) // k].

def deli_niz(s, k): return s[len(s) // k] if s[len(s) // k] * k == s else None

Loto

Sestavljanje kombinacij

Prva funkcija, recimo ji generiraj(n), bo kot vhodni podatek dobila število kombinacij, ter vrnila seznam teh kombinacij. Eno loto kombinacijo sestavlja seznam naključnih sedmih števil od 1 do 39, pri čemer se števila znotraj kombinacije ne smejo ponavljati.

Pri reševanju te naloge se bomo delali, da poznamo modul random in njegovo funkcijo sample(s, k), ki iz podanega seznama (ali česa podobnega) s vrne naključen izbor k elementov, pri čemer istega nikoli ne izbere dvakrat.

Z njo je reševanje preprosto: sestavimo prazen seznam in vanj dodamo ustrezno število kombinacij.

import random def generiraj(n): kombinacije = [] for _ in range(n): izbor = random.sample(range(1, 40), 6) kombinacije.append(izbor) return kombinacije

Funkcija spet uporablja enega pogostih vzorcev: naredimo prazen seznam in v zanki vanj dodajamo stvari. Včasih se predtem v zanki pojavi še kak pogoj, ki ga morajo izpolnjevati reči, ki jih dodajamo. Tule ga ni.

Opozorimo na par detajlov. Zanko for tule uporabljamo zgolj za ponavljanje. Veliko lepše bi bilo napisati

def generiraj(n): kombinacije = [] repeat n: izbor = random.sample(range(1, 40), 6) kombinacije.append(izbor) return kombinacije

Vendar takšnega stavka repeat ne moremo napisati iz dokaj banalnega razloga. Namreč: Python česa takšnega nima. To je precejšnja škoda, saj bi bil s tem veliko prijetnejši za prve otroške korake iz programiranja. Ker ga nima, pa jim moramo razlagati, kaj je to range(n), ali, najbrž boljše, preprosto rečemo, da so for i in range(n) "magične besede", ki pomenijo "n-krat ponovi". Zakaj se reče tako, pa da bodo izvedeli kdaj drugič.

Spremenljivki, ki smo jo uporabili za števec, smo dali čudno ime: _. Bolj običajno bi bilo pisati i, v zadnjem času pa se za spremenljivke, ki jih ne potrebujemo, uveljavlja ime _. Ko bralec programa vidi _ tako ve, da gre samo za "spremenljivko zaradi spremenljivke"; potrebujemo jo le, ker jo zahteva stavek for.

Spremenljivka izbor ni posebej nujna: namesto

izbor = random.sample(range(1, 40), 6) kombinacije.append(izbor)

bi lahko pisali

kombinacije.append(random.sample(range(1, 40), 6))

In zakaj nismo? Zaradi berljivosti. Kdo more na prvi pogled videti, čigav argument je šestica?

Mimogrede se spotaknimo ob range: zakaj range(1, 40) in ne range(1, 39)? Vemo, ker je spodnja meja vključena, zgornja ne. To je navadno zelo praktično, tule pa ne preveč. Kaj moremo.

Če vas že ves čas strašim s funkcijskim programiranjem, hočem reči, če vam že vas čas cedim sline po njem, naj bo tako tudi tu. Vrniti hočemo seznam, ki bo vseboval n-krat random.sample(range(1, 40), 6). Če to hočemo, to pač storimo.

def generiraj(n): return [random.sample(range(1, 40), 6) for _ in range(n)]

Preverjanje kombinacij

Druga funkcija, recimo ji preveri(s, dobitna), dobi kot vhodni podatek seznam vplačanih kombinacij s, ter izžrebano kombinacijo dobitna, zapisano kot seznam števil. Funkcija naj izpiše dobitne kombinacije, pri čemer napiše tudi kakšen dobitek je zadela. Dobitki se začnejo pri kombinacijah, ki se ujemajo vsaj v štirih številkah.

Za preverjanje najprej napišimo funkcijo, ki pove, koliko skupnih števil vsebujeta dva seznama. Pogost vzorec, ki ga moramo znati spisati za to, je preštevanje: zanka prek nečesa, znotraj nje pa pogoj, ki prišteva k števcu.

def stevilo_skupnih(s, t): skupnih = 0 for e in s: if e in t: skupnih += 1 return skupnih

Tule, konkretno, za vsak element s-a pogledamo, ali je v t-ju in v tem primeru k skupnih prištejemo 1.

Ko bomo znali malo več Pythona, bo postala funkcija trivialna: oba seznama spremenimo v množici, izračunamo njun presek in vrnemo njegovo velikost.

def stevilo_skupnih(s, t): return len(set(s) & set(t))

Ostalo nam je le še preleteti seznam in izpisati vse, ki kombinacije, v katerih se pojavljajo vsaj štiri števila iz zmagovalne kombinacije.

def preveri(s, dobitna): for k in s: if stevilo_skupnih(k, dobitna) >= 4: print(dobitna)