Prva predavanja bomo žrtvovali za ponavljanje tega, kar že znate. Nov predavatelj, pa še iz tujih krajev, prinese s seboj nove besede; pa besednjak raje uskladimo na temah, ki so vam že znane. Mimogrede bomo tudi videli, koliko v resnici že znamo. Tudi sicer ponavljanje ne škodi; bomo že poskrbeli, da bomo ob njem izvedeli tudi kaj novega.

Ugibanje števila

Najprej bomo reševali približno tole nalogo z vašega izpita.

Zapišite program, ki si bo na začetku izmislil število, nato pa ga bo uporabnik uganjeval. Če bo uporabnik število uganil, mu bo izpisal »Bravo!«, če bo vpisal manjše število, mu bo izpisal »Moje število je večje!«, če pa večje, bo izpis »Moje število je manjše!«. Igra se naj ustavi takrat, ko uporabnik vpiše pravilno število ali pa se 5 krat zmoti.

Da bo manj trivialna, bomo izpisovali še številko poskusa in na koncu morebitnega neuspešnega ugibanja igralcu namenili neprijazno besedo.

Očitno bomo imeli zanko, ki se bo ponovila - kolikokrat? Največ petkrat, morda pa tudi manjkrat. Kaj bomo uporabili, for ali while? V Pythonu (in drugih jezikih s podobno obliko zanke for) bom zanko for uporabil, kadar bi rad "prehodil" neko reč (seznam, niz, datoteko ali kaj drugega, kar se da "prehoditi") ali kadar vnaprej vem, kolikokrat bom ponovil zanko (v tem primeru prehodim interval števil - range(5), recimo, so vsa števila od 0 do 5). Zanko while bom uporabil, če ne vem, kolikokrat nameravam ponoviti neko reč.

Če se odločim narobe, lahko še vedno napišem delujoč program, le nekoliko bolj neroden bo. Z zanko while lahko tudi štejem in simuliram zanko for; zanko for pa lahko vedno tudi prekinem z break in tako simuliram to, kar sicer dela zanka while.

Ravno tale primer je nekje vmes. Vem, kolikokrat bom ponovil, lahko pa bom tudi manjkrat. Izkaže se, da je nekoliko prikladnejša zanka for, a predvsem zaradi neke hecne reči, ki ji jo lahko v Pythonu pripnemo.

import random izmisljeno = random.randint(1, 20) for ugib in range(5): stevilo = int(input("{}. poskus: ".format(ugib + 1))) if stevilo == izmisljeno: print("Bravo!") break elif stevilo < izmisljeno: print("Moje število je večje!") else: print("Moje število je manjše!") else: print("Luzer.")

Ker bomo delali z naključnimi števili, uvozimo modul random. Takoj zatem ga uporabimo, da nam izžreba naključno število. (Mimogrede: vas je že kdaj zmotilo vprašanje, kako računalnik "proizvaja" naključna števila? Računalnik, kot po enem semestru programiranja že veste, vedno izračuna natančno tisto, kar mu rečemo in v njem ni nobene kocke ali kovanca. Nekoč je nekdo sprogramiral modul random. Kaj računa le-ta, da vsakič naračuna nekaj drugega in nas sovražnik v igrici vsakič napade izza drugega grma?)

Zdaj pride zanka: for ugib in range(5) preberem kot "petkrat ponovi", spremenljivka poskus pa bo štela poskuse. Uporabniku nato povemo, za kateri poskus gre in počakamo, da vnese število (funkcija input). Kar vnese, je niz, ki ga takoj (funkcija int) spremenimo v (celo) število.

Zakaj ugib + 1 - mu ne bomo povedali številke trenutnega poskusa? Čemu +1? Zato: ljudje imajo čudno navado, da štejejo od 1 in ne od 0, kot računalniki. Ničtemu poskusu ljudje rečejo prvi poskus. (Ljudje imajo za takšno štetje sicer čisto dobre argumente: ko opravijo prvi in drugi poskus (po človeškem štetju), so opravili dva poskusa. A računalnikarji imamo še boljše razloge, da štejemo od 0; programski jeziki, v katerih so šteli od 1, so izumrli, osovraženi ali akademski, in to z dobrim razlogom: nerodni so.)

Skratka, spremenljivka poskus bo imela vrednosti od 0 do 4, program pa mora izpisovati številke od 1 do 5. Zato +1. Druga možnost bi bila, da bi zanko napisali kot for poskus in range(1, 6). S tem bi se izognili prištevanju, vendar bi bil program manj pregleden za vse, ki for i in range(5) vidimo isto, kot če bi pisalo "petkrat ponovi".

Sledijo pogoji. Kakorkoli trivialni so, tudi o njih se da veliko povedati. Kot učitelj programiranja si ob tem, kako so napisani, veliko mislim o študentu, ki jih je napisal.

Prvi je nesporen: če smo uganili, potem bravo in nehamo. Sledi elif: če nismo uganili, preverimo, ali je število premajhno. Bi lahko namesto elif pisali tudi samo if? Stavek elif pomeni "če prvi pogoj ni izpolnjen, preveri tole", if pa "preveri tole". Razlika je tule očitno nepomembna: če je prvi pogoj izpolnjen, imamo break in tako ali tako sploh ne pridemo do drugega pogoja. Kaj napisati, je stvar okusa: sam sem pisal elif, da mi je tudi, ne da bi moral opaziti break, jasno, da bomo prišli sem, le če nismo uganili števila.

Boleč je tretji pogoj. Tule bi mnogi (in najbrž ste mnogi) pisali elif stevilo > izmisljeno. Tega se ne dela. Vem, da število ni enako in vem, da ni manjše. Torej je večje. Zato samo else.

Bolj drastičen primer je takle program:

if palckov != 7: print("Palčkov ni sedem!") elif palckov == 7: print("Palčkov je sedem")

Ob tem Python pomisli: ne me zezat. Preveril sem ali je število palčkov različno od 7. Če ugotovim, da število palčkov ni različno od 7, zakaj naj potem preverjam, ali to slučajno pomeni, da jih je 7?! Iz previdnosti mogoče? Ne, tule zadošča else.

Če kdo meni, da je potrebno poudariti, da je palčkov sedem in da se bo naslednji del programa ukvarjal s to situacijo, to napišemo v komentar.

if palckov != 7: print("Palčkov ni sedem!") else: # Palčkov je še vedno sedem, vse je OK print("Palčkov je sedem")

A to pride v poštev le pri daljših programih z bolj zapletenimi pogoji.

S tem je program v glavnem napisan. Ostane le še opozorilo na mentalni primanjkljaj. Pri tem nam pride prav, da lahko v Pythonu na koncu zanke dodamo else. Kot se spomnimo (se?), se tisto, kar zapišemo v takšen else zgodi, če se zanka ni prekinila z break. Večina jezikov česa podobnega nima (točneje: nobenega drugega takšnega ne poznam) in očitno je mogoče živeti tudi brez tega. Vendar nam pride zelo zelo prav.

Kaj bi storili, če po zanki ne bi mogli napisati else? Običajni vzorec je takšen:

import random izmisljeno = random.randint(1, 20) uspesno = False for ugib in range(5): stevilo = int(input("{}. poskus: ".format(ugib + 1))) if stevilo == izmisljeno: print("Bravo!") uspesno = True break elif stevilo < izmisljeno: print("Moje število je večje!") else: print("Moje število je manjše!") if not uspesno: print("Luzer.")

Uvedli smo spremenljivko uspesno, ki v začetku predpostavi, da tekmovalec ne bo uspešen. Le če mu uspe, jo postavimo na True in preprečimo neprimerne besede ob koncu igre.

Če je že tako, lahko napravimo program malo berljivejši, če prestavimo ves izpis na konec.

import random izmisljeno = random.randint(1, 20) uspesno = False for ugib in range(5): stevilo = int(input("{}. poskus: ".format(ugib + 1))) if stevilo == izmisljeno: uspesno = True break elif stevilo < izmisljeno: print("Moje število je večje!") else: print("Moje število je manjše!") if uspesno: print("Bravo!") else: print("Luzer.")

Takle vzorec je kar pogost - predvsem v drugih programskih jezikih. V tej konkretni nalogi pa se lahko spremenljivke uspesno tudi znebimo, saj lahko uspešnost enostavno preverimo tudi drugače.

import random izmisljeno = random.randint(1, 20) for ugib in range(5): stevilo = int(input("{}. poskus: ".format(ugib + 1))) if stevilo == izmisljeno: break elif stevilo < izmisljeno: print("Moje število je večje!") else: print("Moje število je manjše!") if stevilo == izmisljeno: print("Bravo!") else: print("Luzer.")

Prva rešitev - ona z else po zanki, je seveda elegantnejša. Kar smo dobili sedaj, pa je precej podobno rešitvi, ki bi jo napisali z while.

import random izmisljeno = random.randint(1, 20) stevilo = -1 poskus = 1 while poskus <= 5 and stevilo != izmisljeno: stevilo = int(input("{}. poskus: ".format(poskus))) if stevilo < izmisljeno: print("Moje število je večje!") elif stevilo > izmisljeno: print("Moje število je manjše!") poskus += 1 if stevilo == izmisljeno: print("Bravo!") else: print("Luzer.")

Kadar se odločimo za while, čeprav bi bil naravnejši for, bomo to plačali tako, da bomo morali šteti sami, namesto da bi za nas štela zanka. V tem primeru smo morali na začetku postaviti poskus na 1 in ga na koncu zanke vestno povečali za 1. Če ga pozabimo, se program ne bo nikoli končal.

Pogoj v glavi zanke se bere popolnoma naravno: ponavljej, dokler je število poskusov manjše ali enako 5 in dokler igralec ne ugane števila. Da bi lahko napisali takšen pogoj, pa mora imeti spremenljivka stevilo vrednost že pred začetkom zanke, torej še preden igralec prvič ugiba. Dali ji bomo neko vrednost, ki bo zanesljivo napačna, recimo -1.

Znotraj zanke sta zdaj if in elif, s pogojema "ali je večje" in "ali je manjše". Zdaj pa moramo uporabiti ifelse in napisati pogoj, da se izognemo morebitni tretji možnosti, namreč, da bi bila številka enaka. Za ta primer bo namreč poskrbel pogoj v while.

Stranpot: kakšen interval naključnih števil določiti?

V izpitni nalogi je manjkalo navodilo, kako velika števila naj si izmišlja računalnik. Kakšen razpon bi bil smiseln? Po mojem, bi bilo dobro vzeti tak razpon, da bi bil igralec, ob pametni igri, uspešen v polovici primerov. Kako določiti tak interval? Z vprašanjem se bomo pozabavali, ker gre v bistvu za računalniški problem, ne matematični (no, odvisno od tega, kje postavimo mejo med računalništvom in matematiko.

Igro bomo postavili malenkost drugače. Človekova naloga je, da izve, katero število si je izmislil računalnik. Z izve hočemo povedati tole: ni nam dovolj, da ugane, hočemo, da s spraševanjem ugotovi, za katero število gre. Poleg tega nam je vseeno, ali računalnik potrdi, da gre za to število (kaj mislim s tem, bomo videli vsak čas). Končno, dogovorimo se še, da bodo vprašanja, ki jih lahko postavljamo, vedno oblike "ali je število večje ali enako od". Kasneje bomo reč bistveno posplošili, za zdaj pa bodimo zadovoljni s temi omejitvami.

Da bo razmišljanje lažje, se dogovorimo še, da si računalnik izmišlja števila od 0 do kolikorsižebodi, ne od 1.

Za začetek recimo, da si računalnik izmišlja samo števila do 0. Z drugimi besedami, vedno si izmisli 0. Koliko vprašanj potrebujemo, da bomo lahko s popolno zanesljivostjo vedeli, katero število si je izmislil? Nobenega, jasno. Še preden kaj vprašamo, že vemo, kaj si je izmislil, namreč 0.

Prav, v naslednji igri si računalnik izmišlja števila do 1 (torej 0 ali 1). Koliko vprašanj mu moramo postaviti, da ugotovimo, katero število si je izmislil? Enega. Vprašamo ga, ali je njegovo število večje ali enako 1. Če reče, da je, vem, da gre za 1; če ne, gre za 0.

Kaj pa, če si računalnik izmišlja števila od 0 do 3? Torej 0, 1, 2 ali 3? Tedaj potrebujem dva poskusa: najprej bom vprašal, ali je število večje ali enako 2, nato pa, ali je večje ali enako 1 oz. ali je večje ali enako 3.

Če si izmišlja števila od 0 do 7, ga bom najprej vprašal, ali je večje ali enako 3, nato ali je večje ali enako 2 oz. ali je večje ali enako 6... In tako naprej.

Z 0 poskusi lahko ugotovim eno število. Z enim dve. Z dvema poskusoma štiri. S tremi poskusi osem. S štirimi 16... In tako naprej: z n poskusi lahko zanesljivo uganem število od 0 do 2n-1 (ena moram odšteti, ker sem začel z ničlo).

Emmm, pa je res bilo nujno začeti z ničlo? Da, iz dveh razlogov. Prvi je ta, da bomo reč sprogramirali in to bo, verjemite, lažje z ničlami. Drugi je, da bi se radi ob tem še nekaj naučili. Poglejte tole sliko.

Izberimo si eno številko, recimo 5. Kakšna pot, kakšni odgovori nas pripeljejo do nje? DA NE DA. Namesto DA NE DA bi lahko napisali tudi 101. Kakšna pot nas pripelje do 0? 000. Do 1 pridemo z 001. Do 2 pridemo z 010. 3 je 011. Naprej gre 100, 101, 110, 111. Ste že slišali za dvojiški številski sistem? Odlično: prva števka nam pove, ali je število večje od 4, druga pove, ali je večje od 2 oz. 6, tretja pa, ali je večje od 1 oz. 3 oz. 5 oz. 7.

Tri dvojiške števke, trije biti, predstavljajo "drevo" s tremi nivoji in v njegovih listih je 23 različnih števk. Če bi imel na voljo osem vprašanj (osem bitov, osem števk), bi ga lahko predstavil z drevesom z osmimi nivoji, to pa bi imelo 28=256 listov, v katerih bi bilo 256 različnih števil.

Zdaj pa obljubi. Ko sem omejil igro na vprašanja tipa "ali je število večje od" in ko sem rekel, da bomo šteli od 0, sem v tolažbo obljubil, da bomo reč bistveno posplošili. In smo jo, mar ne?

"Kako?" ugovarja študent, ki ga uspavata zgodnja ura in naporno predavanje. Kje je tu kakšna posplošitev? Uh, če moram vse narisati, pa bom.

Recimo, da rešujem neko uganko, pri kateri smem postaviti tri vprašanja in vsa vprašanja so takšnega tipa, da imajo lahko le dva možna odgovora (recimo DA in NE, ali pa SEVER in JUG, ali pa LEVO in DESNO...). S tremi vprašanji lahko ločujem med osmimi stvarmi. Ne več, ne manj.

Zdaj pa ugiba še računalnik

Druga obljuba je bila, da bomo stvar sprogramirali. Napišimo torej program, ki ugiba števila med 0 in 7. Po gornjem razmišljanju smo postali tako pametni, da to res ne bo težko.

stevka = 4 stevilo = 0 for i in range(3): s = input("Je število večje ali enako {}? [d/n] ".format(stevilo + stevka)) if s == "d": stevilo += stevka stevka //= 2 print("Zamislil si si število {}".format(stevilo))

Vrstica stevka //= 2 deli spremenljivko števka z 2. Pomeni torej isto kot stevka = stevka // 2. Dvojno poševnico uporabljamo zato, ker hočemo celoštevilsko deljenje. Če ne bi storili tako, da bi nas program v naslednjem koraku vprašal, ali je število večje od 2.0, to pa ne bi bilo lepo.

Podrobneje pa ga ne bomo razlagali. Kdor ga ne razume, naj še enkrat premisli

Program predpostavlja, da potrebujemo ravno tri ugibanja. Če bi ga želeli napisati splošneje, bi lahko uporabili while - vse drugo ostane natančno takšno kot prej.

stevka = 4 stevilo = 0 while stevka > 0: s = input("Je število večje ali enako {}? [d/n] ".format(stevilo + stevka)) if s == "d": stevilo += stevka stevka //= 2 print("Zamislil si si število {}".format(stevilo))

Po treh poskusih bo stevka enaka 0 in igre bo konec. Tako kot prej. Lepota tega programa pa je v tem, da lahko spremenimo stevka = 4 v stevka = 16, pa bo program ugibal števila do 31.

Smiseln razpon

Odgovoru na vprašanje o smiselnem razponu pa sem se izognil! Zdaj lahko odgovorimo splošnejše: igra, pri kateri odgovarjamo z DA ali NE in pri kateri ima igralec na voljo n poskusov, bo poštena, če je potrebno razlikovati med 2n + 1 rečmi. Predstavljajte si drevo. Če bi razlikovali med 2n rečmi, bi vedno prišli do pravilnega odgovora. Če število reči podvojimo, dobi drevo še en nivo, vsaka reč se razdeli še na dvoje. Z dovoljenimi n vprašanji je igralec, ki ugiba, omejil izbiro na le še dve stvari. Ker zdaj ne sme več spraševati, mora ugibati na slepo in uganil bo v polovici primerov. Tako imata oba igralca enako verjetnost za zmago oz. poraz.

Ob tej analizi smo predpostavili, da so vse reči enako verjetne. Vendar ni nujno tako - ne na zadnjem nivoju, ne prej. Kakšna je poštena igra takrat?

S tem se ukvarja teorija informacij in tole je bil pravzaprav preprost uvod vanjo. Zanjo žal nimamo časa, niti ni to ravno snov tega predmeta. Povejmo le, da je povsem preprosto izračunati poprečno število potrebnih vprašanj pri podanih verjetnostih reči in pri optimalni igri. Če bo čas, pa se k temu povrnemo kdaj kasneje - in mimogrede izvemo še, kako pravzaprav deluje stiskanje datotek, kot recimo zip.

Kodiranje vojaka Ryana

Druga izpitna naloga je šla takole.

Vojska za komunikacijo uporablja t.i. fonetično abecedo, ki deluje tako, da se vsaka črka zamenja z besedo, ki jo predstavlja. Sledi spisek besed za katere privzemite, da so shranjene (shranjene so le besede npr. Alfa in ne A – Alfa) v spodnjem vrstnem redu v tabeli v_abc.

A – Alfa G – Golf M – Mike S – Sierra Y - Yankee B - Beta H – Hotel N – November T – Tango Z - Zulu C - Charlie I – India O – Oscar U – Uniform D - Delta J – Juliet P - Papa V – Victor E – Echo K – Kilo Q - Quebec W – Whiskey F - Foxtrot L - Lima R - Romeo X – Xray

Vsebina seznama v_abc je tako: v_abc = ["Alfa", "Beta","Charlie", … , "Zulu"]

a.) Napišite funkcijo, ki bo prebrano besedilo (brez šumnikov) zakodirala v vojaško fonetično abecedo. Presledki se ne kodirajo, označite jih z znakom "---", morebitna ločila pa ignorirajte.

Avtorju izpita, ki je nalogo ovrednotil z 20 točkami, moramo priznati, da je duhovit človek. Rešitev je namreč dolga eno vrstico,

def kodiraj(s): return "\n".join(v_abc[ord(c) - 65] if "A" <= c <= "Z" else "---" * (c == " ") for c in s.upper())

Žal pa takole še ne znamo (vendar bomo, bomo!). Rešitev, ki bi jo, upam, smeli pričakovati od pol leta starih programerjev, je takšna.

def kodiraj(besedilo): kodirano = "" for znak in besedilo.upper(): if "A" <= znak <= "Z": kodirano += v_abc[ord(znak) - ord("A")] + "\n" elif znak == " ": kodirano += "---\n" return kodirano

Tako, kot smo sprogramirali zdaj, gre predvsem za vajo iz razumevanja tega, kar se da početi z nizi. V prvi vrstici funkcije smo sestavili prazen niz (OK, trivialno). V drugi moramo vedeti, da lahko gremo z zanko for prek niza; kar dobivamo, so posamezni znaki niza. Namesto prek besedilo se z zanko sprehodimo prek besedilo.upper(), torej prek besedila, pretvorjenega v same velike črke. Besedilo naloge sicer ne zahteva, da moramo sprejemati tudi besedila, ki vsebujejo male črke - a nič nas ne stane. V naslednji vrstici se spomnimo, da lahko nize (ali posamezne znake) primerjamo med seboj; z "A" <= znak <= "Z" preverimo, ali gre za znak med A in Z.

V naslednji vrstici je "najtežja" reč: spomniti se moramo na funkcijo ord(c), ki ji podamo znak in vrne kodo ASCII tega znaka. Kakšne so kode, nas niti ne zanima, pomembno je, da gredo po vrsti; znak B ima za 1 večjo kodo kot A, C za dve večjo ... (V resnici ima A kodo 65, B 66, C 67 in tako naprej). Če od znaka odštejemo kodo znaka A, bomo dobili 0 za A, 1 za B, 2 za C in tako naprej. Številko, ki jo tako dobimo, lahko uporabimo kot indeks v seznam v_abc, drži? Pri znaku A želimo ničti element, pri B prvega, pri C drugega... Besedo iz tabele v_abc prištejemo v končni rezultat. Za njim dodamo še "\n", kar je še nekaj, kar moramo vedeti o nizih: znak, ki ga zapišemo z \n, pomeni prehod v novo vrstico.

Nato poskrbimo še za presledek, ki ga zamenjamo z ---. Tu uporabimo elif, ne else: če ne gre za črko, preverimo, ali gre za presledek. Če ni ne črka ne presledek, v kodirano ne dodamo ničesar.

Funkcija vrne rezultat, kodirano. Tole je pomembno: na redke čase si bom zaželel, da napišete funkcijo, ki nekaj izpiše. V vseh ostalih primerih si bom želel, da funkcija nekaj vrne; celo, če bo pisalo, da mora funkcija nekaj izračunati, naj se razume, da mora funkcija rezultat izračuna vrniti, ne izpisati. Zakaj? Zato ker s funkcijami, ki izpisujejo, namesto da bi vračale, nimam kaj početi! Predstavljajte si, da bi funkcija math.sqrt(x) izpisala koren podanega števila (vrnila pa ne bi ničesar). Recimo, da bi hotel izračunati dolžino hipotenuze pravokotnega trikotnika s stranicama a in b. Napisal bi c = math.sqrt(a ** 2 + b ** 2). Kakšen bi bil po tem c? Bi morda vseboval dolžino hipotenuze? Nak, vseboval bi nič, None, ker bi math.sqrt dolžino, hura!, izpisala, namesto da bi jo vrnila.

Otežimo si delo! Predpostavimo, da nimamo funkcije ord (ali pa ne vemo zanjo).

def kodiraj(besedilo): kodirano = "" for znak in besedilo.upper(): if "A" <= znak <= "Z": for beseda in v_abc: if beseda[0] == znak: kodirano += beseda + "\n" break elif znak == " ": kodirano += "---\n" return kodirano

V primerjavi s prejšnjim programom smo tule fasali še eno zanko. V njej gremo prek vseh besed v v_abc (for beseda in v_abc). Ko naletimo na tisto, katere prva črka je enaka iskani črki if beseda[0] == znak, pripnemo to besedo in znak \n na konec niza z rezultatom ter z break prekinemo zanko.

Je ta break res potreben? Bi program brez njega dal enak rezultat?

Razmislimo. Brez njega bi zanka tekla naprej, do konca seznama v_abc. Bi naleteli še na kakšno besedo, ki se začne s pravim znakom? Ne. Tudi če spustimo zanko teči do konca, bomo dobili enak rezultat.

Čemu potem zapletati program z nepotrebnim breakom? Ker ni potrebe, da bi zanka tekla še naprej, naj ne teče naprej. S tem bomo prihranili čas, program bo hitrejši. Tule je to sicer nepomembno in neopazno, v kaki drugi podobni situaciji pa bi lahko bilo, zato se v takih primerih kar navadimo pisati break.

Naloga b?

Pozorni opazovalec je v besedilu naloge opazil skrivnostni znak a. ) pred "Napišite funkcijo, ki (...)". To bi ga utegnilo navdihniti z mislijo, da je imel sestavljalec naloge tudi idejo za kaj, pred čemer bi stal b. ). Kot poznavalec razmišljanja sestavljalcev izpitov bi rekel, da je besedilo, ki se je začelo z b. ), vendar je bilo iz milosti do študentov pobrisano. Ali pa iz hudobije: morda so želeli študente prikrajšati za enostavno nalogo in preprosto pot do tako potrebnih točk.

Rešitev nenapisane naloge je takšna:

def odkodiraj(kodirano): besedilo = "" for beseda in kodirano.split(): if beseda == "---": besedilo += " " else: besedilo += beseda[0] return besedilo

Vedeti moramo le tole: kodirano besedilo, kakršnega je vračala funkcija kodiraj, bomo razbili na posamezne besede z kodirano.split(). Zdaj nam je narediti le tole: za vsako besedo (for beseda in kodirano.split():) preverimo, ali gre za "---" in v tem primeru dodamo presledek, sicer pa prvo črko besede (beseda[0]). C'est tout.

Ko pride čas, bomo še bolj jedrnati. Rekli bomo le

def odkodiraj(kodirano): return "".join(" " if beseda == "---" else beseda[0] for beseda in kodirano.split())

Anagrami

Naloga z izpita ni popolnoma izvirna. Od ondod, od koder prihaja prepišimo in priredimo še rešitev s komentarjem.

Pri reševanju večine nalog za začetnike si lahko predstavljamo, kako bi jo reševali ročno in to rešitev prepišemo v Python. Tule pa bodo "ročne" rešitve nekoliko okorne.

"Ročno" bi nalogo reševali tako, da bi gledali črke ene besede in (v mislih) črtali črke druge. def anagram(b1, b2): crke2 = list(b2) for crka in b1: if not crka in crke2: return False else: crke2.remove(crka) return crke2 == []

Besedi sta anagrama, če smo uspeli v crke2 najti vsako črko iz crke1 (s tem, da črke iz crke2 vmes brišemo) in če so na koncu vse črke druge besede prečrtane. Konec smo napisali nekoliko jasneje, kot bi ga v praksi; v resnici bi namesto primerjanja s praznim seznamom lahko napisali return not crke2.

V nalogi se pokaže najbolj klasičen izmed vseh klasičnih vzorcev, s katerimi učitelji programiranja mučimo začetnike: zanka, znotraj katere je if, znotraj katerega je return. Vzorec je, v splošnem, takšen: imamo zanko, v kateri iščemo kaj, kar nam ni všeč. Čim najdemo kaj takšnega, zatulimo (vrnemo) Falsch! Če ne najdemo ničesar napačnega, vrnemo True. Tule imamo majhno variacijo, saj tudi na koncu ne vrnemo vedno True, temveč še na nekaj popazimo.

Obstaja tudi obratna različica, ko iščemo kaj, kar nam je všeč (in v tem primeru takoj vrnemo True. Šele če ne najdemo ničesar, kar nam ni všeč, pa vrnemo False.

Ker smo (ali bomo) učitelji, poglejmo tipično napako, ki jo tu delate učenci. Vendar si jo raje oglejmo na čistejšem primeru. Recimo, da dobimo neko besedo in nas zanima, ali vsebuje tudi kakšno črko A. (Za to sicer obstaja tudi hitrejši način, a ga tule pozabimo.)

# Tole je narobe! def vsebuje_a(beseda): for crka in beseda: if crka == "A": return True else: return False

Ta funkcija naredi tole: dela se, da bo pregledala vse črke besede (for crka in beseda). Vendar že pri prvem znaku vrne bodisi True (če je enak A) bodisi False (če ni). V resnici torej preverja le prvi znak, ostalih niti ne povoha.

Pravilna rešitev je, kot skoraj vedno, preprostejša.

def vsebuje_a(beseda): for crka in beseda: if crka == "A": return True return False

To je torej vzorec: iščem kaj, kar mi je všeč (A). Če najdem, srečen vrnem True. Če ne, iščem naprej. False (ali kaj drugega, s čimer mora funkcija sporočiti slabo novico) vrnem šele na koncu.

Ne spreglejte, da smo v prvi vrstici funkcije spremenili niz b2 v seznam črk crke2. To je smiselno zato, ker je brisanje elementov seznama preprostejše kot brisanje črk niza.

Seveda pa lahko poskusimo tudi z nizi; to bo priložnost, da pokažemo nekaj zvitosti.

def anagram(b1, b2): if len(b1) != len(b2): return False for crka in b1: b2 = b2.replace(crka, "", 1) return not b2

Če sta niza različnih dolžin, nista anagrama. Sicer gremo prek črk prve besede in zamenjamo dotično črko v drugi besedi s praznim nizom; z drugimi besedami, pobrišemo jo. Tretji argument v replace, 1, pomeni, da želimo pobrisati največ eno ponovitev. Če te črke v drugem nizu ni (več), je pač ne bomo pobrisali. Ker v drugem nizu pobrišemo (največ) toliko črk, kolikor jih ima prvi in ker sta v začetku oba niza enako dolga, je lahko drugi niz na koncu prazen le, če smo vsakič pobrisali po eno črko. To pa se zgodi natanko takrat, ko so v drugem nizu iste črke kot v prvem.

S prvo rešitvijo, seznami, ni nič narobe, vendar zasluži 0 točk za eleganco. Druga rešitev je vsaj duhovita, vendar tudi dokaj neučinkovita in grda, ker v njej brišemo črke iz niza. To se ne dela (brez dobrega vzroka).

Rešitev, ki bi jo napisal vsak programer v Pythonu, ki ima kaj samospoštovanja, pa je takšna: črke besede uredimo po abecedi. Funkcija sorted(x) sprejme seznam, niz ali karkoli drugega, prek česar moremo z zanko for in vrne urejen seznam elementov x-a. Če vsebuje x, recimo, številke, bomo dobili številke, urejene po velikosti. Če vsebuje črke, dobimo črke, urejene po abecedi.

>>> sorted("pirat") ['a', 'i', 'p', 'r', 't']

Če dobimo pri obeh besedah isto, gre za anagram.

def anagram(b1, b2): return sorted(b1) == sorted(b2)

V drugem letniku vas čaka predmet, pri katerem se boste pogovarjali o podatkovnih strukturah. Že tu povejmo nekaj malega, le toliko, da boste zaslutili, da so tu zadaj še veliko globje reči. Vzemimo, da so besede "kar dolge". Če jih še podaljšujemo, se s tem podaljšuje tudi čas, ki ga porabi funkcija, vendar pri zadnji rešitvi čas, ki ga potrebuje funkcija, narašča veliko počasneje kot pri prvih dveh, z brisanjem. Prvi dve za dvakrat daljšo besedo potrebujeta kar štirikrat več časa. Po domače: če so besede zelo dolge, je zadnja rešitev precej hitrejša. Če so kratke, je čas zanemarljiv pri vseh različicah; v tem primeru nam je spet najbolj všeč zadnja rešitev, ker je funkcija najkrajša, celo tako kratka, da se v njej nimamo kje zmotiti. (Da, prednost kratkih programov je tudi v tem, da imajo manj napak!)

Avtobusni prevozi

Na šoli je potrebno stalno organizirati prevoze za šolske dejavnosti. Ravnatelj vam je zato naložil nalogo, da napišete program, ki mu bo poenostavil delo. Program mora delovati tako, da ravnatelj vpiše število učencev, nato pa mu ta vrne koliko avtobusov, kombijev oz. avtomobilov je potrebno naročiti. Šola ima pogodbo s podjetjem, ki ima v svojem voznem parku naslednja vozila: avtobuse s 50 sedeži, mini avtobuse z 25 sedeži, kombije z 10 sedeži in avtomobile s 5 sedeži. Program naj deluje tako, da vedno do konca napolni največje vozilo, nato šele izbere naslednjega po velikosti. Tako bo npr. za 50 učencev predlagal en avtobus in ne 10 avtomobilov.

Tule je naivna (a delujoča) rešitev, ki ustreza temu, kako je ravnatelj doslej delal ročno.

otrok = int(input("Število otrok: ")) s = "" if otrok >= 50: s = "{} avtobus(ov)".format(otrok // 50) otrok = otrok % 50 if otrok >= 25: if s: s += ", " s += "1 mini avtobus" otrok = otrok % 25 if otrok >= 10: if s: s += ", " s += "{} kombi(ja)".format(otrok // 10) otrok = otrok % 10 if otrok > 0: if s: s += ", " s += "{} avtomobila(-ov)".format((otrok + 3) // 4) s += "." print(s)

Število avtobusov in mini avtobusov določimo tako, da celoštevilsko delimo število otrok s kapaciteto prevoznega sredstva. Celoštevilsko deljenje zaokroža navzdol: pri 110 otrocih bomo dobili dva avtobusa. Pri mini avtobusu smo ravnali nekoliko drugače, saj nikoli ne bomo naročil več kot enega: če je otrok za dva mini avtobusa, jih je dovolj tudi za avtobus. Pri avtomobilih pa je potrebno zaokrožati navzgor. To lahko naredimo tako, da uporabimo funkcijo math.ceil ali, kot smo storili tu, prištejemo 3, preden delim s 4. Če bi kdo namesto tega napisal otrok // 4 + 1, se mu ne bi obneslo, saj bi za osem otrok naročil tri avtomobile. Če k številu otrok prištejemo 3, pa se ravno izide. Če imamo 8 otrok, bomo naročili (8 + 3) // 4, torej dva avtomobila, če jih je 9, pa naročimo (9 + 3) // 4 = 3 avtomobile.

Za avtomobile smo predpostvili, da lahko vanje stlačimo štiri otroke. Naloga ne pove, kako stari so, predpostavljamo pa (vsaj), da ne bodo vozili avtomobilov.

Na koncu vsakega prevoznega sredstva izračunamo, koliko otrok je še ostalo. Pri avtobusu, recimo, imamo otrok = otrok % 50, izračunamo torej ostanek po deljenju otrok (s 50) na avtobuse.

Vse, kar je potrebno naročiti, potrpežljivo zlagamo v niz s in ga na koncu izpišemo.

Dolgoletne statistike kažejo, da je med programerji večinski vzrok depresij, živčnih zlomov in nasilja nad (poslovnimi in zakonskimi) partnerji postavljanje vejic pri naštevanju v nizih. Ker je samomorov med Slovenci že tako ali tako preveč (sploh pa nam manjka programerjev, torej bi jih bilo res škoda, če bi se obešali), odpravimo vsaj ta vzrok. Gornji program bi bil namreč pol krajši, če nam ne bi bilo potrebno skrbeti za te frdamane vejice! (Če se vam vejice ne zdijo problem, bo to samo zato, ker še niste toliko programirali kot jaz. ;)

Trik številka 1 je, da za vsako rečjo dodamo vejico.

otrok = int(input("Število otrok: ")) s = "" if otrok >= 50: s = "{} avtobus(ov), ".format(otrok // 50) otrok = otrok % 50 if otrok >= 25: s += "1 mini avtobus, " otrok = otrok % 25 if otrok >= 10: s += "{} kombi(ja), ".format(otrok // 10) otrok = otrok % 10 if otrok > 0: s += "{} avtomobila(-ov), ".format((otrok + 3) // 4) s = s[:-2] + "." print(s)

Ko sestavimo niz s, vemo, da ima na koncu zagotovo vejico in presledek. Da bi bilo vedno tako, smo jo dodali celo pri avtomobilih, čeprav vemo, da je tam zagotovo ne bomo potrebovali. Ker vemo, da sta na koncu niza vedno natančno dva znaka, ki ju ne potrebujemo, ju pred izpisom - pravzaprav, preden dodamo piko - preprosto odbijemo s = s[:-2] + ".".

Trik številka 2, ki vžge v jezikih, ki imajo nekoliko boljšo podporo za besedila, je, da sestavimo seznam nizov, ki jih nato zlepimo skupaj z vejicami. Python to stori z metodo join (če je niste spoznali v prvem semestru, si jo le oglejte, zelo je koristna!).

otrok = int(input("Število otrok: ")) vozila = [] if otrok >= 50: vozila.append("{} avtobus(ov)".format(otrok // 50)) otrok %= 50 if otrok >= 25: vozila.append("{} mini avtobus".format(otrok // 25)) otrok %= 25 if otrok >= 10: vozila.append("{} kombi(ja)".format(otrok // 10)) otrok %= 10 if otrok > 0: vozila.append("{} avtomobila(-ov)".format((otrok + 3) // 4)) print(", ".join(vozila))

Če imamo, recimo 76 otrok, bomo v seznam vozila zložili ["1 avtobus(ov)", "1 mini avtobus", "1 avtomobila(-ov)"]. Ob izpisovanju to mimogrede zlepimo z vejicami.

Mimogrede smo postorili še dvoje. otrok = otrok % 50 (in podobne stavke) smo zamenjali otrok %= 50. Predvsem pa smo malo pokvarili program pri mini avtobusu. Zdaj je napisan, kot da se ne bi zavedali, da vedno potrebujemo največ enega. To je bilo potrebno zato, da se program bolj očitno ponavlja: prvi trije if-i (z vsem znotraj njih) so si popolnoma enaki, le številke in nizi se spreminjajo. Napišimo torej krajše.

otrok = int(input("Število otrok: ")) na_voljo = [(50, "avtobus(ov)"), (25, "mini avtobus"), (10, "kombi(ja)")] vozila = [] for kapaciteta, opis in na_voljo: if otrok >= kapaciteta: vozila.append("{} {}".format(otrok // kapaciteta, opis)) otrok %= kapaciteta if otrok > 0: vozila.append("{} avtomobila(-ov)".format((otrok + 3) // 4)) print(", ".join(vozila))

Namesto prvih treh if-ov imamo zdaj zanko, ki se ponovi trikrat. Številke smo zamenjali s kapaciteta, opise prometnih sredstev pa z opis.

Kronane glave

Še zadnja izpitna naloga nam je ostala.

Ker se imena kraljev v posameznih kraljevinah pogosto ponavljajo, se njihovim imenom doda še številka, da se natančno ve, za katerega kralja gre. V angleški zgodovini je bilo kar nekaj kraljev z imenom Henry (Henry I, Henry II, . . . , Henry VIII). Uporabnik vpiše podatke o vladarjih. V prvi vrstici je število vladarjev, tej pa sledijo vsa njihova imena. Izpiši jih v istem vrstnem redu. Imenom, ki se ponovijo večkrat, pa dodaj še zaporedno številko. Predpostaviš lahko naslednje:

  • vsa imena bodo zapisana z malimi črkami, le začetnica bo velika;
  • vsa imena bodo enobesedna;
  • imen ne bo več kot 20.

Primer vhoda:    Izpis:
10
Edward           Edward 1
Mary             Mary
Henry            Henry 1
Richard          Richard
Henry            Henry 2
Henry            Henry 3
Charles          Charles 1
William          William
Charles          Charles 2
Edward           Edward 2

Ničesar od naštetega ne bomo predpostavili, ker nam ni treba. Uporabnik bo vpisoval z malimi in veliki črkami, kakor mu drago, kralji bodo imeli lahko poljubno število imen in jih bo lahko tudi dvesto, če bodo tako blagovolili.

Program ima dva dela. Prvi je duhamoren: vpisovanje. V njem ni ničesar posebno lepega in poučnega, vendar bomo morali poskrbeti zanj. Sledi drugi, zanimivejši del naloge: izpisovanje.

Najprej torej poskrbimo za vpis: napišimo program, ki poskrbi, da uporabnik vpiše imena kronanih glav. Rezultat bo v spremenljivki imena.

imen = int(input("Koliko kronanih glav imamo? ")) imena = [] for i in range(imen): imena.append(input().title())

Vse je preprosto in očitno, le title() omenimo: podobno kot upper() vrne niz, zapisan s samimi velikimi črkami, bo title() vrnil niz, v katerem so vse besede napisane z veliko začetnico. Tako bo "maRIja terezija".title() vrnil "Marija Terezija.

Mimogrede, tole vpisovanje je nerodno, ker mora človek, preden začne vpisovati, prešteti, koliko reči bo vpisal. Naloga je takšna, kot je, iz zgodovinskih razlogov (česar nalogi, ki se ukvarja z angleškimi kralji, niti ne smemo očitati). Dandanes, ko imamo Python, bi raje naredili takole: uporabnik vpisuje imena, dokler se ne naveliča. Ko ima dovolj, pritisne le Enter, s čimer vnese prazen niz in nam pove, da je končal.

imena = [] while True: ime = input().title() if not ime: break imena.append(ime)

Tule opazimo neskončno zanko (while True), ki pa jo v primernem trenutku prekinemo z break.

Poskrbivši, da so imena vnešena, se lotimo zanimivejšega dela naloge. Lotimo se ga "po človeško": razmislimo, kako bi to nalogo reševali ročno. Šli bi prek seznama imen. Pri vsakem bi preverili, ali se v celotnem seznamu pojavi le enkrat. Če je tako, bi ga izpisali. Če se večkrat bi, preverili, kolikokrat se je pojavilo v doslej izpisanih imenih. Številko, ki jo je potrebno dodati za imenom, bi dobili tako, da bi k številu dosedanjih pojavitev prišteli 1.

Da bi ta postopek udobneje sprogramirali, se moramo spomniti še dveh prikladnih lastnosti seznamob. Seznami imajo metodo count. Z, recimo, imena.count("Matjaž") izvemo, koliko kraljev Matjažev je v seznamu imena. Drugo, če imamo nek seznam s, z s[:4] dobimo seznam, ki vsebuje le prve štiri elemente s-a.

Tako oboroženi lahko hitro opravimo z nalogo.

for i in range(len(imena)): ime = imena[i] if imena.count(ime) == 1: print(ime) else: print(ime, imena[:i].count(ime) + 1)

Z i bomo šteli od 0 do toliko, kolikor imamo imen (for i in range(len(imena))). Vzamemo i-to ime. Preverimo, ali se v celotnem seznamu pojavi le enkrat. Če je tako, ga izpišemo. Če se večkrat, preverimo, kolikokrat se je pojavilo v doslej izpisanih imenih (imena[:i].count(ime), število pojavitev med vsemi imeni do i-tega). Številko, ki jo je potrebno dodati za imenom, bi dobimo tako, da k številu dosedanjih pojavitev prištejemo 1.

Kot razodeva podobnost zadnjih dveh odstavkov, je program dobeseden prevod iz slovenščine v Python.

V zvezi z zanko for je potrebno opozoriti (in zato študente stalno opozarjam) še na nekaj. Nekateri (predvsem tisti, ki že znajo programirati v kakem drugem jeziku in se še niso povsem navadili Pythona - takšni tule niso ravno v večini, če je sploh kje kdo), zelo radi pišejo

for i in range(len(imena)): ime = imena[i]

Imamo torej indeks i in z njim dostopamo do i-tega elementa. To ni prav lepo, veliko lepše, preglednejše, Pythonovsko je, če iz seznama pobiramo elemente neposredno, ne prek indeksov:

for ime in imena:

Vendar prav tule tole, slednje, ne bi bilo posrečeno, ker v resnici potrebujemo tudi indeks elementa, ne le njegove vrednosti. Proti koncu programa namreč rečemo "vsi elementi pred i-tim".

V takšne namene v Pythonu uporabljamo enumerate, ki seznam (poljubnih) reči "spremeni" v seznam parov (indeks, reč). Lepa rešitev naloge je torej:

for i, ime in enumerate(imena): if imena.count(ime) == 1: print(ime) else: print(ime, imena[:i].count(ime) + 1)
Последнее изменение: четверг, 5 октября 2017, 11:44