Dol z Marsovci!
Marsovci še kar najedajo. Zdaj so se parkirali pred Zemljo in imajo očitno slabe namene. Na srečo je Slovenska vojska pripravljena na vse: na strateških mestih ima parkirane ČNVL-je (Čisto nevidne vesoljske ladje), ki bodo uničile marsovsko floto. Manjka jim le še strateški načrt. Ta je predmet te domače naloge.
Za razumevanje naloge si najprej oglejte animacijo. Marsovske ladje so predstavljene s krogci, hrabri ČNVL pa s kvadratki.
Za oceno 6
Napiši funkcijo
razdalja(x, y)
, ki prejme terki s koordinatami dveh točk in vrne evklidsko razdaljo med njimi. Da bomo pripravljeni tudi na transdimenzionalna bitja, je dimenzija točk lahko poljubna (od 1 do kolikor je treba). Razdaljo v večdimenzionalnem prostoru računamo podobno kot v dvo- ali tridimenzionalnem$$d(x, y) = \sqrt{\sum_{i=0}^{n-1}(x_i - y_i)^2}$$
- Klic
razdalja((5, 12), (2, 16))
vrne 5 (to je, $\sqrt{(5 - 2)^2 + (12 - 16)^2} = \sqrt{3^2 + 4^2}$). - Klic
razdalja((5, ), (8, )
(razdalja na premici) vrne 3 (to je $\sqrt{(5 - 8)^2}$). - Klic
razdalja((1, 7, 4, 2, 6, -7, 4), (-1, 10, 5, 2, 6, -8, 3)
(razdalja v 7-dimenzionalnem prostoru) vrne 4.
- Klic
Napiši funkcijo
najblizja(marsovec, ladje)
, ki dobi terko s koordinatami marsovske ladje in seznam terk s položaji naših ladij, ČNVL-jev. Vrniti mora koordinate najbližjega ČNVL-a. (Ta bo zadolžen za napad na to marsovsko ladjo.)- Klic
najblizja((1, 1), [(0, 0), (5, 2), (-8, 3)]
vrne(0, 0)
, saj je marsovski ladji na koordinatah(1, 1)
najbližji ČNVL na koordinatah(0, 0)
. - Klic
najblizja((-7, 2, 5, 1), [(0, 0, 5, 2), (5, 2, 5, 2), (-8, 3, 5, 2)])
vrne(-8, 3, 5, 2)
.
- Klic
Napiši funkcijo
dodeli_ladje(marsovci, ladje)
, ki prejme seznam marsovskih in naših ladij. Vrniti mora seznam terk, ki je enako dolg kot seznammarsovci
: i-ti element rezultata vsebuje koordinate ČNVL-ja, ki je najbližji i-ti marsovski ladji.- Klic
dodeli_ladje([(1, 1), (0, 0), (-7, 2), (5, 1)], [(0, 0), (5, 2), (-8, 3)])
vrne[(0, 0), (0, 0), (-8, 3), (5, 2)]
, saj je prvima dvema marsovcema najbližji ČNVL na koordinatah(0, 0)
, tretjemu ČNVL na(-8, 3)
, četrtemu pa tisti na(5, 2)
.
- Klic
Za oceno 7
Napiši funkcijo
sredisce(s)
, ki prejme seznam ali množico koordinat točk in vrne terko s koordinatami njihovega središča. Koordinate te točke so izračunane kot poprečne koordinate točk vs
po vsaki dimenziji posebej.Število točk v
s
je poljubno. Točke so poljubno-dimenzionalne.- Klic
sredisce([(2, 8), (6, 10)
vrne(4, 9)
.
- Klic
Napiši funkcij
razpostavi_ladje(skupine)
, ki poišče optimalno razpostavitev ladij. Funkcija prejme neko razdelitev marsovskih ladij v skupine; skupine so opisane s seznamom množic koordinat (torej v obliki, ki jo vrne funcijaskupine_marsovcev
, ki je opisana spodaj). Funkcija mora vrniti seznam koordinat središč skupin.- Klic
razpostavi_ladje([{(0, 1), (2, 2), (1, 3), (4, 5)}, {(100, 101), (103, 98)}, {(51, 52), (45, 50)}])
vrne seznam, ki vsebuje
[((0 + 2 + 1 + 4) / 4, (1 + 2 + 3 + 5) / 4), ((100 + 103) / 2, (101 + 98) / 2), ((51 + 45) / 2, (52 + 50) / 2)]
(Seveda ne vsebuje teh izrazov, temveč ustrezne vrednosti.)
Za oceno 8
Napiši funkcijo
skupine_marsovcev(marsovci, ladje)
, ki vrne seznam množic terk s koordinatami marsovskih ladij. Bistvo te funkcije je grupiranje marsovskih ladij. Če bodo marsovske ladje uničevali trije ČNVL-je, se vsaka množica nanaša na enega od njih in vsebuje tiste ladje, ki jih bo uničil ta, pripadajoči ČNVL.Vrstni red množic je lahko poljuben. Predpostaviti smeš, da bo vsak ČNVL uničil vsaj eno ladjo (oziroma: s tem vprašanjem se ne ukvarjaj.)
Klic
skupine_marsovcev( [(0, 1), (2, 2), (51, 52), (100, 100), (1, 3), (4, 5), (45, 50), (103, 98)], [(0, 0), (50, 50), (100, 100)]))
vrne
[{(0, 1), (2, 2), (1, 3), (4, 5)}, {(100, 100), (103, 98)}, {(51, 52), (45, 50)}]
Prva množica vsebuje koordinate marsovskih ladij, ki jih uniči NČVL na koordinatah
(0, 0)
, druga ladje, ki jih uniči NČVL na koordinatah(100, 100)
in tretja tiste, ki jih uniči(50, 50)
.Funkcija v bistvu vrne množice koordinat ladij, ki so v animaciji iste barve.
Namig: čeprav ni videti tako, ti bodo tu prišli prav slovarji.
Za oceno 9
Napiši funkcijo
nakljucna(marsovci, ladij)
, ki vrne nek naključen razpored podanega števila ladij. Funkcija mora vrniti seznam, ki vsebujeladij
terk koordinat. Koordinate so izžrebane iz koordinat marsovskih ladij. Zai
-to koordinato izberemo koordinatoi
neke naključne marsovske ladje.Klic
nakljucna([(5, 8), (2, 17), (1, 33), (4, 9)], 3)
bi lahko vrnil, recimo
[(1, 8), (4, 17), (2, 8)]
. Vsaka prva koordinata je žrebana iz prvih koordinata in druga iz drugih.Funkcija je uporabna za začetno razpostavljanje ladij.
Za oceno 10
Napiši funkcijo
optimiraj_ladje(marsovci, ladje)
, ki prejme položaje marsovcev in neko začetno pozicijo naših ladij. Funkcija naj izmenično ponavlja naslednja koraka:- določi skupine, ki pripadajo posamezni ladji, ko to počne funkcija
skupine_marsovcev
; - na podlagi teh skupin, naj izračuna boljše položaje ladij, se pravi, prestavi vsako ladjo v središče skupine, ki ji je dodeljena;
- ker so se ladje premaknile, naj izračuna novo dodelitev marsovcev;
- ker to spremeni skupine, naj premakne ladje v nova središča skupin;
- ker so se ladje premaknile ...
Prej ko slej se bodo ladje nehale premikati in skupine nehale spreminjati. Takrat naj se postopek ustavi. Funkcija naj vrne končne koordinate ladij.
Funkcija v bistvu izvaja optimizacijo, ki jo kaže video. Video, konkretno, predstavlja štiri klice funkcije iz različnih začetnih pozicij.
Za pomoč je v testu za oceno 9 shranjen potek položajev ladij v zadnjem testu. Če ga funkcija izpisuje, mora biti (do določenega števila decimalnih mest) enak.
- določi skupine, ki pripadajo posamezni ladji, ko to počne funkcija
O testih
V testih so funkcije že zastavljene: imajo nekaj dokumentacije v enem od običajnih oblik, poleg tega pa so označeni tipi argumentov in rezultatov. Če tega ne razumeš, ignoriraj. Če razumeš, ti lahko služi kot dodatna dokumentacija.
Ker je vrstni red elementov seznamov, ki jih vračajo tvoje funkcije včasih poljuben, bodo testne funkcije včasih uredile rezultat tvoje funkcije in ga primerjale z urejenim pričakovanim rezultatom. Naj te to ne zmede: funkciji ni potrebno ničesar urejati.
Če tvoja funkcija vrača seznam, kjer testi pričakujejo terko, se bodo (najbrž) pritožili. Bodi pozoren na oklepaje v izpisu.
(3)
ni terka temveč samo 3
v oklepaju. (3, )
je terka.
Če test pričakuje, da bo funkcija vrnila [(4 + 6) / 2, (3 + 9) / 3]
, seveda pričakuje [5, 4]
. V tej obliki je zapisano le, da lažje razberemo, kaj mora funkcija računati.
Testi
- 1 December 2021, 10:31 AM