Programiranje

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.

• 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).

• Napiši funkcijo dodeli_ladje(marsovci, ladje), ki prejme seznam marsovskih in naših ladij. Vrniti mora seznam terk, ki je enako dolg kot seznam marsovci: 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).

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 v s 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).

• 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 funcija skupine_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 vsebuje ladij terk koordinat. Koordinate so izžrebane iz koordinat marsovskih ladij. Za i-to koordinato izberemo koordinato i 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.

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