I120 - Algoritmer, Datastrukturer og Programmering

Oppgavesett 7

Fredag 20.10.00

Oppgave 1

Vi skal i denne oppgaven lage en løkketest for rettede grafer.  For å teste algoritmene ligger det noen testfiler med grafer her. Formatet på filene er som følger:

v11 v12
v21 v22
.
vm1 vm2
#

der vi1 er en streng som identifiserer startnoden til kant i og vi2 målnoden til kanten. # angir slutten på filen.

  1. Lag en metode

    2. public Graph readGraphFromFile(instream)

    som leser inn en graf fra en fil med formatet som beskrevet over og returnerer den tilsvarende grafen.
     

  2. En rettet graf er en graf der alle kantene er rettet. Lag en metode

    3. public boolean isGraphAcyclic(Graph G, Vertex startnode)

    som returnerer false hvis og bare hvis den rettede grafen G inneholder en (rettet) løkke
    som kan nås fra node startnode. Metoden skal ha tidskompleksitet O(n+m).
    Hint: Istedetfor å "merke" besøkte noder vha en boolsk variabel for hver node, kan metoden passelig kalle en rekursiv metode

    boolean isGraphAcyclic(Graph G, Position startNode, Sequence aktuellenoder, Sequence besoktenoder)

    der aktuellenoder er nodene i "aktuell sti" og besoktenoder er alle nodene er har vært innom under løkketesten. Pass på at du ikke går i rekursjonsbrønner!
     

  3. Lag en metode

    4. boolean isGraphAcyclic(Graph G)

    som returnerer true hvis og bare hvis den rettede grafen G inneholder en (rettet) løkke.
     

  4. Test programmet ditt på testfilene som er angitt under punkt 1. Hvilke filer inneholder asykliske grafer?

Oppgave 2

En variasjon over golf spilles på et felt med N hull (nummerert med 0 <= h < N). Målet er å spille ballen raskest mulig fra et gitt hull x til et gitt hull y - men på en bestemt måte. Fra hull nummer i, er det lov å spille ballen til hull nummer  j hvis og bare hvis:
  1. j =i-1
  2. j=i+1
  3. j=2i>N
  4. i er partall og j=i/2
Programmer en algoritme spill(int N, int x, int y) som, gitt N, x og y beregner den raskeste (korteste) måten å spille ballen fra x til y. (x trenger ikke være mindre enn y!). Output skal være ruten ballen skal spilles gjennom, dvs en sekvens x, v1, v2,..., vk, y. F.eks:

Ekstraoppgave!

I spillet fra oppgave 2 hadde vi faste regler (1-3) for hvordan ballen spilles mellom hullene. Vi vil nå lage en generell algoritme som kan brukes uansett hvilke regler som definerer lovlige bevegelser fra et hull til neste. F.eks vil man kanskje spille etter regler der ballen kan spilles fra hullet i til hullet j hvis og bare hvis:
  1. j er en av {i-1, 2i+1,i/3}
  2. 0 <= j <= N
  3. å spille til hullet i/3 er tillatt kun når i er delelig med 3, dvs når i=3k for en eller annen k>0
Eksempel:
  1. Identifiser stedene i algoritmen fra oppgave 2 som må endres og design et interface Rules som vil kunne brukes i en generell algoritme. Forklar kort intensjonene med alle metodene. Reglene defineres alltid som i eksemplene over, dvs som aritmetiske uttrykk over heltallene som identifiserer hullene.

    2.  
  2. Programmer en algoritme spill(int N, int x, int y, Rules r) som kan brukes til å spille etter forskjellige regler avhengig av implmenetasjon av interface Rules.

    3.  
  3. Programmer to implementasjoner av interface Rules fra 3.3.1, ra og rb, slik at et kall til spill(N, x, y, ra) skal gi samme resultat som et kall til spill(N,x,y) fra oppgave 2, mens et kall til spill(N,x,y,rb) skal gi et resultat tilsvarende reglene 1-3 over.