Sist endret: 23.09.2016  
 

Praksisoppgave - MsAlgoFan på ferie

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 13.11.2017 15:00

Denne øvingen er ikke laget ferdig ennå.

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
alletilalle.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
alletilalle.py Funksjonen korteste_rute(rekkefolge, nabomatrise, byer) og innlesing av nabomatrise fra input.
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 5
umulig

MsAlgoFan på ferie

Det er ikke nødvendig å lese historien for å løse oppgaven.

Algemannen våknet med et rykk til lyden av at datamaskinen hans ropte 'You've got mail!'. Hvem kan det være, tenkte han, som sender meg mail på dette tidspunktet av døgnet? Han var jo vant med å få fanmail av alt fra vakre beundrere til enda vakrere beundrere, men klokken var tross alt to på natten! Det fikk da være måte på tenkte han, mens han gikk bort til datamaskinen sin.

To: algemannen@superhelt.org
From: msalgofan87@vakker.no
Subject: Jeg vet du får mye mail, men jeg har et forslag!

Hei Algemannen,

Jeg er din absolutt største fan, og jeg synes du er veldig smart, flott og ikke minst
dødelig kjekk. Nå som det er ute av veien: Denne vinteren hadde jeg tenkt meg på ferie
rundt om i landet, men jeg simpelthen aaaaner ikke hvordan jeg skal gjøre det billigst mulig!

Siden jeg er en fattig og uskyldig studine så lurte jeg på om du kunne hjelpe meg?

xoxo MsAlgoFan87

Jasså, tenkte Algemannen, hun trenger hjelp? Vanligvis kan jeg ikke bruke tiden sin på slike trivialiteter, men Algemannen hjelper alltid en uskyldig studine i nød! MsAlgoFan hadde lagt ved en liste over byer hun ville besøke og i hvilken rekkefølge, samt prisene for å reise mellom de. Heldigvis har Algemannen gått på superheltskolen, hvor han lærte noen hendige triks for slike problemer! Det eneste han trenger å gjøre er å finne den kortest mulige veien å besøke alle byene i den oppgitte rekkefølgen, så kan han glede jenta. Kanskje får jeg være med? tenkte Algemannen før han satte i gang.

Oppgave

For å hjelpe den uskyldige studinen å finne den billigste måten å gjennomføre turen sin på, må du finne den korteste veien innom alle byene i den oppgitte rekkefølgen. Det finnes flere måter å implementere dette på, men å bruke en eller annen form for korteste-vei algoritme er nok et godt utgangspunkt.

Input består av følgende linjer:

  1. Antall tester som følger (input-eksempelet har f.eks. to tester).
  2. Antall byer(n) som skal besøkes.
  3. Rekkefølgen byene skal besøkes i.
  4. De neste n linjene er en nabomatrise, bestående av n integere per linje, som beskriver hvor mye det koster å reise fra en by til en annen. (Linje 3, tall nummer 4 beskriver for eksempel hvor mye det koster å reise fra by nummer tre til by nummer 4).

Merk følgende:

  • Det koster alltid 0 kroner å reise fra en by til seg selv.
  • Hvis det ikke går ann å komme seg direkte fra by i til by j vil tall j på linje i være -1. Det vil si at -1 betyr ingen kant, og 0 betyr med andre ord at det er gratis å reise mellom de to byene.
  • Hun skal alltid returnere til den byen hun kom fra!
  • Byer kan besøkes flere ganger, men vil bare telle når besøkt i riktig rekkefølge. For rekkefølgen 1 0 2 vil for eksempel 1 2 0 2 1 være lov, mens 1 2 0 1 vil ikke være lov.

For hver test så skal output bestå av en linje bestående av et tall; den laveste mulige kostnaden for å fullføre turen. Om det er umulig å besøke alle byene, så skal output være umulig.

Rammeverk

from sys import stdin, maxsize

def shortest_path(order_list, adjacency_matrix, cities):
    # SKRIV DIN KODE HER

testcases = int(stdin.readline())
for test in range(testcases):
    cities = int(stdin.readline())
    order_list = [int(city) for city in stdin.readline().split()]
    adjacency_matrix = []
    for city in range(cities):
    # SKRIV DIN KODE HER
    print(shortest_path(order_list, adjacency_matrix, cities))

Variabelbeskrivelse

Rammeverket lager folgende variabler for deg: 'rekkefolge' er en liste med tall som sier hvilken rekkefolge byene skal besokes i. Tallene i listen er altsaa indeksene til byene. [0, 2, 1] betyr altsaa at by 0 skal besokes forst, deretter by 2, faar by 1 til slutt. 'nabomatrise' er en nabomatrise for byene, som sier noe om hvor dyrt det er aa reise fra en by til en annen. 0 3 -1 1 0 1 1 3 0 Nabomatrisen over, betyr at det er gratis aa reise fra by 0 til by 0, fra by 1 til by 1, og fra by 2 til by 2. Det betyr ogsaa at kostnaden for aa reise fra by 0 til by 1 er 3, og at det er umulig aa reise direkte fra by 0 til 2, osv. 'byer' er et tall som sier hvor mange byer det er, altsaa hoyden og bredden til nabomatrisen. Dersom du fortsatt er usikker pà variablene kan det vaere smart aa printe de og se hva de faktisk inneholder.

Input-eksempel

2
3
0 2 1
0 1 2
1 0 1
1 3 0
2
0 1
0 -1
1 0

Tilhørende output

5
umulig

Hvordan teste Python-program

Unix

Du kan teste programmet ditt med kommandoen:

    python program.py < input.txt

Windows

  • Lagre programmet ditt på feks m:\tdt4120\
  • Åpne kommandolinje (Start -> Kjør -> cmd)
    • m:
    • cd \tdt4120
    • python.exe program.py < input.txt
  • Merk at hvis du bare skriver "python", ikke "python.exe", ser det ut til ofte å oppstå en feil fordi python prøver å kjøre inputfilen også.

Godbit