podatek(kljuc, podatki)
Napiši funkcijo podatek(kljuc, podatki)
, ki dobi neko
vrednost kljuc
in nek seznam parov. Med njimi mora poiskati
tisti, par, pri katerem je prva vrednost enaka podanemu ključu; funkcija
mora vrniti drugo vrednost.
- Klic `podatek("Berta", [("Ana", 156), ("Berta", 167), ("Cilka", 160)])` vrne 167.
- Klic `podatek(42, [(42, "6 * 8"), (33, "11 * 3")])` vrne `"6 * 8"`.
- Klic `podatek("Koper", [('Piran', (0, 0)), ('Koper', (8, 2)), ('Žiri', (39, 60))])` vrne `(8, 2)`.
- Klic `podatek("Žiri", [("Piran", 23), ("Koper", 4), ("Žiri", 481)])` vrne 481.
Če ključa ne najde, (npr. v klicu
podatek("Žiri", [("Piran", 23), ("Koper", 4)])
) mora vrniti
None
.
Gremo čez podatke. Spremenljivki iz para bomo imenovali
k
in v
. V opravičilo, zakaj to ni neskladno z
mojim stalnim teženjem o tem, da je potrebno spremenljivki pametno
poimenovati, naj povem, da je ta par kar običajen: k
in
v
se v Pythonu stalno uporablja za kombinacijo key
in value, kar slučajno lepo sovpada s slovenskim ključ
in vrednost.
Če naletimo na ključ, ki se ujema s podanim, vrnemo vrednost. Če se
zanka izteče neuspešno vrnemo None
.
def podatek(kljuc, podatki):
for k, v in podatki:
if k == kljuc:
return v
return None
Eksplicitni return None
na koncu bi lahko tudi
izpustili, saj funkcije, ki ne vrnejo ničesar, vrnejo None
.
Vendar se šteje za lepo prakso, da v primeru, da funkcija
včasih vrne vrednost, le-ta vrne vrednost None
tudi, kadar nima česa vrniti. Da se ve, da nismo pozabili.
razdalja(t1, t2)
Napiši funkcijo razdalja(t1, t2)
, ki prejme dve terki,
ki predstavljata koordinati točk na ravnini. Vrniti mora evklidsko
razdaljo med točkama. Klic razdalja((0, 0), (3, 4))
mora
vrniti 5
.
Razpakiramo in izračunamo
from math import sqrt # najboljše je, da damo to na začetek programa
def razdalja(t1, t2):
= t1
x1, y1 = t2
x2, y2 return sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
oddaljenost(kraj1, kraj2, koordinate)
Napiši funkcijo oddaljenost(kraj1, kraj2, koordinate)
,
ki prejme imeni dveh krajev in seznam, ki vsebuje koordinate krajev v
takšni obliki, kot ga vidiš v tretjem primeru pri prvi funkciji.
Funkcija mora vrniti evklidsko razdaljo med krajema. (Dober nasvet:
funkcija naj kliče prejšnji funkciji.) Predpostaviti smeš, da se
koordinate obeh krajev nahajo v seznamu.
Če uporabimo funkciji podatek
in razdalja
,
opravimo s tem kar v enem koraku.
def oddaljenost(kraj1, kraj2, koordinate):
return razdalja(podatek(kraj1, koordinate), podatek(kraj2, koordinate))
visina(kraj1, kraj2, visine)
Napiši funkcijo visina(kraj1, kraj2, visine)
, ki prejme
imeni dveh krajev in višine krajev v seznamu, kot ga vidiš v četrtem
primeru pri prvi funkciji. Funkcija naj vrne višinsko razliko (vzpon) od
prvega kraja do drugega; če je prvi višji, funkcija vrne negativno
vrednost. Spet smeš predpostaviti, da sta višini obeh krajev znani.
Še lažje.
def visina(kraj1, kraj2, visine):
return podatek(kraj2, visine) - podatek(kraj1, visine)
Na podlagi izkušenj iz prejšnjih let sem domneval - in nisem se motil - da bo veliko študentov kompliciralo takole.
def visina(kraj1, kraj2, visine):
= podatek(kraj2, visine) - podatek(kraj1, visine)
razlika if razlika > 0:
return razlika
else:
return -razlika
To je seveda narobe: če je razlika
negativna in vrnemo
-razlika
, vrnemo pozitivno razliko, kadar je le-ta
negativna. Ko odkrijejo to napako, jo popravijo z
def visina(kraj1, kraj2, visine):
= podatek(kraj2, visine) - podatek(kraj1, visine)
razlika if razlika > 0:
return razlika
else:
return -abs(razlika)
To deluje, ni pa zelo smiselno. Navodilo pravi samo, da razliko vedno merimo od prvega do drugega kraja in včasih je ta pač negativna. Ampak rezultat takega navodila me vedno zabava: študenti naredijo napako prav zato, ker poskušajo upoštevati tisto, kar bi brez mojega opozorila spregledali (in bi vse delalo). :)
cas(s, h)
Napiši funkcijo cas(s, h)
, ki vrne čas, ki ga porabi nek
kolesar, da prevozi pot dolžine s
(v kilometrih), ki se
dvigne za h
(v metrih; h
je lahko tudi
negativen, če gre za spust). Čas izračunamo tako:
- kolesar v osnovi porabi 2,4 minute za kilometer razdalje.
- Če gre za dvig, se čas poveča še za 1 / 12 minute za vsak meter višine;
- če gre za spust, pa se čas zmanjša za 1 / 250 minute za vsak meter spusta.
Primera:
- Klic `cas(2, 300)` vrne 29,8: za 2 km porabi 2 * 2,4 = 4,8 minut, poleg tega pa porabi 1 / 12 * 300 = 25 minut zaradi 300 m dviga.
- Klic `cas(10, -100)` vrne 23,6: za 10 km porabi 10 * 2,4 = 24 minut, vendar se to zmanjša za 100 / 250 = 0.4 minute zaradi spuščanja.
(Posebej drugi primer kaže, da vsaka podobnost te formule z resničnimi dogodki ni zgolj naključna temveč tudi ne prav zelo verjetna.)
No, tole pa zahteva nek pogoj in ločeno obravnavo pozitivnih in negativnih višin. Naredimo lahko, recimo, tako:
def cas(s, h):
if h > 0:
return 2.4 * s + 1 / 12 * h
else:
return 2.4 * s + 1 / 250 * h
cas_med(kraj1, kraj2, koordinate, visine)
Napiši funkcijo
cas_med(kraj1, kraj2, koordinate, visine)
, ki vrne čas, ki
ga bo kolesar potreboval za vožnjo od prvega do drugega kraja. Pomen
argumentov in formule so takšne kot v prejšnjih nalogah. (Uporabljaj
funkcije, ki jih že imaš!)
Kot na opominja navodilo, moramo le poklicati funkcije, ki jih že imamo.
def cas_med(kraj1, kraj2, koordinate, visine):
= oddaljenost(kraj1, kraj2, koordinate)
razdalja = visina(kraj1, kraj2, visine)
razlika return cas(razdalja, razlika)
Šlo bi tudi tako:
def cas_med(kraj1, kraj2, koordinate, visine):
return cas(oddaljenost(kraj1, kraj2, koordinate),
visina(kraj1, kraj2, visine))
Vendar to ni bistveno krajše, praktično nič hitrejše, je pa manj
berljivo. Prva različica je boljša, ker poimenuje vmesne vrednosti in
bolj jasno pove, kaj podajamo funkciji cas
.
skupni_cas(kraji, koordinate, visine)
Napiši funkcijo skupni_cas(kraji, koordinate, visine)
,
ki prejme seznam krajev, skozi katere bo šel kolesar, in vrne skupni
čas, ki ga bo porabil za to pot.
Iti moramo prek vseh parov zaporednih krajev. To lahko dosežemo z motoviljenjem z indeksi, za Python zglednejša pa je tale rešitev:
def skupni_cas(kraji, koordinate, visine):
= 0
skupni for kraj1, kraj2 in zip(kraji, kraji[1:]):
+= cas_med(kraj1, kraj2, koordinate, visine)
skupni return skupni
Čez ne tako dolgo časa pa bomo vedeli, da se to bolj zares sprogramira tako:
def skupni_cas(kraji, koordinate, visine):
return sum(cas_med(kraj1, kraj2, koordinate, visine)
for kraj1, kraj2 in zip(kraji, kraji[1:]))
Kolesar bi rad čimbolj skrajšal čas potovanja. Izpustiti sme en kraj - lahko prvega, lahko zadnjega, lahko kateregakoli vmes.
Napiši funkcijo skrajsaj(kraji, koordinate, visine)
, ki
vrne seznam brez tega kraja. Klic
skrajsaj(["Piran", "Ljubljana", "Koper"], koordinate, visine)
vrne ["Piran", "Koper"]
. Enak rezultat vrneta tudi klica
skrajsaj(["Ljubljana", "Piran", "Koper"], koordinate, visine)
in
skrajsaj(["Piran", "Koper", "Ljubljana"], koordinate, visine)
.
Dodatna naloga ni bila posebej težka. Edina sitnost je bila sestavljanje skrajšanega seznama.
Nekateri so šli z zanko čez kraje in z remove
odstranjevali posamezne kraje iz seznama. Ker bi vas rad naučil o tem,
kako nevarna funkcija je remove
, sem v testih namerno
sestavil tudi pot, v katerem se en kraj ponovi. remove
odstrani prvo ponovitev.
V podobno past so se ujeli tisti, ki so sestavljali nov seznam tako, da so prepisali vanj vse elemente razen tega, ki ga hočejo izločiti. Ti so odstranili obe ponovitvi kraja.
Vsekakor je bilo tu potrebno delati z indeksi. Jaz sem se lotil tako, da sem s pomočjo rezin sestavljal nove sezname, v katerih je manjkal prvi, drugi, tretji element in tako naprej.
def skrajsaj(kraji, koordinate, visine):
= skupni_cas(kraji, koordinate, visine)
naj_cas = kraji
naj_pot for i in range(len(kraji)):
= kraji[:i] + kraji[i + 1:]
predlog = skupni_cas(predlog, koordinate, visine)
cas if cas < naj_cas:
= cas, predlog
naj_cas, naj_pot return naj_pot
Za začetek predpostavimo, da je najboljša rešitev kar celotna pot. Tekom zanke se bo izkazalo, da to ni res. Če je pot slučajno prazna, pa bo funkcija vrnila to, prazno pot, kar je tudi dobro.
Funkcija je, v primerjavi z gornjimi kar dolga. Čez neveliko časa bomo znali napisati krajšo.
def skrajsaj(kraji, koordinate, visine):
return min((kraji[:i] + kraji[i + 1:] for i in range(len(kraji))),
=lambda x: skupni_cas(x, koordinate, visine)) key
Obe rešitvi počneta isto, le da v drugi rešitvi funkcija
min
počne tisto, kar smo morali v prvi rešitvi
sprogramirati sami.
Obe rešitvi sta tudi nekoliko počasni, ker vedno znova računata trajanje (skoraj) celotne poti. Hitrejša, a daljša rešitev je, da opazujemo zaporedne trojke krajev in preverjamo, pri kateri trojki prihranimo največ, če izpustimo srednji kraj. Pri tem je sitno predvsem, da moramo ločeno obravnavati začetek in konec.
def skrajsaj(kraji, koordinate, visine):
= cas_med(kraji[0], kraji[1], koordinate, visine)
naj_prihranek = 0
naj_indeks = cas_med(kraji[-2], kraji[-1], koordinate, visine)
prihranek if prihranek > naj_prihranek:
= prihranek
naj_prihranek = len(kraji) - 1
naj_indeks for i, (k1, k2, k3) in enumerate(zip(kraji, kraji[1:], kraji[2:])):
= (cas_med(k1, k2, koordinate, visine)
prihranek + cas_med(k2, k3, koordinate, visine)
- cas_med(k1, k3, koordinate, visine)
) if prihranek > naj_prihranek:
= prihranek
naj_prihranek = i + 1
naj_indeks return kraji[:naj_indeks] + kraji[naj_indeks + 1:]
Recimo, da bi v vseh krajih v seznamu koordinate
zabili
visok jambor in nato okrog Slovenije napeli zelo dolgo elastiko. Ta bi
se dotikala le nekaterih jamborjev - tistih, "na robu". Ljubljane gotovo
ne, saj je preveč v sredini, gotovo pa bi se dotikala Murske Sobote, ki
štrli ven.
Napiši funkcijo, ki prejme seznam koordinat in vrne seznam krajev (po vrsti, začenši od poljubnega kraja), ki bi se jih elastika dotikala.
Rešitev te naloge pa posebej, ob predavanjih za tiste, ki znajo že malo več.
This task includes tests. Your solution will be accepted as correct only if it passes them. See instructions for running tests.
Implement a function podatek(kljuc, podatki)
, which
receives a certain value key
and a list of pairs
(podatki
). The function must find a pair in which the first
value equals the key, and it must return the second value of the
pair.
podatek("Berta", [("Ana", 156), ("Berta", 167), ("Cilka", 160)])
returns 167.podatek(42, [(42, "6 * 8"), (33, "11 * 3")])
returns "6 * 8"
.podatek("Koper", [('Piran', (0, 0)), ('Koper', (8, 2)), ('Žiri', (39, 60))])
returns (8, 2)
.podatek("Žiri", [("Piran", 23), ("Koper", 4), ("Žiri", 481)])
return 481.If the key is not found (as in
podatek("Žiri", [("Piran", 23), ("Koper", 4)])
) the
function must return None
.
Implement a function razdalja(t1, t2)
, which gets
two tuples that represent coordinates of two points in a plain. It must
return the Euclidean distance between them. The call
razdalja((0, 0), (3, 4))
must return
5
.
Implement a function
oddaljenost(kraj1, kraj2, koordinate)
, which gets names of
two places and a list with names and coordinates in the same form as in
the third example for the first function. The function must return the
Euclidean distance between the two places. (A good advice: the function
should call the first two functions.)
You may assume that the list includes both places.
Implement a function visina(kraj1, kraj2, visine)
,
which gets names of two places and list of heights above sea level as in
the fourth example for the first function. The function must return the
ascent from the first place to the second; the ascent is of course
negative if the second place is lower than the first. You may again
assume that both places appear in the list.
Implement a function cas(s, h)
, which returns time
needed by a cylist for a path of length s
kilometers with
h
meters of ascent (h
can also be negative).
The time is computed using the following formulae:
Examples:
cas(2, 300)
returns 29.8: for 2 km she needs 2 *
2.4 = 4.8 minutes, which is increased by 1 / 12 * 300 = 25 minutes
because of 300 m ascent.cas(10, -100)
returns 23.6: for 10 km she needs 10
* 2.4 = 24 minutes, which is decreased by 100 / 250 = 0,4 minutes
because of descent.(The second example clearly shows that any similarity of this formulae with real times is purely coincidental and not very probable.)
Implement a function
cas_med(kraj1, kraj2, koordinate, visine)
, that return time
that the cyclist will need from the first to the second place. The
meaning of arguments and the formulae are the same as before. (And so is
the advice: use the functions that you already have.)
Implement a function
skupni_cas(kraji, koordinate, visine)
, which gets a list of
places that the cyclist will traverse, and returns the total time needed
for the trip.
The cyclist would like to decrease the time needed for the trip. He may skip one single place -- the first, the last or any in between.
Implement a function
skrajsaj(kraji, koordinate, visine)
, which returns a list
without that place. The order of other places must stay the same. Call
skrajsaj(["Piran", "Ljubljana", "Koper"], koordinate, visine)
returns ["Piran", "Koper"]
(Piran and Koper are nearby
towns on the seaside, and Ljubljana is 100 km away). The same result is
returned by
skrajsaj(["Ljubljana", "Piran", "Koper"], koordinate, visine)
and
skrajsaj(["Piran", "Koper", "Ljubljana"], koordinate, visine)
.
(Solve this for your amusement; it does not affect the grade.)
Assume a large mast is set at each place in the list
koordinate
. Then we stretch an elastic rope around
Slovenia. This rope surely does not touch Ljubljana, which is a rather
central town, but it touches Murska Sobota, which is in the corner, not
far from Austria and Hungary.
Write a function that gets a list of coordinates and returns a list of towns (in order, but starting from any) that the rope will touch.