Programiranje

Ta naloga se ocenjuje, zato je ne smete izpustiti. Rešiti jo morate vsaj za oceno 6. Za določeno oceno je potrebno pravilno rešiti tudi vse naloge za nižje ocene. Nalogo oddate kot običajno, v eni datoteki.

Oddelek za gospodarstvo in motorni promet pri Mestni občini Ljubljana je za popularizacijo kolesarjenja uvedel sistem nagradnih točk za uporabo različnih veščin. Vožnja po travi je vredna tri točke, divjanje med pešci štiri točke, vožnja po avtocesti deset točk in tako naprej. Kolesar, ki zbere določeno število nagradnih točk, dobi vozniško dovoljenje za motorno vozilo kategorije C (+ koncesijo za parkiranje na pločniku).

Točkovanje:

• črepinje: 1,
• robnik: 1,
• lonci: 1,
• gravel: 2,
• bolt: 2,
• rodeo: 2,
• trava: 3,
• pešci: 4,
• stopnice: 6,
• avtocesta: 10.

Nekaj sprememb v primerjavi z nalogo Načrtovanje poti:

• Veščine so iste kot zadnjič, le da uporabljamo samo okrajšave.
• Ključi v zemljevidu so enaki, vendar sta v zemljevidu že obe smeri, tako da se vam ni potrebno zafrkavati s funkcijo dvosmerni_zemljevid.
• Vrednosti v zemljevidu so množice okrajšanih veščin, na primer {"pešci", "avtocesta"}. (Da bi neka povezava zahtevala divjanje med pešci na avtocesti, mogoče zveni hecno, a glede na to, da MOL že od pomladi odkriva, da so pločniki lahko tudi parkirišča, tudi preusmeritev prometa na pločnike ne bi bila preveliko presenečenje.)

Pri reševanju mi boste hvaležni za spodnjo sliko.

Za oceno 6

• Napiši funkcijo vrednost_povezave(povezava, zemljevid), ki vrne število nagradnih točk, ki jih dobi kolesar, če prevozi povezavo. Povezava je podana kot terka z imeni križišč, na primer ("A", "B"), torej v enaki obliki kot ključi zemljevida. Število točk je enako vsoti točk, ki jih dobi za potrebne veščine. Če so potrebne veščine za neko povezavo {"pešci", "avtocesta", "bolt"}, mora funkcija vrniti 16 (to je, 4 + 10 + 2).

• Napiši funkcijo najboljsa_povezava(zemljevid), ki vrne povezavo, za katero dobimo največ točk. Če je takšnih povezav več, lahko vrne poljubno izmed njih. (Vedno bosta vsaj dve, namreč ena in ista povezava v eno in drugo smer.)

Za oceno 7

• Napiši funkcijo vrednost_poti(pot, zemljevid), ki vrne število nagradnih točk, ki jih dobi kolesar za določeno pot, to je, vsoto nagradnih točk za vse povezave na tej poti. Če mora na poti večkrat uporabiti različno veščino, dobi točke za vsako uporabo. Pot je podana v obliki niza, kot smo že vajeni. Predpostaviti smete, da je pot možna.

• Napiši funkcijo najbolj_uporabna(pot, zemljevid), ki prejme tisto veščino, ki se največkrat pojavi na podani poti. Če je takšnih veščin več, lahko vrne poljubno med njimi. Če za neko pot ne rabi nobene veščine naj funkcije vrne None.

Za oceno 8

Napiši funkcijo do_nagrade(pot, zemljevid, meja), ki vrne mesto, do katere lahko pelje kolesar, tako da skupno število nagradnih točk pri tem še ne preseže podane meje meja, po kateri bi mu Zoki slovesno izročil plaketo in vozniško dovoljenje.

Če pot zaradi kake manjkajoče povezave ni možna, funkcija vrne točko, kjer se je kolesar prisiljen ustaviti.

Lahko pa se zgodi tudi, da pride do konca poti. V tem primeru funkcija seveda vrne zadnjo točko.

Za oceno 9

Imamo kolesarja, ki zna vse, vendar vsako veščino demonstrira največ enkrat na poti. Napiši funkcijo neponovljiva_pot(pot, zemljevid), ki vrne točko, do katere bo pripeljal tak kolesar. To je lahko - končna točka, če je pot možna, - točka, kjer bi moral prvič ponovno uporabiti eno od že uporabljenih veščin, - točka, iz katere sploh ni povezave v naslednjo točko na poti.

Za oceno 10

Napiši funkcijo mozna_pot(pot, zemljevid, vescine), ki je podobna prejšnji, vendar kolesar ne zna vsega, temveč le veščine iz podane množice. Tak kolesar se zato ustavi tudi, kadar neka povezava zahteva veščino, ki je ne obvlada.

Testi