bild
Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD1339 / inda13 / Vårens uppgifter / Uppgift 11

Uppgift 11 våren 2014

Uppgiften ska lämnas till din övningsledare på övningen den 25/4.

För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter.

Hemuppgift

Läs om filer och felhantering i kapitel 12 i programmeringsboken. Studera programmet Grep.java. Det är en förenklad version (som inte hanterar reguljära uttryck) av Unixkommandot grep. Programmet använder "try with resource", som introducerades i Java 7, för att automatiskt stänga filen. GrepOld.java är en äldre version som stänger filen i en finally-sats.

Jämför också gärna med grep.go, motsvarande program skrivet i Go.

Skriftlig uppgift

Din uppgift är att skriva ett program, i Java eller Go, som anropas från kommandoraden i Unix. Om du använder Java så ska anropet vara:

java Path FROM TO

För Go blir det:

path FROM TO
FROM och TO är två heltal som anger en startnod och en slutnod i en graf. Programmet ska skriva ut noderna på någon väg från FROM till TO om det finns en sådan väg i grafen, annars skriver programmet ut en tom rad. Vägen ska innehålla minimalt antal noder. Använd breddenförstsökning.

Grafen ska lagras i en fil med namnet Distances.txt. Noderna är numrerade 0, 1, 2, ..., n-1. Filens första rad innehåller talet n. De andra raderna innehåller tre tal i, j och d separerade med blanktecken. Det positiva talet d anger avståndet mellan noderna i och j. Filen kan också innehålla "//"-kommentarer och tomma rader. Kommentarerna fungerar på samma sätt som i Java och Go. Här är ett exempel på en fil som beskriver en liten graf.

// This is a database with distances between a number
// of cities. The cities are numbered 0, 1, 2, ..., n-1.
// The first lines contains the integer n, i.e. the
// number of cities. Each following line contains three
// integers i, j, and d separated by spaces. The positive
// number d is the distance between i and j.

6        // Size

0 1 100  // First edge
0 3 80
0 5 25
1 2 120
1 5 60
2 3 50
3 4 100
4 5 200  // Last edge

Vid eventuella fel så ska programmet skriva ut ett relevant felmeddelande till stderr och inte skriva något på stdout.

Valfri extrauppgift

Kraven är desamma som i den obligatoriska uppgiften men du skall i stället skriva ut den kortaste vägen mellan start- och slutnod. Använd Dijkstras algoritm.

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2014-04-21