Tokratna naloga je ena od treh nalog za oceno. Končna ocena predmeta bo poprečje poprečja teh treh nalog in izpita.

Za oceno 6

Napišite funkcijo beri_mesta(ime_datoteke), ki kot argument sprejme ime datoteke s koordinatami nekaterih večjih slovenskih krajev, in vrne slovar, katerega ključi so imena mest, vrednosti pa pari z zemljepisno dolžino in širino, zapisani v stopinjah (minute ustrezno pretvorite).

Trije primeri datotek so priloženi testom. Predpostaviti smete, da so vsa mesta na severni polobli, vzhodni hemisferi.

Za oceno 7

Napišite funkcijo razdalja(koordinate, mesto1, mesto2), ki kot argument sprejme koordinate mest (v takšni obliki, kot jih vrača funkcija beri_mesta) in imeni dveh mest. Kot rezultat naj vrne razdaljo med mestoma.

Za računanje razdalj uporabite funkcijo, ki jo najdete na naslovu: http://www.platoscave.net/blog/2009/oct/5/calculate-distance-latitude-longitude-python/. To funkcijo lahko skopirate v svoj program in jo kličete, ali pa jo skopirate v svoj program in jo ustrezno spremenite. V vsakem primeru pa uporabljajte natančno to formulo, saj bodo tudi testni primeri predpostavljali takšne razdalje.

Za oceno 8

Napišite funkcijo dolzina_poti(koordinate, pot), ki kot argumenta prejme koordinate mest in seznam mest, prek katerih potujemo (s helikopterjem). Pot je lahko, na primer, ["Ljubljana", "Celje", "Kranj", "Lasko", "Jesenice"]. Funkcija naj vrne skupno razdaljo, ki jo preletamo ob takem potovanju.

Za oceno 9

Napišite funkciji najblizje(koordinate, mesto), ki za podano mesto vrne ime najbližjega drugega mesta, in funkcijo najblizja(koordinate, mesto, n), ki vrne seznam n najbližjih mest podanemu mestu. Seznam naj bo urejen po razdaljah (od bližnjih proti bolj oddaljenim).

Če zahtevamo več mest, kolikor jih je v podatkih (npr. da bi hoteli milijon slovenskih mest), naj jih funkcija vrne toliko, kolikor jih pač je, vendar v pravem vrstnem redu.

Za oceno 10

Napišite funkcijo najkrajsa_pot(koordinate, mesta), ki kot argumenta dobi koordinate mest in seznam mest. Vrniti mora nov seznam, v katerem sta prvo in zadnje mesto enaki, vmesna pa so preurejena tako, da je pot med njimi čim krajša. Če bi bila mesta, recimo ["Ljubljana", "Celje", "Kranj", "Lasko", "Jesenice"], naj funkcija vrne ["Ljubljana", "Lasko", "Celje", "Kranj", "Jesenice"]. Prvo in zadnje mesto sta določeni in se ne smeta spreminjati, vmes pa je pametneje leteti iz Laškega v Celje in potem Kranj, kot iz Celja v Kranj in potem v Laško.

Predpostaviti smeš, da seznam vsebuje vsaj dve mesti in da se mesta ne ponavljajo.

Pri reševanju si pomagaj s funkcijo permutations v modulu itertools. Z njo sestavljaj permutacije mest od drugega do predzadnjega, prvo in zadnje pa vsakič znova pripni zraven in računaj dolžino poti.

Testi bodo funkcijo preverili na primerno majhni množicah mest. Kot zanimivost pa lahko preveriš, kako počasna postane tvoja funkcija, ko želimo obiskati več mest. Potem si lahko prebereš še kaj o slavnem Problemu trgovskega potnika.

Rešitev

Branje mest ste nekateri zelo zapletli, ker imate preveč radi split. Veliko preprosteje gre z običajnim indeksiranjem.

def beri_mesta(ime_dat): mesta = {} for v in open(ime_dat): mesto, x, y = v.split("\t") x = int(x[:3]) + int(x[4:6]) / 60 + int(x[7:9]) / 3600 y = int(y[:3]) + int(y[4:6]) / 60 + int(y[7:9]) / 3600 mesta[mesto] = (x, y) return mesta

Metodo split uporabimo le za ločevanje glede na tabulator, \t. Po tem dobimo koordinate v obliki 123E45'67": prvi trije znaki predstavljajo stopinje, 4. in 5. predstavljata minute, 7. in 8. sekunde. Dobimo jih z indeksiranjem, spremenimo v števila in ustrezno delimo. Vse skupaj lepo sproti dodajamo v slovar, ki ga na koncu vrnemo.

Funkcijo za računanje razdalj sem naročil ukrasti s spleta. Mimogrede, kadar počnemo takšne stvari, moramo preveriti, ali imamo do tega pravico, poleg tega pa se spodobi napisati vir - da ne bi kdo mislil, da smo to napisali sami.

# Po: <a href="http://www.platoscave.net/blog/2009/oct/5/calculate-distance-latitude-longitude-python/" class="_blanktarget">http://www.platoscave.net/blog/2009/oct/5/calculate-distance-latitude-longitude-python/</a> import math def razdalja(koordinate, mesto1, mesto2): lat1, lon1 = koordinate[mesto1] lat2, lon2 = koordinate[mesto2] radius = 6371 # km dlat = math.radians(lat2-lat1) dlon = math.radians(lon2-lon1) a = math.sin(dlat/2) * math.sin(dlat/2) + math.cos(math.radians(lat1)) \ * math.cos(math.radians(lat2)) * math.sin(dlon/2) * math.sin(dlon/2) c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a)) d = radius * c return d

Funkcijo, ki jo dobimo na spletu, je bilo potrebno le malo spremeniti: namesto koordinat mest dobi slovar s koordinatami in imeni mest. V prvih dveh vrsticah iz slovarja izvlečemo prave koordinate, naprej pa gre z ukradeno kodo.

Za iskanje najbližjih mest sem za začetek rekel, da je najbližje mesto "", ki je zelo zelo daleč. (To ni najbolj varen način, a tule naj nam bo.) Potem gremo prek vseh drugih mest; če gre slučajno za isto mesto (mesto == mesto2), ga preskočimo. Sicer izračunamo razdaljo in če je krajša od najkrajše, si zapomnimo mesto in razdaljo do njega. (Takšno nalogo smo reševali že ničkolikokrat).

def najblizje(koordinate, mesto): naj_mesto, naj_razdalja = "", 10000000 for mesto2 in koordinate: if mesto == mesto2: continue d = razdalja(koordinate, mesto, mesto2) if d < naj_razdalja: naj_mesto, naj_razdalja = mesto2, d return naj_mesto

Za dolžino poti jemljemo pare mest in seštevamo razdalje med njimi. Zanko spustimo do enega mesta manj, kot je velikost seznama (len(pot) - 1), da lahko potem mirno računamo razdalji med mestoma z indeksoma i in i + 1. Tudi naloge v tem slogu smo že videvali.

def dolzina_poti(koordinate, pot): dolzina = 0 for i in range(len(pot) - 1): dolzina += razdalja(koordinate, pot[i], pot[i + 1]) return dolzina

Seznam najbližjih mest najpreprosteje (čeprav to ni nujno tudi najučinkoviteje) dobimo tako, da sestavimo seznam parov (razdalja, mesto). To naredi prva zanka v spodnji funkciji. Nato ta seznam uredimo. Potem gremo prek mest od 1. do n + 1. Ničtega izpustimo, saj je ničto ravno mesto mesto. Zanko smo napisali tako, da par (razdalja, mesto) odpakiramo v spremenljivki z imenoma _ in mesto. Ime _ tradicionalno uporabljamo za spremenljivke, ki nas v resnici ne zanimajo; tudi tule nas zanimajo le mesta, ki jih pridno zložimo v nov seznam in ga vrnemo.

def najblizja(koordinate, mesto, n): razdalje = [] for mesto2 in koordinate: razdalje.append((razdalja(koordinate, mesto, mesto2), mesto2)) razdalje.sort() naj = [] for _, mesto in razdalje[1:n+1]: naj.append(mesto) return naj

Do najkrajše poti pa pridemo takole: najprej izračunamo dolžino "predlagane" poti in jo shranimo kot najboljšo pot. Nato gremo z zanko prek vseh permutacij mest - pri čemer izpustimo prvo in zadnje mesto, itertools.permutations(mesta[1:-1]). Sestavimo pot, tako da ponovno pripnemo prvo in zadnje mesto pot = [mesta[0]] + list(red) + [mesta[-1]]. Izračunamo dolžino te poti in če je boljša od najboljše doslej, si jo zapomnimo. Na koncu vrnemo najboljše, kar smo našli.

import itertools def najkrajsa(koordinate, mesta): naj_pot, naj_razdalja = mesta, dolzina_poti(koordinate, mesta) for red in itertools.permutations(mesta[1:-1]): pot = [mesta[0]] + list(red) + [mesta[-1]] razdalja = dolzina_poti(koordinate, pot) if razdalja < naj_razdalja: naj_pot, naj_razdalja = pot, razdalja return naj_pot
Last modified: Saturday, April 12, 2014, 10:44 AM