Imamo seznam nekaterih slovenskih krajev 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

Izpiši imena vseh krajev.
Izpiši imena vseh krajev in njihove razdalje od koordinatnega izhodišča.
Izpiši imena vseh krajev, ki ležijo znotraj pravokotnika, katerega levo spodnje oglišče je (10, -20) in desno zgornje (50, 30). Program naj bo seveda napisan tako, da lahko te številke tudi spremenimo.

Rešitev

Prva naloga je služila temu, da se spomnimo, kako z zanko prek seznama trojk.

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

Namesto tega bi lahko pisali tudi kaj bolj groznega, vse do

for i in range(len(kraji)):
    print(kraji[i][0])

Vendar je ono zgoraj veliko pregledneje.

Druga naloge doda samo malo računanja. Toliko, da res potrebujemo x in y.

from math import *
for ime, x, y in kraji:
    print(ime, sqrt(x ** 2 + y ** 2))

To je, spet, veliko preglednejše od

from math import *
for i in range(len(kraji)):
    print(kraji[i][0], sqrt(kraji[i][1] ** 2 + kraji[i][2] ** 2))

V tretji pa dodamo pogoj. Tu nam pride prav, če se spomnimo, da lahko pogoje nizamo.

minx = 10
maxx = 50
miny = -20
maxy = 30

for ime, x, y in kraji:
    if minx <= x <= maxx and miny <= y <= maxy:
        print(ime)

Meje "okna" smo shranili v štiri spremenljivke. Če jih je kdo napisal kar v pogoj, mu tega ne bomo zamerili.

Obvezna naloga

Napiši program, ki izpiše ime najbolj severnega, najjužnejšega, najzahodnejšega in najvzhodnejšega kraja (v tem vrstnem redu).

Rešitev

Spodnja rešitev predpostavlja, da imamo vsaj po en kraj s pozitivnimi in z negativnimi koordinatami x. (Zakaj?)

naj_S = naj_J = naj_V = naj_Z = 0
for ime, x, y in kraji:
    if y > naj_S:
        naj_S = y
        naj_S_kraj = ime
    if y < naj_J:
        naj_J = y
        naj_J_kraj = ime
    if x > naj_V:
        naj_V = x
        naj_V_kraj = ime
    if y < naj_Z:
        naj_Z = x
        naj_Z_kraj = ime

print(naj_S_kraj)
print(naj_J_kraj)
print(naj_Z_kraj)
print(naj_V_kraj)

V naj_S, naj_J, naj_Z in naj_V bodo vsebovali koordinate najbolj severnega, najbolj južnega, najzahodnejšega in najvzhodnejšega kraja. Če je trenutni kraj bolj severno od najbolj severnega doslej (if y > naj_S), si zapomnimo trenutno koordinato kot najbolj severno (naj_S = y) in ime trenutnega kraja kot ime najbolj severnega kraja (naj_S_kraj = ime). Isto frazo ponovimo še za vse ostale kraje.

Sam bi to morda napisal malo krajše, tako da bi hkrati prirejal imena in koordinate.

naj_S = naj_J = naj_V = naj_Z = 0
for ime, x, y in kraji:
    if y > naj_S:
        naj_S, naj_S_kraj = y, ime
    if y < naj_J:
        naj_J, naj_J_kraj = y, ime
    if x > naj_V:
        naj_V, naj_V_kraj = x, ime
    if y < naj_Z:
        naj_Z, naj_Z_kraj = x, ime

print(naj_S_kraj)
print(naj_J_kraj)
print(naj_Z_kraj)
print(naj_V_kraj)

No, če sem čisto iskren, bi napisal

from operator import itemgetter

print(max(kraji, key=itemgetter(1))[0])
print(max(kraji, key=itemgetter(2))[0])
print(min(kraji, key=itemgetter(1))[0])
print(min(kraji, key=itemgetter(2))[0])

Ali pa kar

from operator import itemgetter
print("\n".join(f(kraji, key=itemgetter(i))[0] for f in (max, min) for i in (1, 2)))

Dodatna naloga

Program naj poišče in izpiše tri kraje, ki so si med seboj najbolj oddaljeni v tem smislu, da je ploščina trikotnika med njimi največja.

Rešitev

Da rešimo to nalogo, moramo znati napisati zanko v zanko v zanki. Če nimamo ravno računalnika iz leta 1990, bo program dovolj hiter.

maxp = 0
maxk = None
for k1, x1, y1 in kraji:
    for k2, x2, y2 in kraji:
        for k3, x3, y3 in kraji:
            a = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
            b = sqrt((x3 - x1) ** 2 + (y3 - y1) ** 2)
            c = sqrt((x2 - x3) ** 2 + (y2 - y3) ** 2)
            s = (a + b + c) / 2
            q = s * (s - a) * (s - b) * (s - c)
            if q < 0:
                q = 0
            p = sqrt(q)
            if p > maxp:
                maxp = p
                maxk = k1, k2, k3
print(maxp)
print(maxk)

Za vsako trojko krajev izračunamo stranice trikotnika (Evklid) in ploščino (Heron). Zaradi napak, ki jih računalnik naredi pri zaokrožanju, se lahko zgodi, da bo tisto, kar je pod korenom, negativno. Tedaj je ploščina trikotnika enaka 0 ali pa vsaj zelo majhna.

Tako napisan program ni ravno remek delo. Primerno je za tretji teden programiranja, za kaj več pa ne.

Za začetek se lahko spomnimo, da se da ploščino trikotnika med točkami s podanimi koordinatami lahko izračuna tudi z drugo formulo.

maxp = 0
maxk = None
for k1, x1, y1 in kraji:
    for k2, x2, y2 in kraji:
        for k3, x3, y3 in kraji:
            p = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2
            if p > maxp:
                maxp = p
                maxk = k1, k2, k3
print(maxp)
print(maxk)

Ta program je bistveno hitrejši.

Nato nam pride na misel, da vsako trojko preverimo šestkrat (abc, acb, bac, bca, cab in abc). To rešimo takole:

maxp = 0
maxk = None
for i, (k1, x1, y1) in enumerate(kraji):
    for j, (k2, x2, y2) in enumerate(kraji[:i]):
        for k3, x3, y3 in kraji[:j]:
            p = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2
            if p > maxp:
                maxp = p
                maxk = k1, k2, k3
print(maxp)
print(maxk)

To je zdaj bistveno hitrejše.

Kombiniranje lahko prepustimo tudi Pythonu.

from itertools import combinations
maxp = 0
maxk = None
for (k1, x1, y1), (k2, x2, y2), (k3, x3, y3) in combinations(kraji, 3):
        p = abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2
        if p > maxp:
            maxp = p
            maxk = k1, k2, k3
print(maxp)
print(maxk)

In tako pridemo do (nemogoče) rešitve (obljubite, da ne boste tako programirali)

print([ime for ime, x, y in max(combinations(kraji, 3), key=lambda c: abs(c[0][1] * (c[1][2] - c[2][2]) + c[1][1] * (c[2][2] - c[0][2]) + c[2][1] * (c[0][2] - c[1][2])) / 2)])

Sicer pa bi se morali naloge, če bi jo hoteli rešiti res zgledno in hitro, lotiti popolnoma drugače. Kako, vam lahko pove asistent Tomaž. :)

Zadnja sprememba: torek, 17. oktober 2017, 19.04

Course Activities

Nedavno dostopani predmeti

Ogrevalne naloge

Rešitev

Obvezna naloga

Rešitev

Dodatna naloga

Rešitev