• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges.
• Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.

Prioritet och associativitet hos operatorerna i C

Uppgift 1 (1 p)

Uppgift 2 (1 p)

Uppgift 3 (1 p)

Uppgift 4 (2 p)

    float m[N][N][7];

a) Vi vill summera talen i matrisen m, med de här programraderna:

    summa = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < 7; ++k)
                summa += m[i][j][k];

b) Vi provkör programmet med N = 1000. och ser att summeringen av matrisen m tar 5 sekunder. Hur lång tid kan vi räkna med att den summeringen tar om N = 2000?

c) Hur lång tid kan vi räkna med att summeringen tar om N = 1 miljon?

Uppgift 5 (1 p)

    char c1 = 1, c2 = 3, c3 = 4;

    c1 = c2 & c3;
    c2 = c2 | c3;
    c3 &= 7;

Scenario till uppgift 6 och 7

Vi ska hantera robotar och spelplaner i ett C-program.

Uppgift 6 (15 p)

Datatypen ska bestå av en posttyp ("struct") som innehåller x- och y-koordinaterna, och dessutom ett namn på roboten. Namn är textsträngar som kan vara högst 10 tecken långa.

• init_robot, som initierar en Robot-post. Man skickar med x-värdet, y-värdet och robotens namn till funktionen.
• save_robot, som sparar en Robot-post på en öppen textfil. Man skickar med en FILE*, och en post.
• fetch_robot, som läser in en Robot-post från en öppen textfil. Man skickar med en FILE*.
• distance, som tar två Robot-poster som argument, och returnerar avståndet mellan robotarna som ett flyttal. (Använd Pythagoras sats.)
• is_collision, som jämför två Robot-poster och returnerar ett sant värde om robotarna befinner sig på samma position.

a) (4p) Skriv (hela) include-filen Robot.h.

b) (8p) Skriv (hela) implementationsfilen Robot.c.

c) (3p) För att provköra Robot-paketet skapar vi ett program, på filen test_robots.c, som gör följande:

• Skapar tre Robot-poster för robotarna Cameron, Cromartie och WALL-E. Robotarna ska ges lämpliga koordinater, och initieras med hjälp av funktionen init_robot.
• Använder distance för att beräkna avståndet mellan Cromartie och WALL-E, samt skriver ut resultatet.

Uppgift 7 (19 p)

Välj själv hur spelplanen ska lagras. Det ska gå att skriva följande funktioner, som ska finnas med:

• init_board, som initierar en spelplan så den blir tom, dvs inte innehåller några roboter.
• put_robot, som placerar ut en robot på spelplanen. Funktionen måste kolla att det inte uppstår en kollision med någon robot som redan finns på planen, och om det gör det ska den inte placera ut den nya roboten.
• find_robot, som tar en x-koordinat och en y-koordinat som argument, och som returnerar den robot som eventuellt finns på den positionen på spelplanen.
• remove_robot, som tar en x-koordinat och en y-koordinat som argument, och som tar bort den robot som eventuellt finns på den positionen från spelplanen.
• walk_robots, som flyttar alla robotar på spelplanen ett steg i en slumpmässig riktning (upp, ner, vänster eller höger). Om en robot (A) flyttar sig till en position där en annan robot (B) redan står, ska roboten B tas bort från planen.

• Spelplanens storlek är inte begränsad (annat än av storleken på datatypen heltal), så även om man från början placerar alla robotarna i närheten av origo, så kan de vandra iväg mycket långt.
• Inte heller antalet robotar på spelplanen är begränsat (annat än av vad som får plats i minnet på datorn.)
• Vi har inga särskilda krav på prestanda, och vi accepterar att programmet kan gå långsamt om antalet robotar blir stort.
• Tips: Funktionen rand ger ett slumpmässigt heltal, som är större än eller lika med noll.

a) (4p) Skriv (hela) include-filen Board.h.

b) (8p) Skriv (hela) implementationsfilen Board.c.

c) (4p) För att provköra Board-paketet skapar vi ett program, på filen test_board.c, som först skapar en tom spelplan, och sen läser in hundra robotar från filen robots.txt med hjälp av funktionen fetch_robot, och också placerar ut var och en av dem på spelplanen med funktionen put_robot. Som avslutning ska funktionen walk_robots anropas en gång.

d) (3p) Vilken tidskomplexitet har de tre funktionerna find_robot, put_robot och walk_robots? Vad händer om vi vill placera ut flera miljoner robotar? Skulle din lösning behöva ändras, och i så fall hur?