Zemlja je, kot vemo, ploščata, Slovenija pa sploh (izvzemši hribe in doline, gore in kotline, vrtače in uvale ter druge lokalne ekstreme). Tule je seznam nekaterih slovenskih krajev in koordinat v nekem koordinatnem sistemu.

kraji = [
    ('Brežice', 68.66, 7.04), ('Lenart', 85.20, 78.75), ('Rateče', -65.04, 70.04),
    ('Ljutomer', 111.26, 71.82), ('Rogaška Slatina', 71.00, 42.00), ('Ribnica', 7.10, -10.50),
    ('Dutovlje', -56.80, -6.93), ('Lokve', -57.94, 19.32), ('Vinica', 43.81, -38.43),
    ('Brtonigla', -71.00, -47.25), ('Kanal', -71.00, 26.25), ('Črnomelj', 39.05, -27.93),
    ('Trbovlje', 29.61, 35.07), ('Beltinci', 114.81, 80.54), ('Domžale', -2.34, 31.50),
    ('Hodoš', 120.70, 105.00), ('Škofja Loka', -23.64, 35.07), ('Velike Lašče', 0.00, 0.00),
    ('Velenje', 33.16, 54.29), ('Šoštanj', 29.61, 57.75), ('Laško', 42.60, 33.29),
    ('Postojna', -29.54, -5.25), ('Ilirska Bistrica', -27.19, -27.93),
    ('Radenci', 100.61, 84.00), ('Črna', 15.41, 66.57), ('Radeče', 39.05, 24.57),
    ('Vitanje', 47.36, 57.75), ('Bled', -37.84, 56.07), ('Tolmin', -63.90, 36.75),
    ('Miren', -72.14, 7.04), ('Ptuj', 87.61, 61.32), ('Gornja Radgona', 97.06, 89.25),
    ('Plave', -73.34, 21.00), ('Novo mesto', 37.91, -3.47), ('Bovec', -76.89, 52.50),
    ('Nova Gorica', -69.79, 12.29), ('Krško', 60.35, 14.07), ('Cerknica', -18.89, -3.47),
    ('Slovenska Bistrica', 66.31, 57.75), ('Anhovo', -72.14, 22.78), ('Ormož', 107.71, 61.32),
    ('Škofije', -59.14, -27.93), ('Čepovan', -60.35, 22.78), ('Murska Sobota', 108.91, 87.57),
    ('Ljubljana', -8.24, 22.78), ('Idrija', -43.74, 17.54), ('Radlje ob Dravi', 41.46, 82.32),
    ('Žalec', 37.91, 43.79), ('Mojstrana', -49.70, 64.79),
    ('Log pod Mangartom', -73.34, 59.54), ('Podkoren', -62.69, 70.04),
    ('Kočevje', 16.61, -21.00), ('Soča', -69.79, 52.50), ('Ajdovščina', -53.25, 5.25),
    ('Bohinjska Bistrica', -48.49, 47.25), ('Tržič', -22.44, 56.07), ('Piran', -75.69, -31.50),
    ('Kranj', -20.09, 43.79), ('Kranjska Gora', -60.35, 68.25), ('Izola', -68.59, -31.50),
    ('Radovljica', -31.95, 54.29), ('Gornji Grad', 13.06, 49.03), ('Šentjur', 54.46, 40.32),
    ('Koper', -63.90, -29.72), ('Celje', 45.01, 42.00), ('Mislinja', 42.60, 66.57),
    ('Metlika', 48.56, -19.21), ('Žaga', -81.65, 49.03), ('Komen', -63.90, -1.68),
    ('Žužemberk', 21.30, 0.00), ('Pesnica', 74.55, 80.54), ('Vrhnika', -23.64, 14.07),
    ('Dravograd', 28.40, 78.75), ('Kamnik', -1.14, 40.32), ('Jesenice', -40.19, 64.79),
    ('Kobarid', -74.55, 43.79), ('Portorož', -73.34, -33.18), ('Muta', 37.91, 82.32),
    ('Sežana', -54.39, -13.96), ('Vipava', -47.29, 1.79), ('Maribor', 72.21, 75.28),
    ('Slovenj Gradec', 31.95, 71.82), ('Litija', 14.20, 22.78), ('Na Logu', -62.69, 57.75),
    ('Stara Fužina', -52.04, 47.25), ('Motovun', -56.80, -52.50), ('Pragersko', 73.41, 57.75),
    ('Most na Soči', -63.90, 33.29), ('Brestanica', 60.35, 15.75),
    ('Savudrija', -80.44, -34.96), ('Sodražica', 0.00, -6.93),
]

Ogrevalne naloge

1. Izpiši imena vseh krajev.

Za tole je potrebno z zanko prek vseh trojk ime, x, y in izpisovati ime. To smo pravzaprav delali že na predavanjih.

for ime, x, y in kraji:
    print(ime)

2. Uporabnik vnese koordinato x in koordinato y. Program izpiše imena vseh krajev in njihove razdalje od teh koordinat.

To je podobno kot prej, le da poleg imena izpišemo še razdaljo.

x0 = float(input("Vnesi x: "))
y0 = float(input("Vnesi y: "))

najmanjsa_razdalja = None
for ime, x, y in kraji:
    razdalja = sqrt((x0 - x) ** 2 + (y0 - y) ** 2)
    print(ime, razdalja)

3. Uporabnik vnese koordinati, tako kot prej, program pa izpiše le razdaljo do najbolj oddaljenega kraja.

Tako kot prej računamo razdalje, vendar jih ne izpisujemo, temveč za vsako razdaljo pogledamo, ali je večja od največje doslej, in si jo v tem primeru zapomnimo. Ko je zanke konec, izpišemo največjo razdaljo.

x0 = float(input("Vnesi x: "))
y0 = float(input("Vnesi y: "))

najvecja_razdalja = 0
for ime, x, y in kraji:
    razdalja = sqrt((x0 - x) ** 2 + (y0 - y) ** 2)
    if razdalja > najvecja_razdalja:
        najvecja_razdalja = razdalja
print(najvecja_razdalja)

Obvezna naloga

Napiši program, ki mu uporabnik vnese koordinato kraja, program pa izpiše ime najbolj oddaljenega kraja.

To je pa isto kot prej, le da si poleg največje razdalje zapomnimo še ime kraja, tako da lahko po zanki izpišemo le-tega in ne razdalje.

x0 = float(input("Vnesi x: "))
y0 = float(input("Vnesi y: "))

najvecja_razdalja = 0
for ime, x, y in kraji:
    razdalja = sqrt((x0 - x) ** 2 + (y0 - y) ** 2)
    if razdalja > najvecja_razdalja:
        najvecja_razdalja = razdalja
        naj_kraj = ime
print(naj_kraj)

Dodatna naloga

Nekdo je prepotoval kraje v gornjem zaporedju. Vedno je šel naravnost (po potrebi skozi hrib; najbrž je šlo za črva). Kakšno razdaljo je prepotoval? (Pravilen odgovor je malo več kot 8000.)

Pri reševanju naloge upoštevaj, da še ne znamo napisati kraji[0]; oglate oklepaje doslej uporabljamo samo za definiranje seznamov.

V xp in yp si bomo zapomnili koordinati prejšnjega kraja. V skupna bomo računali skupno razdaljo, tako da bomo v vsakem koraku prišteli razdaljo med trenutno in prejšnjo točko.

skupna = 0
for ime, x, y in kraji:
    skupna += sqrt((x - xp) ** 2 + (y - yp) ** 2)
    xp, yp = x, y
print(skupna)

Na koncu zanke razglasimo trenutno točko za prejšnjo, xp, yp = x, y, tako da bo trenutna točka v naslednjem koraku prejšnja.

To skoraj deluje. A ne čisto. V začetku, v prvem krogu zanke, še nimamo prejšnje točke. Če je nimamo, pa recimo, da je None. Potem v zanki prištevajmo razdaljo do prejšnje točke le, če imamo prejšnjo točko.

skupna = 0
xp = yp = None
for ime, x, y in kraji:
    if xp != None:
        skupna += sqrt((x - xp) ** 2 + (y - yp) ** 2)
    xp, yp = x, y
print(skupna)

Nalogo se bomo nekoč naučili rešiti na bistveno krajši način:

print(sum(sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2) for (kraj1, x1, y1), (kraj2, x2, y2) in zip(kraji, kraji[1:])))

Ne pravim pa, da je bistveno lepši. Ali lepši - sploh.

Zelo dodatna naloga

V kakšnem vrstnem redu bi moral prepotovati kraje, da bi bila razdalja čim manjša?

Če ti naloga dela preglavice, morda najprej ugotovi, v kakšnem zaporedju bi moral prepotovati prvih pet krajev. Nato poskusi prvih šest in tako naprej.

Pri reševanju te naloge smeš uporabljati vse, kar smo se učili, kar se še bomo učili in tudi tisto, česar se ne bomo.

Tole je naloga za razmišljanje, reševanje pa ni prav perspektivno. Gre za enega od problemov, za katere še ne vemo, ali jih sploh znamo rešiti. Vsaj v doglednem času in z "običajnimi" računalniki. Kvantni računalniki so druga zgodba, saj znajo rešiti nekatere probleme, ki so za običajne računalnike prezahtevni.

Problem, ki ste ga reševali, je torej zelo znan in se imenuje problem trgovskega potnika. Znamo ga rešiti v doglednem času, a zgolj približno (torej ne da bi mogli biti prepričani, da smo našli idealno rešitev, verjetno pa smo našli kar dobro rešitev). Znamo ga rešiti tudi točno, vendar ne v doglednem času.

Rešitev druge vrste je takšna: grem čez vse možne razporede (to je, permutacije) in za vsako izračunam dolžino poti. Zapomnim si pot, ki je najkrajša. Manjša težavica je, da je vse možnih poti precej veliko.

>>> from math import factorial
>>> factorial(91)
1352001527678402962551665687594951421475868664769066777917417345971536707
71559994765685283954750449427751168336768008192000000000000000000000

Če smo torej pripravljeni počakati kakih toliko let, kolikor je gornja številka, če ji odbijemo kakšnih 10 ničel, je program, ki poišče najkrajšo pot, kar preprost:

from itertools import permutations
def razdalja(kraji):
    return sum(sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2) for (i0, x0, y0), (i1, x1, y1) in zip(kraji, kraji[1:]))

print(min((k for k in permutations(kraji)), key=razdalja))

Če smo neučakani, pa izračunamo tole reč za prvih devet krajev.

from itertools import permutations
def razdalja(kraji):
    return sum(sqrt((x0 - x1) ** 2 + (y0 - y1) ** 2) for (i0, x0, y0), (i1, x1, y1) in zip(kraji, kraji[1:]))

print(min((k for k in permutations(kraji[:9])), key=razdalja))

Nekateri izmed študentov so pisali programe, ki naj bi poiskali pravilno rešitev - vendar je ne. Kdor napiše program, ki bo hitro delal tudi za veliko število krajev (kaj pomeni hitro, vas uči kolega Sadikov pri Uvodu v računalništvo, zares pa se boste o tem učili v drugem letniku), bo zaslužil milijon dolarjev. Vendar večina računalnikarjev verjame, da se to ne da. Dokazati pa ne znamo...

Nekateri pa ste napisali odlične programe, ki zelo hitro najdejo kar dobro rešitev. Kudos.

마지막 수정됨: 화요일, 18 10월 2016, 12:08 PM