Napišite funkcijo cena(zasedenost, cene)
, ki prejme
numpyjevo tabelo zasedenost
tipa bool
, ki ima
šest stolpcev in toliko vrstic, kolikor vrst ima letalo ter vsebuje
True
na mestih, ki ustrezajo zasedenim sedežem in
False
na mestih, ki ustrezajo prostim. Poleg tega dobi
Pythonov seznam cene
, ki vsebuje cene vozovnic za sedeže v
prvih treh stolpcih, na primer [200, 175, 193]
, če sedeži
ob oknu (stolpec 0) stanejo 200, sedeži na sredini (stolpec 1) 175 in
sedeži ob hodniku (stolpec 2) 193 evrov. Cene sedežev v drugih treh
stolpcih so zrcalno enake tem (na primer 193, 175 in 200).
Funkcija mora vrniti vsoto cen vseh prodanih vozovnic. Funkcija mora biti napisana v numpyju. Točkovanje bo upoštevalo eleganco rešitve.
Najprej rešitev, potem sledi razlaga.
def cena(zasedenost, cene):
return np.sum(zasedenost * (cene + cene[::-1]))
Najprej razširimo cene na vseh šest stolpcev. Če imamo Pythonov
seznam cene
, na primer
= [200, 175, 193] cene
lahko k njemu pripnemo še prezrcaljen seznam,
+ cene[::-1] cene
[200, 175, 193, 193, 175, 200]
pa dobimo cene za vse stolpce. Zdaj pa imamo dve poti. Očitnejša (a, kot se bo izkazalo, malenkost daljša, vendar vam pri ocenjevanju tega nisem štel v slabo), je, da najprej preštejemo zasedenost vseh stolpcev.
import numpy as np
= np.array([
zasedenost True, False, False, False, False, False],
[False, True, True, False, False, False],
[False, False, False, True, True, True],
[False, False, False, True, True, True],
[False, True, False, True, True, True],
[False, False, False, True, True, False],
[False, False, False, False, True, False]
[ ])
Zasedenost po stolpcih dobimo tako, da tabelo seštejemo po osi 0,
sum(zasedenost, axis=0) np.
array([1, 2, 1, 4, 5, 3])
To tabelo pomnožimo s cenami.
sum(zasedenost, axis=0) * (cene + cene[::-1]) np.
array([200, 350, 193, 772, 875, 600])
pa dobimo vsote cen po stolpcih. To, končno, seštejemo v skupno ceno.
sum(np.sum(zasedenost, axis=0) * (cene + cene[::-1])) np.
2990
Druga rešitev je, da celotno tabelo pomnožimo s cenami.
* (cene + cene[::-1]) zasedenost
array([[200, 0, 0, 0, 0, 0],
[ 0, 175, 193, 0, 0, 0],
[ 0, 0, 0, 193, 175, 200],
[ 0, 0, 0, 193, 175, 200],
[ 0, 175, 0, 193, 175, 200],
[ 0, 0, 0, 193, 175, 0],
[ 0, 0, 0, 0, 175, 0]])
In to seštejemo.
sum(zasedenost * (cene + cene[::-1])) np.
2990
Druga rešitev je krajša, prva (tista, ki smo jo napisali tudi na vrhu) pa najbrž hitrejša. Z vidika tega predmeta sta obe enako dobri.
Imamo tabelo, v kateri so pari poletov in pristankov, na primer
[(360, 420), (400, 580), (485, 1300), (490, 600), (600, 800), (650, 720), (700, 800), (780, 800), (930, 1380), (950, 1380), (950, 1000), (1100, 1200)]
.
Časi so v minutah od polnoči. Tako prvi par, (360, 420) pomeni da neko
letalo vzleti ob 6. uri zjutraj in pristane ob 7. uri. Vsa letala
vzletajo in pristajajo na istem letališču, saj gre za turistične
prelete.
Nek turist bi rad v istem dnevu naredil čim več poletov. Pri tem pa
mora med pristankom nekega leta in odletom naslednjega miniti vsaj 60
minut, da gre vmes po sendvič. Napišite funkcijo
stevilo_letov(prvi, leti)
, ki prejme prvi
let,
na katerega bo šel in seznam vseh letov, ter vrne največje število
poletov, ki jih lahko opravi v enem dnevu.
stevilo_letov((360, 420), leti)
vrne 5
, saj lahko gre na lete
(360, 420), (490, 600), (700, 800), (950, 1000), (1100, 1200)
.stevilo_letov((600, 880), leti)
vrne
3
, saj bo ujel samo
(600,800), (950, 1000), (1100, 1200)
.Tole je v bistvu globina rodbine. :) Let B je "potomec" nekega leta A, če mu lahko sledi, torej, če let B odleti vsaj 60 minut kasneje kot let A.
def stevilo_letov(prvi, leti):
= 0
naj_letov for let in leti:
if prvi[1] + 60 <= let[0]:
= stevilo_letov(let, leti)
letov if letov > naj_letov:
= letov
naj_letov return naj_letov + 1
Ko sestavljaš nalogo iz rekurzije zlahka spregledaš, da je naloga rešljiva tudi brez. Kolega iz laboratorija me je opozoril na preprosto rešitev: v vsakem koraku vzamemo letalo, ki se bo čimprej vrnilo.
def stevilo_letov(naslednji, leti):
= 0
letov while naslednji != None:
= naslednji[1] + 60
cas = None
naslednji for let in leti:
if let[0] >= cas and (naslednji is None or let[1] < naslednji[1]):
= let
naslednji += 1
letov return letov
Argument prvi
smo zaradi higiene preimenovali v
naslednji
- predstavljal bo naslednji let. Imeli bomo
zanko, ki bo tekla, dokler imamo še kakšen naslednji let. Znotraj zanke
shranimo čas pristanka naslednjega leta in z zanko (znotraj zanke) med
vsemi leti iščemo tistega, ki ima najzgodnejši pristanek. To bo naš
naslednji let...
To rešitev bi morali razumeti vsi, saj ne vsebuje ničesar preveč zapletenega (in predvsem nobene rekurzije :).
Kdor bolj obvlada Python, lahko napiše še krajše.
def stevilo_letov(naslednji, leti):
= 0
letov while naslednji != None:
= min((let for let in leti if let[0] >= naslednji[1] + 60),
naslednji =lambda x: x[1],
key=None)
default+= 1
letov return letov
Še imenitnejša (pravilnejša, hitrejša) rešitev je urediti lete po časih pristankov. Predstavljajmo si potnika, ki začne z določenim letom. Vsakič ko pristane, pogleda seznam in izbere naslednji let z najzgodnejšim pristankom...
def stevilo_letov(naslednji, leti):
= sorted(leti, key=lambda x: x[1])
leti = 1
letov for let in leti[leti.index(naslednji):]:
if let[0] >= naslednji[1] + 60:
= let
naslednji += 1
letov return letov
"Skrivnosten" je le sort
- tisti
key=lambda x: x[1]
poskrbi, da bo elemente (pare, lete)
primerjal po elementu z indeksom 1, torej po pristanku.
Neka letalska družba pa sedežev ne dodeljuje vnaprej, temveč lahko potniki zgolj izrazijo željo. Potnike nato vkrcavajo po seznamu. Vsak potnik se usede na želeni sedež, če je ta že zaseden, pa se pomika nazaj po vrstah, dokler ne naleti na vrsto, v kateri je sedež v želenem stolpcu prazen, ter ga zasede. Če so, na primer, že zasedeni sedeži 12C, 13C in 14C, se bo potnik, ki bi želel sedeti na 12C, usedel na 15C. Letalska družba uporablja dolga letala, ki imajo 130 vrst, obenem pa ji ne gre prav dobro (čudno, čudno), zato smete predpostaviti, da se bo po tem postopku našel sedež za vsakogar.
Napišite funkcijo razpored(seznam)
, ki dobi seznam s
pari (ime_potnika, zeleni_sedez)
in vrne nov seznam, ki je
enak temu, le da so sedeži zamenjani z sedeži, ki jih bodo potniki
dejansko dobili.
Pomoč: če je c
črka A, B, C, D, E ali F, je
ord(c) - 65
enak 0, 1, 2, 3, 4 oz. 5. Mogoče vam pride
prav.
Tole je naloga iz množic in iz zanke while
. Lahko pa
tudi ni iz množic. Vsekakor pa je iz zanke while
. :)
Nekam bo potrebno shranjevati zasedena mesta. Lahko, torej,
pripravimo množico zasedeni
z zasedenimi mesti, poleg tega
pa seznam dejanski
, v katerega bomo postavljali potnike in
ga na koncu vrnili.
def razpored(zelje):
= set()
zasedeni = []
dejanski for potnik, sedez in zelje:
= int(sedez[:-1]), sedez[-1]
vrsta, stolpec while (vrsta, stolpec) in zasedeni:
+= 1
vrsta
zasedeni.add((vrsta, stolpec))f"{vrsta}{stolpec}"))
dejanski.append((potnik, return dejanski
Ker smo toliko delali z numpy
-jem -- pa tudi zaradi
tega, kako so bili shranjeni podatki v prvi nalogi -- je gotovo prišlo
komu na misel namesto množice uporabiti numpy-jevo tabelo. (Priznanje:
tudi sam sem nalogo najprej rešil tako. Vendar je to predvsem posledica
tega, kaj sem razmišljal, ko sem jo sestavljal.)
def razpored(zelje):
= np.zeros((130, 6), dtype=bool)
zaseden = []
razpored for potnik, sedez in zelje:
= int(sedez[:-1]), ord(sedez[-1]) - 65
vrsta, stolpec while zaseden[vrsta, stolpec]:
+= 1
vrsta = True
zaseden[vrsta, stolpec] f"{vrsta}{sedez[-1]}"))
razpored.append((potnik, return razpored
Takšna rešitev je malenkost bolj zapletena, ker potrebujemo še indeks
stolpca. Tega dobimo z ord
, kot je svetoval opis
naloge.
Morda bi koga zmotilo, dvojno shranjevanje podatkov. To, kaj je
zasedeno, je razvidno že iz razpored
, torej je
zaseden
v bistvu nepotreben. To je res, vendar je nerodno,
da je razpored
seznam, v katerem je zoprno preverjati, ali
je določen sedež zaseden. Če že hočemo, pa lahko uporabimo slovar, ki za
vsak sedež pove, kdo sedi na njem.
def razpored(zelje):
= {}
zasedeni for potnik, sedez in zelje:
= int(sedez[:-1]), sedez[-1]
vrsta, stolpec while (vrsta, stolpec) in zasedeni:
+= 1
vrsta = potnik
zasedeni[vrsta, stolpec]
= []
dejanski for (vrsta, stolpec), potnik in zasedeni.items():
f"{vrsta}{stolpec}"))
dejanski.append((potnik, return dejanski
Prvi del se je malenkost poenostavil. V return
pa moramo
iz slovarja sestaviti pare potnikov in sedežev.
Drugi del lahko poenostavimo, če znamo sestavljati izpeljane sezname:
return [(potnik, f"{vrsta}{stolpec}")
for (vrsta, stolpec), potnik in zasedeni.items()]
Napišite funkcijo ravnotezje(ime_datoteke)
, ki prejme
ime datoteke s podatki, ločenimi z vejico. V prvi vrstici so zapisana
imena stolpcev. Eden od njih se imenuje sedez; sedeži so zapisani v
običajni obliki, npr. 12F ali 1C ali 128E. Funkcija mora vrniti razliko
med številom potnikov, ki sedijo na desni (stolpci D, E, F) in levi
(stolpci A, B, C) strani letala. Če, recimo, na desni sedi 7 potnikov
več, vrne 7; če je 7 potnikov več na levi, vrne -7.!
Ta, ki je normalno in pridno delal domače naloge, se ob tej nalogi
lahko zahvali za poceni točke. Potrebno je le uporabiti
DictReader
, brati vrednosti v ustreznem stolpcu in glede na
zadnji znak spreminjati ravnotežje letala. Lahko ločeno štejemo levo- in
desnosedeče ter na koncu vrnemo razliko ...
import csv
def ravnotezje(ime_datoteke):
= desno = 0
levo for vrstica in csv.DictReader(open(ime_datoteke, encoding="utf-8"), delimiter=","):
if vrstica["sedez"][-1] <= "C":
+= 1
levo else:
+= 1
desno return desno - levo
... lahko pa razliko računamo že kar sproti.
def ravnotezje(ime_datoteke):
= 0
ravno for vrstica in csv.DictReader(open(ime_datoteke, encoding="utf-8"), delimiter=","):
if vrstica["sedez"][-1] <= "C":
-= 1
ravno else:
+= 1
ravno return ravno
Kakor vam drago, je rekel Vili.
Napišite funkcijo vozni_redi(potniki, ime_datoteke)
.
Argument potniki je seznam z imeni potnikov, številkami letov in pari
(ura, minuta) za odhod in prihod. Primer podatkov je, recimo
[("Ana Argon", "LH2832", (12, 10), (13, 20)), ("Berta Bor", "UO391", (15, 5), (20, 30)), ("Cilka Cankar", "LH192", (7, 0), (12, 30))]
.
Funkcija mora v datoteko s podanim imenom zapisati tabelico z imeni,
leti in časi, v naslednji obliki.
Ana Argon LH2832 12:10-13:20
Berta Bor UO391 15:05-20:30
Cilka Cankar LH192 7:00-12:30
Točno obliko - število presledkov - razberite iz testov.
Tudi tale je bila kar poceni.
def vozni_redi(potniki, ime_datoteke):
= open(ime_datoteke, "w", encoding="utf-8")
f for potnik, let, (od_h, od_m), (pri_h, pri_m) in potniki:
f"{potnik:20} {let:>6} {od_h:2}:{od_m:02}-{pri_h:2}:{pri_m:02}\n") f.write(
Ker smo tule napisali veliko različnih rešitev, združimo vse skupaj še v "pričakovano" rešitev izpita. Tudi za vtis o dolžini celotnega izpita.
import re
import csv
import numpy as np
def cena(zasedenost, cene):
return np.sum(zasedenost * (cene + cene[::-1]))
def stevilo_letov(prvi, leti):
= 0
naj_letov for let in leti:
if prvi[1] + 60 <= let[0]:
= stevilo_letov(let, leti)
letov if letov > naj_letov:
= letov
naj_letov return naj_letov + 1
def razpored(zelje):
= set()
zasedeni = []
dejanski for potnik, sedez in zelje:
= int(sedez[:-1]), sedez[-1]
vrsta, stolpec while (vrsta, stolpec) in zasedeni:
+= 1
vrsta
zasedeni.add((vrsta, stolpec))f"{vrsta}{stolpec}"))
dejanski.append((potnik, return dejanski
def ravnotezje(ime_datoteke):
= 0
ravno for vrstica in csv.DictReader(open(ime_datoteke, encoding="utf-8"), delimiter=","):
if vrstica["sedez"][-1] <= "C":
-= 1
ravno else:
+= 1
ravno return ravno
def vozni_redi(potniki, ime_datoteke):
= open(ime_datoteke, "w", encoding="utf-8")
f for potnik, let, (od_h, od_m), (pri_h, pri_m) in potniki:
f"{potnik:20} {let:>6} {od_h:2}:{od_m:02}-{pri_h:2}:{pri_m:02}\n") f.write(