Naloga

Naloga se ocenjuje, zato je ne smete izpustiti. Ker je potrebno narediti nekoliko več, bo tudi lažje preverjati izvirnost. Prosim, rešujte pravočasno in sami!

Imamo slovar s koordinatami krajev - prvi dve sta koordinati x in y (v nekem koordinatnem sistemu - kakšnem, ni pomembno), tretja je nadmorska višina (v dekametrih). Slovar je takšen:

koordinate = { "Kranjska Gora": (76, 76, 65.5), "Jesenice": (108, 84, 58.0), "Radovljica": (122, 115, 49.0),

... in tako naprej. Sorazmerja med višinami in koordinatami ne ustrezajo realnim. To naj vas ne vznemirja.

Med kraji so postavljeni nekakšni žlebovi. Kako, pove naslednji slovar:

povezave = { "Kranjska Gora": {"Jesenice"}, "Radovljica": {"Jesenice", "Tržič", "Kranj"}, "Kranj": {"Tržič", "Kamnik", "Škofja Loka"},

Iz Radovljice, recimo, so napeljani žlebovi v Jesenice, Tržič in Kranj...

Da je napeljan žleb iz Kranja v Radovljico, je jasno, zato tega v Kranju ne pišemo ponovno. To pri reševanju ignorirajte. Funkcija za oceno 7 bo zaradi tega delovala nekoliko narobe. V funkciji za oceno 8 boste naredili dopolnjevanje tega slovarja (glej spodaj) in testi funkcij za oceno 9 in 10 bodo uporabljali dopolnjeni slovar.

Za ogrevanje

Napišite funkcijo evklid(s, t), ki dobi koordinate dveh točk v poljubno dimenzionalnem prostoru, in vrne evklidsko razdaljo med njima.

Rešitev

Najlažje je, če se spomnimo na zip. Gremo vzporedno prek obeh seznamov, odštevamo in kvadriramo, kot nas je učil Evklid (pih, Pitagora!) in na koncu korenimo vsoto.

def evklid(s, t): d = 0 for si, ti in zip(s, t): d += (si - ti) ** 2 return sqrt(d)

Če ne vemo za zip, se moramo hecati z indeksi. Ni hudega, a zip je lepši.

def evklid(s, t): d = 0 for i in range(len(s)): d += (s[i] - t[i]) ** 2 return sqrt(d)

Za oceno 6

Napišite funkcijo razdalja(kraj1, kraj2), ki prejme imeni dveh krajev in vrne dolžino žleba med njima. Upoštevati mora tudi višinsko razliko.

Napišite funkcijo naklon(kraj1, kraj2), ki vrne naklon žleba med dvema krajema. Naklon je negativen, če je kraj2 nižje kot kraj1. Uporabite funkcijo atan iz modula math.

Napišite funkcijo dolzina_poti(pot), ki vrne dolžino poti, ki bi jo prepotovali, če bi šli po podani poti. Funkciji ni potrebno preverjati, ali med podanimi kraji dejansko obstajajo žlebovi. (Pravzaprav tega niti ne sme, saj testi preskušajo poti, ki ne obstajajo.)

Rešitev

S koordinate[kraj1] in koordinate[kraj2] dobimo koordinate in jih podamo Evklidu.

def razdalja(kraj1, kraj2): return evklid(koordinate[kraj1], koordinate[kraj2])

Za naklon je potrebno malo razmisliti: navpično komponento pove razlika med koordinatami z, vodoravna pa je premik v smereh x in y. Zato slednji dve damo Evklidu, nato pa vse skupaj Arkusu.

def naklon(kraj1, kraj2): x1, y1, z1 = koordinate[kraj1] x2, y2, z2 = koordinate[kraj2] xy = evklid([x1, y1], [x2, y2]) return atan((z2 - z1) / xy)

O dolžini poti pa ni izgubljati besed: gremo prek zaporednih parov krajev in seštevamo. Kako prek zaporednih parov pa je nekaj, kar smo letos ponovili že velikokrat.

def dolzina_poti(kraji): s = 0 for kraj1, kraj2 in zip(kraji, kraji[1:]): s += razdalja(kraj1, kraj2) return s

Za oceno 7

Predstavljajte si, da v nekem kraju na sistem žlebov postavimo kroglico. Odkotalila se bo po žlebu z največjim padcem; če gredo vsi žlebovi iz podanega kraja navzgor, ne bo šla nikamor.

Napišite funkcijo izbira(kraj1), ki izpiše kraj, v katerega bi se odkotalila kroglica iz kraja kraj1.

Rešitev

Iščemo kraj2, za katerega klic naklon(kraj1, kraj2 vrne največjo vrednost. Tudi takšne reči smo počeli že dostikrat.

def izbira(kraj1): naj_naklon = 0 naj_kraj = None for kraj2 in povezave[kraj1]: nak = naklon(kraj1, kraj2) if nak < naj_naklon: naj_naklon, naj_kraj = nak, kraj2 return naj_kraj

Za oceno 8

Napišite funkcijo dopolni(povezave), ki prejme slovar povezav, kakršen je gornji, in vrne slovar, v katerem so vpisane povezave v obe smeri.

V vrnjenem slovarju mora biti, recimo, ključ Jesenice z vrednostjo

{"Radovljica", "Kranjska Gora"}, poleg tega mora pri, recimo, Kopru, dodati k Piranu (ki obstaja že v originalnem slovarju) še Postojno.

Rešitev

Tule uporabimo defaultdict; seveda bi šlo brez, a z njim je preprosteje.

import collections def dopolni(povezave): nove = collections.defaultdict(set) for kraj1, kraji in povezave.items(): for kraj2 in kraji: nove[kraj1].add(kraj2) nove[kraj2].add(kraj1) return nove

Gremo prek vseh krajev (kraj1) in za vsakega prek vseh krajev, s katerimi je povezan (kraj2). V nove povezave dodamo povezavo iz kraj1 v kraj2 in iz kraj2 v kraj1.

Za oceno 9

Napišite funkcijo pot(kraj), ki vrne seznam krajev, čez katere se kotali žogica, če jo postavimo v kraj. Žogica se iz vsakega kraja kotali naprej v kraj, v katerega vodi žleb z največjim naklonom. Ustavi se, ko pride v kraj, iz katerega vodijo žlebovi le še navzgor.

Napišite funkcijo kam(kraj), ki vrne kraj, v katerem se ustavi žogica, če jo postavimo v podani kraj.

Rešitev

Najprej napišimo pot, saj bo kraj potem trivialna.

def pot(kraj): s = [] while kraj: s.append(kraj) kraj = izbira(kraj) return s

Sestavimo prazno pot, s. Nato ponavljamo kraj = izbira(kraj) - iz vsakega kraja gremo v kraj, ki ga vrne funkcija izbira. To počnemo, dokler izbira ne vrne None (while kraj). Kraje, prek kateri potujemo, sproti dajemo v s (s.append(kraj)).

Kadar počnemo takšne stvari, moramo popaziti, da v seznam damo tako prvi kot zadnji kraj - često se bo namreč zgodilo, da bomo ponesreči izpustili enega od njiju. Tule, kakopak, vse deluje, kot mora. Prvi kraj damo v seznam s prvim s.append(kraj); ta stavek se namreč izvede še preden, gremo v drugi kraj (v naslednji vrstici). Kadar tidve vrstici obrnemo tako, se bo rado zgodilo, da pozabimo zadnji kraj. No, tu se ne. Zadnji kraj je tisti, za katerega izbira vrne None. V s smo ga očitno dali pred klicem izbira.

Funkcija kraj pokliče pot in vrne zadnji kraj na seznamu.

def kam(kraj): return pot(kraj)[-1]

Za oceno 10

Napišite funkcijo od_kod(), ki vrne slovar, katerega ključi so imena krajev, v katerih se lahko žogice ustavijo, vrednosti pa množice imen krajev, ki peljejo v te kraje.

Kot lahko vidite iz testov, mora funkcija vrniti takšen slovar:

{'Krško': {'Radovljica', 'Litija', 'Tržič', 'Celje', 'Velenje', 'Zidani most', 'Kranj', 'Krško', 'Kamnik', 'Jesenice', 'Ljubljana', 'Ribnica', 'Kranjska Gora', 'Škofja Loka'}, 'Sežana': {'Sežana'}, 'Koper': {'Koper', 'Piran'}, 'Vrhnika': {'Postojna', 'Vrhnika'}, 'Murska Sobota': {'Murska Sobota', 'Ljutomer'}, 'Črnomelj': {'Novo mesto', 'Kočevje', 'Črnomelj'}, 'Lendava': {'Lendava'}, 'Pivka': {'Pivka'}, 'Ptuj': {'Maribor', 'Ptuj'}}

Žogica se ustavi v, recimo, Črnomlju, če jo postavimo v Novo mesto, Kočevje ali Črnomelj. Zelo pogosto se ustavi v Krškem - namreč, če jo spustimo v Radovljico, Litijo, Tržič, Celje, Velenje, Zidani most... (Sava je vedela, kam teče...). V Sežani se ustavi le, če jo damo v Sežano...

Rešitev

Tole je v resnici preprosto, čim razmislimo, kako mora biti obrnjen slovar. Gremo prek vseh krajev (for kraj in povezave) in pogledamo, kam se iz njega odvali žogica (kam(kraj)). V slovar (v resnici vzamemo defaultdict, katerega vrednosti so množice) zapišemo, da v kraj kam(kraj) pride (tudi) žogica iz kraja kraj, od[kam(kraj)].add(kraj).

def od_kod(): od = collections.defaultdict(set) for kraj in povezave: od[kam(kraj)].add(kraj) return od
Zadnja sprememba: torek, 5 maj 2015, 00:03