Övningsuppgifter Programmeringsteknik med C och Matlab

1 Programmeringskoncept

Uppgifter som tränar grundläggande programmeringskoncept som uttryck, loopar, funktioner och if-satser.

1.1 Minimala program

Några minimala problem för att komma igång.

1.1.1 Hello world

Skriv ett program som skriver ut texten "Hello World" på skärmen, dvs int main(int argc,char**argv) följt av en rad med printf("Hello World\n");.

Svårigheten består i att få till ovanstående med alla klamrar och andra detaljer som C:s syntax kräver.

För att kompilera er lösning spara er fil som main.c och skriv in följande kommando i terminalen.

gcc -Wall -o main main.c

Därefter ska den gå att köra med kommandot

./main

och bör skriva ut

Hello World

1.1.2 Anropa program

Något som kan vara bra att kunna när man ska programmera är att köra programmen man skrivit. Här följer några korta tips om hur man kör program från kommandoraden under unix.

För att starta ett program som inte är installerat i systemet anger man sökvägen till programmet följt av programnamnet. Sökvägarna . och .. representerar nuvarande respektive ovanförvarande katalog.

Exempel

./main

detta startar programmet main som finns i nuvarande katalog.

Om man sedan vill skicka parametrar till program kan man skriva parametrarna efter programnamnet.

./main en-parameter 'en annan parameter'

Notera att jag skrev ihop den första parametern med ett bindestreck och omgav den andra med citattecken. Om man inte gör detta tolkas i stället varje ord som en separat parameter, vilket kan vara ett problem.

1.1.3 Skriva ut uttryck

Skriv ett nytt program som i stället för att skriva ut ''Hello World'' skriver ut resultatet av följanden matematiska uttryck.

5
5.0
5/2
5.0/2
5/2.0
3*4+5
3*4.0+5

Reflektera över resultaten och fundera på vad som händer. Korrekta resultat är

5=5
5.0=5.0
5/2=2
5.0/2=2.5
5/2.0=2.5
3*4+5=17
3*4.0+5=17.0

Ni kan skriva ut heltal med printf("%d\n",ERT_TAL) och decimaltal med printf("%lf\n",ERT_TAL).

Kompilera med samma kommandon som ovan.

1.1.4 Variabler

När vi vill beräkna komplicerade matematiska uttryck kan det ibland vara fördelaktigt att först beräkna resultaten av delformler och spara i variabler.

Exempelvis kan

y = $\displaystyle {\frac{{(7*5)-1}}{{(7*5)+1}}}$

förenklas till

x	=	7*5
y	=	$\displaystyle {\frac{{x-1}}{{x+1}}}$

Skriv ett program där du brutit ut lämpliga bitar av följande uttryck och skrivit ut dem på skärmen.

${\frac{{(7*5)-1}}{{(7*5)+1}}}$
(4 + 7*8 - 3)²
3.1415*1 + 3.1415*2 + 1415*3
(1 + 3.0*50000)/(78*90000)

C-syntaxen för heltalsvariabler är int x=5; och för decimaltal double x=5;, i båda fallen kan värdet och namnet väljas relativt fritt.

Det finns inget exakt facit på den här uppgiften, tanken är att ni ska bryta ut så att ni får ett så lättläst uttryck som möjligt. Det gäller alltså att hitta en bra avvägning mellan antalet variabler och uttryckens längd.

1.2 Enkla matematiska uttryck

Många program, särskilt inom ingenjörsvetenskaperna, har till uppgift att göra matematiska beräkningar. Dessa program är till stor del uppbyggda av matematiska uttryck. Det kan vara enkla saker som att addera 1 till en räknare eller mer komplicerade matematiska formler som till exempel räknar ut geometriska samband.

Många av de mest använda matematiska funktionerna finns implementerade i ett av C:s standardbibliotek, som kan inkluderas via #include <math.h>, vilket ni kan ha nytta av i vissa uppgifter.

Uppgifterna som följer avser att visa på några typer av uttryck och hur dessa kan användas för att implementera enkla matematiska funktioner i C.

1.2.1 Cirkelarea

Skriv en funktion som räknar ut en cirkels area givet dess radie.

Ni ska använda följande funktionssignatur

double circleArea(double radius);

och ett värde på π med minst 5 värdesiffror, tex 3.1416.

Använd följande givna kod och ersätt /*TODO*/ med
return ert-uttryck;

#include <stdio.h>

double circleArea(double radius)
{
    /*TODO*/
}

/*program som anropas med en radie som parameter och
* skriver ut cirkelarean som den radien ger*/
int main(int argc,char**argv)
{

    /* kontrollerar om antalet parametrar är korrekt
    * om inte skrivs ett felmedelande ut */
    if(argc==2)
    {
        double in;

        /* konverterar parametern till ett flyttal
        * vid fel skrivs error medelande ut*/
        if(sscanf(argv[1],"%lf",&in)==1)
        {
            /*anropar er funktion och skriver
            * ut resultatet*/
            printf("%lf\n",circleArea(in));
        }
        else
        {
            fprintf(stderr,"Programparametern är inte en siffra\n");
            return 2;
        }
    }
    else
    {
        fprintf(stderr,"Programmet kräver exakt 1 parameter\n");
        return 1;
    }
    return 0;
}

1.2.2 Hypotenusan i rätvinklig triangel

Skriv en funktion som räknar ut längden av hypotenusan i rätvinklig triangel, givet längden av de två kateterna.

Ni ska använda följande funktionssignatur.

double hypotenusa(double katet1,double katet2);

Använd följande kod för att testa er lösning

#include <stdio.h>

double hypotenusa(double katet1,double katet2)
{
    /*TODO*/
}

/*program som anropas med tva tal som parametrar och
* skriver ut hypotenusan som de talen ger*/
int main(int argc,char**argv)
{

    /* kontrollerar om antalet parametrar är korrekt
    * om inte skrivs ett felmedelande ut */
    if(argc==3)
    {
        double in1;
        double in2;

        /* konverterar parametern till ett flyttal
        * vid fel skrivs error medelande ut*/
        if((sscanf(argv[1],"%lf",&in1)==1)
            &&(sscanf(argv[2],"%lf",&in2)==1))
        {
            /*anropar er funktion ok skriver
            * ut resultatet*/
            printf("%lf\n",hypotenusa(in1,in2));
        }
        else
        {
            fprintf(stderr,"Programparametrarna är inte siffror\n");
            return 2;
        }
    }
    else
    {
        fprintf(stderr,"Programmet kraver exakt 2 parametrar\n");
        return 1;
    }
    return 0;
}

1.3 If-satser

Många gånger finns det skäl att göra olika beräkningar beroende på värdet på till exempel en funktionsparametrar eller värden lästa från en fil eller från användaren. Till detta används if-satser som tillåter oss att specificera ett villkor och vad vi ska göra om villkoret är uppfyllt och, om vi så önskar, också vad vi ska göra om det inte är uppfyllt.

1.3.1 Är talet negativt

Skriv en enkel funktion som tar ett tal som parameter och returnerar 0 om talet är icke-negativt och något annat (exempelvis 1) om talet är negativt. (Tänk på att C betraktar alla värden skilda från 0 som sant.)

Använd följande signatur.

int negative(double x);

Ni kan använda följande kod för att testa er lösning.

#include <stdio.h>

int negative(double x)
{
    /*TODO*/
}

int main(int argc,char**argv)
{

    /* kontrollerar om antalet parametrar är korrekt
    * om inte skrivs ett felmedelande ut */
    if(argc==2)
    {
        double in;

        /* konverterar parametern till ett flyttal
        * vid fel skrivs error medelande ut*/
        if(sscanf(argv[1],"%lf",&in)==1)
        {
            /*anropar er funktion och skriver
            * ut resultatet*/
            if(negative(in))
            {
                printf("talet är negativt\n");
            }
            else
            {
                printf("talet är inte negativt\n");
            }
        }
        else
        {
            fprintf(stderr,"Programparametern är inte en siffra\n");
            return 2;
        }
    }
    else
    {
        fprintf(stderr,"Programmet kräver exakt 1 parameter\n");
        return 1;
    }
    return 0;
}

1.3.2 Finns talet i intervallet

Skriv en funktion som testar om ett tal finns i ett givet intervall och returnerar 1 om talet finns i intervallet och 0 om talet är utanför. Betrakta intervallet som stängt, det vill säga om ett tal är lika med ett av de två gränsvärdena finns det i intervallet.

Använd följande signatur.

/*bounds inclusive*/
int inInterval(double x,double lowerbound,double upperbound);

Använd följande kod för att testa er lösning. För att göra det måste ni dels implementera funktionen och sedan anropa den på angivet ställe i koden samt använda ytterligare en if-sats för att skriva ut om talet ligger i intervallet eller inte. Tips: se den givna koden i förra uppgiften.

#include <stdio.h>

/*bounds inclusive*/
int inInterval(double x,double lowerbound,double upperbound)
{
    /*TODO*/
}

int main(int argc,char**argv)
{

    /* kontrollerar om antalet parametrar är korrekt
    * om inte skrivs ett felmedelande ut */
    if(argc==4)
    {
        double in;
        double upper;
        double lower;

        /* konverterar parametern till ett flyttal
        * vid fel skrivs error medelande ut*/
        if((sscanf(argv[1],"%lf",&in)==1)
            &&(sscanf(argv[2],"%lf",&lower)==1)
            &&(sscanf(argv[3],"%lf",&upper)==1))
        {
            /*anropar er funktion och skriv
            * ut resultatet*/
            /*TODO if sats här som skriver ut resultat*/
        }
        else
        {
            fprintf(stderr,"Programparametrarna är inte en siffror\n");
            return 2;
        }
    }
    else
    {
        fprintf(stderr,"Programmet kräver exakt 3 parametrar\n");
        return 1;
    }
    return 0;
}

1.3.3 Vem är äldst

Skriv en funktion som tar reda på vilken av två personer som är äldst. Returera 0 om andra personen är äldst och något annat om första personen är äldst eller de är lika gamla.

Följande signatur ska användas.

int older(int year1,int month1,int day1,int year2,int month2,int day2);

Använd följande kod för att testa er lösning. För att göra det måste ni dels implementera funktionen och dels anropa den på angivet ställe i koden, samt använda ytterligare en if-sats för att skriva ut om första personen är äldst eller inte.

#include <stdio.h>

int older(int year1,int month1,int day1,int year2,int month2,int day2)
{
    /*TODO*/
}

int main(int argc,char**argv)
{

    /* kontrollerar om antalet parametrar är korrekt
    * om inte skrivs ett felmedelande ut */
    if(argc==7)
    {
        int y1,m1,d1;
        int y2,m2,d2;

        /* konverterar parametern till ett flyttal
        * vid fel skrivs error medelande ut*/
        if((sscanf(argv[1],"%d",&y1)==1)
            &&(sscanf(argv[2],"%d",&m1)==1)
            &&(sscanf(argv[3],"%d",&d1)==1)
            &&(sscanf(argv[4],"%d",&y2)==1)
            &&(sscanf(argv[5],"%d",&m2)==1)
            &&(sscanf(argv[6],"%d",&d2)==1))
        {
            /*anropar er funktion och skriv
            * ut resultatet*/
            /*TODO if sats här som skriver ut resultat*/
        }
        else
        {
            fprintf(stderr,"Programparametrarna är inte en siffror\n");
            return 2;
        }
    }
    else
    {
        fprintf(stderr,"Programmet kräver exakt 6 parametrar\n");
        return 1;
    }
    return 0;
}

1.4 Funktioner

Funktioner är ett sätt att utöka de operationer man kan använda i uttryck likt funktioner i matematiken som sin och cos. I C kan funktioner även ha sidoeffekter, något jag inte kommer att gå in på här.

Vi har redan använt funktioner med en given signatur i tidigare uppgifter. I de följande uppgifterna får ni skriva signaturen själva.

1.4.1 Min och max

Min och max är ett par mycket enkla funktioner som är förvånansvärt användbara. Ni ska här implementera dem för flyttal. Funktionerna fungerar så att dom tar två parametrar och returnerar det största eller det minsta.

Använd följande kod för att testa funktionerna.

#include <stdio.h>

/*TODO er funktion här*/

int main(int argc,char**argv)
{

    /* kontrollerar om antalet parametrar är korrekt
    * om inte skrivs ett felmedelande ut */
    if(argc==3)
    {
        double in1;
        double in2;

        /* konverterar parametern till ett flyttal
        * vid fel skrivs error medelande ut*/
        if((sscanf(argv[1],"%lf",&in1)==1)
            &&(sscanf(argv[2],"%lf",&in2)==1))
        {
            /*TODO er testkod här*/
        }
        else
        {
            fprintf(stderr,"Programparametrarna är inte siffror\n");
            return 2;
        }
    }
    else
    {
        fprintf(stderr,"Programmet kräver exakt 2 parametrar\n");
        return 1;
    }
    return 0;
}

Skriv alltså två program med hjälp av testkoden ovan, ett som implementerar min och ett som implementerar max.

1.4.2 Upphöjt i två

Skriv en funktion square som tar ett heltal och kvadrerar det.

Ni kan använda följande kod för att testa er lösning.

#include <stdio.h>

/*TODO funktion*/

int main(int argc,char**argv)
{

    /* kontrollerar om antalet parametrar är korrekt
    * om inte skrivs ett felmedelande ut */
    if(argc==2)
    {
        double in;

        /* konverterar parametern till ett flyttal
        * vid fel skrivs error medelande ut*/
        if(sscanf(argv[1],"%lf",&in)==1)
        {
            /*TODO testkod*/
        }
        else
        {
            fprintf(stderr,"Programparametern är inte en siffra\n");
            return 2;
        }
    }
    else
    {
        fprintf(stderr,"Programmet kräver exakt 1 parameter\n");
        return 1;
    }
    return 0;
}

1.5 Vektorer (array)

En av styrkorna med datorer är att de kan behandla stora mängder data snabbt. För att kunna hantera stora datamängder behöver vi organisera dem på ett effektivt sätt. Arrayer tillhandahåller en sådan möjlighet. De utgör sekvenser av tal eller andra datatyper. Alla element i sekvensen har ett nummer som kan användas för att referera till dem. Det första elementet i sekvensen har nummer 0.

Man kan läsa och ändra på värden i dessa sekvenser genom att referera till elementens sekvensnummer.

Ett exempel:

        int sekvens[3]={1,2,3};/*innehåller värdena 1 2 3*/

        printf("%d\n",sekvens[0]);/*skriv ut första värdet (1)*/
        printf("%d\n",sekvens[1]);/*skriv ut andra värdet (2)*/
        printf("%d\n",sekvens[2]);/*skriv ut sista värdet (3)*/

        sekvens[1]=4;/*ändra andra värdet till 4*/

        printf("%d\n",sekvens[1]);/*skriv ut andra värdet (4)*/

        printf("%d\n",sekvens[0]+sekvens[2]);/*skriv summan av första och sista värdet*/

1.5.1 Vektorer av char: Strängar

En mycket vanlig form av vektorer är vektorer av tecken (bokstäver), också kallade strängar. Strängar är sekvenser av tecken och avslutas med ett NULL-tecken i slutet. NULL-tecknet är ett tecken med värdet 0 som inte har någon grafisk representation.

Modifiera följande kod genom att ändra alla mellanslag till bindestreck. För att ta reda på vilka sekvensnumer de tecken ni vill ändra har räkna från början av strängen.

#include <stdio.h>

int main(int argc,char**argv)
{
    char text[]="upp delbart ord";/*medveten särskrivning*/
    printf("%s\n",text);/* %s används för att skriva ut strängar */

    /*TODO lägg till kod som modifierar text här*/

    printf("%s\n",text);/*notera den ändrade utskriften om ni gjort rätt*/
    return 0;
}

1.5.2 Byt plats på element: statisk längd

Givet följande kod lägg till kod för att vända på vektorn, dvs flytta första elementet sist, näst första näst sist och så vidare.

#include <stdio.h>

int main(int argc,char**argv)
{
    int seq[5]={1,2,3,4,5};
    /* skriver ut vektorn */
    printf("[%d %d %d %d %d]\n"
            ,seq[0],seq[1],seq[2],seq[3],seq[4]);

    /*TODO lägg till kod som vänder vektorn här*/

    /* skriver ut vektorn */
    printf("[%d %d %d %d %d]\n"
            ,seq[0],seq[1],seq[2],seq[3],seq[4]);
    return 0;
}

1.5.3 Byt plats på element: variabel längd

Skriv en funktion som byter plats på det sista och mittersta elementet i en vektor. Avrunda nedåt för vektorer av jämn längd.

Ni kan använda följande signatur.

void swapMiddleLast(int vectorLength,int vector[]);

Använd följande kod för att testa.

#include <stdio.h>

/*TODO funktion*/

int main(int argc,char**argv)
{
    int seq[5]={1,2,3,4,5};
    /* skriver ut vektorn */
    printf("[%d %d %d %d %d]\n"
            ,seq[0],seq[1],seq[2],seq[3],seq[4]);

    /*TODO*/

    /* skriver ut vektorn */
    printf("[%d %d %d %d %d]\n"
            ,seq[0],seq[1],seq[2],seq[3],seq[4]);

    return 0;
}

1.5.4 Hitta största och minsta talet i en sekvens

Skriv två funktioner, en som hittar största talet i en sekvens och en som hittar det minsta.

Skriv ett program som testar era två funktioner med listor av varierande längd.

1.6 Utskrifter

Att skriva ut saker i ett program är mycket vanligt förekommande. I C så görs det lämpligtvis med printf, sprintf eller fprintf beroende på vilken typ av utskrift man vill göra. printf, sprintf och fprintf använder sig alla av samma typ av formatsträngar, strängar som talar om hur utdatan ska formateras.

Hur formatsträngar fungerar kollar ni lämpligtvis upp i er kursbok¹ eller genom att skriva man 3 printf i en terminal.

1.6.1 Utskrifter av heltal och flyttal

Skriv kod som skriver ut alla heltals- och flyttalsvariabler i programmet nedan.

#include <stdio.h>

int main(int argc,char**argv)
{
    int a=1,b=1,c=2,d=3,e=5;
    double d0=2,d1=1.4142,d2=1.1892,d3=1.0905;

    return 0;
}

1.6.2 Utskrifter av felmeddelanden

Skriv ett program som tar 2 kommandoradsparametrar och skriver ut ett felmeddelande om parametrarna är fler eller färre. Använd fprintf och skriv till stderr.

Att tänka på är att listan med argument har programnamnet som första element följt av parametrarna.

1.6.3 Begränsa stränglängd

Något som kan vara mycket användbart när man skriver ut strängar, till exempel för att man skriver till något som har begränsad kapacitet att lagra tecken, är att begränsa längden på de strängar man skriver ut.

Detta kan göras med en formatsträng på formen %.xs där x är ett tal som anger hur många tecken som ska skrivas ut.

Skriv ett program som skriver de 15 första tecknen av en sträng, som kommer in som parameter till programmet, till en annan sträng, som används som buffer (använd sprintf).

Fyll i följande kod.

#include <stdio.h>

int main(int argc,char**argv)
{
    if(argc==2){
        char buffer[15+1];/*plats för 15 tecken och nullterminatorn*/
        printf("%s\n",argv[1]);/*visar strängen som ni ska skriva
                                            ut början av*/

        /*TODO*/

        printf("%s\n",buffer);/*visar er sträng, ska vara 15 tecken lång*/
    }else{
        fprintf(stderr,"Fel antal program argument");
        return 1;
    }
    return 0;
}

Om ni gjort rätt ska följande argument ge följande utdata om er körbara fil heter main.

./main abcdefghijklmnopqrstuvwxyz abcdefghijklmno

1.7 Loopar

Som ni kanske noterade i avsnittet om sekvenser blir det snabbt krångligt att arbeta på sekvenser av data om man måste referera till data med konstanter eller liknande. För att lösa det och andra problem finns loopar som kan köra samma kod om och om igen tills något villkor inte längre är uppfyllt.

Loopar är centrala i imperativa programmeringsspråk som C, inte minst för operationer på sekvenser av olika slag.

1.7.1 Funktionen summa

Skriv en funktion som tar en vektor med flyttal och returnerar summan av talen. Funktionens signatur bör ta vektorn och vektorns längd som parametrar och returera en double.

Skriv er funktion så att följande fragment skriver ut 10.0

double arr[5]={3.0,2.5,2.5,2.5,-0.5};
double s=sum(5,arr);
printf("%lf\n",s);

1.7.2 Lägga till i en NULL-terminerad buffer

Strängar i C är sekvenser med tecken avslutade med ett NULL-tecken.

Skriv en funktion som givet ett tecken lägger till det sist i en annan sträng, se till att den strängen ni lägger till i fortfarande är NULL-terminerad när er funktion kört klart.

Ni ska använda följande signatur.

void appendChar(char buffer[],char charachter);

Följande kod ska ge utdatan nedan.

#include <stdio.h>
#include <memory.h>

int main(int argc,char**argv)
{
    char string[]="test";/*längd 4*/
    char buffer[6];
    int i;

    memset(buffer,'A',6);
    buffer[0]=0;

    for(i=0;i<4;i++){
        appendChar(buffer,string[i]);
        printf("%s\n",buffer);
    }

    return 0;
}

t te tes test

1.7.3 Skriv ut alla kommandoradsargument

Skriv ett program som skriver ut alla kommandoradsparametrar.

Om programmet heter main och anropas som följer ska nedanstående skrivas ut.

./main jag testar programmet jag testar programmet

1.7.4 Multiplicera matriser

Något som är mycket vanligt i ett flertal avancerade algoritmer är multiplikation av matriser.

Matriser är 2-dimensionella vektorer, eller vektorer av vektorer, beroende på hur man ser på saken. När man ska multiplicera matriser är det praktiskt att se på dem som vektorer av vektorer som man sedan tar skalärprodukter av.

Definition av skalärprodukt

a⋅b = a₁*b₁ + a₂*b₂ + ... + a_n*b_n

Kan beskrivas i ord som, givet två lika långa vektorer multiplicera alla element i ena vektorn med det element i andra vektorn som har samma index. Summera sen de resulterande värdena.

Matrismultiplikation kan då beskrivas i termer av skalärprodukt som

A_{m, n} är en matris med m rader och n kolumner

B_{n, p} är en matris med n rader och p kolumner

C = AB matrismultiplikation A multiplicerat med B resulterar i en ny matris C

C_{m, p} är den resulterande matrisen, den har m rader och p kolumner

c_{i, j} är ett element i C på rad i och kolumn j

a_i,: är vektorn som utgör rad i i A

b_{:, j} är vektorn som utgör kolumn j i B

c_{i, j} = a_i,:⋅b_{:, j}

Kan beskrivas i ord som -- ta varje rad i A, för varje element på den raden i C ta kolumnen i B med samma index som elementet och räkna ut skalärprodukt för raden i A och kolumnen i B, det resulterande värdet är elementets värde i C.

Notera att AB≠BA.

Fyll i kod i programmet nedan som multiplicerar matriserna A och B till en ny matris C. Skriv koden med loopar så att om man ändrar storlek på A eller B kommer koden fortfarande att fungera (givet att man uppdaterar storleken på C).

#include <stdio.h>

int main(int argc,char**argv){
    double A[3][2],B[2][4];

    A[0][0]=1;A[0][1]=0;
    A[1][0]=0;A[1][1]=1;
    A[2][0]=1;A[2][1]=0;

    B[0][0]=1.0;B[0][1]=2.0;B[0][2]=3.0;B[0][3]=4.0;
    B[1][0]=0.5;B[1][1]=0.2;B[1][2]=0.1;B[1][3]=0.0;

    /*TODO define and calculate C*/
    {
        int i;
        for(i=0;i<3;i++){
            int j;
            for(j=0;j<4;j++)
                printf("\t%lf",C[i][j]);
            printf("\n");
        }
    }
    return 0;
}

Korrekt resultat på ovanstående beräkning är att programmet skriver ut

1.000000 2.000000 3.000000 4.000000 0.500000 0.200000 0.100000 0.000000 1.000000 2.000000 3.000000 4.000000

1.8 Typkonvertering och felhantering

Som ni kanske noterat tar program i C in sina kommandoradsparametrar som strängar oavsett om du som programmerare förväntar dig tal eller inte (ett nödvändigt ont).

I den situationen men även andra är det bra att kunna ändra representation från en typ till en annan, oftast bestående i att konvertera text till någon sorts binär representation.

En nackdel med det är att om det man tror ska vara ett tal faktiskt inte är det så kommer ett fel att uppstå i programmet vilket behöver hanteras.

1.8.1 Konvertera sträng till heltal

För att konvertera en sträng till ett heltal kan sscanf användas vilket har gjorts i given kod i tidigare uppgifter.

sscanf (och scanf, fscanf) fungerar på liknande sätt som sprintf. Till skillnad från sprintf används formatsträngen dock för att berätta vilket format vi vill konvertera till, vilket måste matcha typen på variabeln vi försöker lagra datan i.

Exempel på sscanf

int n;
sscanf("%d",&n);

Notera &-symbolen före n. Det är adressen-av operatorn men ni behöver för dessa uppgifter bara veta att den måste vara där för att det ska fungera.

Skriv ett program som konverterar sina kommandoradsparametrar till heltal och summerar dem.

1.8.2 Konvertera sträng till flyttal

Som i uppgiften ovan fast konvertera till flyttal i stället för heltal.

1.8.3 Misslyckade konverteringar

I fallet där datan man försöker konvertera inte kan omvandlas till den typ man vill omvandla till har ett fel uppstått. I C indikeras fel ofta av vilka värden en funktion returnerar, i sscanf's fall retureras antalet argument som fått ett värde tilldelat.

Det betyder att om man försökte konvertera ett värde med sscanf bör man kolla så att returvärdet är 1. Om returvärdet inte är 1 bör man hantera felet genom att antingen köra kod som inte behöver just det värdet (kanske var det en frivillig parameter) eller på något sätt indikera felet, till exempel med en egen returkod och eller felmedelande till stderr.

Utöka ert flyttalskonverteringsprogram ovan till att skriva ut att konverteringen misslyckades för de parametrar som inte är flyttal.

Exempelvis som i följande körning

./main 1 3 -4.0 foo -5 1.0 3.0 -4.0 Icke ett flyttal -5.0

1.9 Stränghantering

Som nämnts i tidigare avsnitt är strängar vektorer av tecken som avslutas med ett NULL-tecken. Det finns i C ett antal färdiga funktioner som hjälper oss att hantera strängar. Dessa kan inkluderas med #include <string.h> det är viktigt att notera att de ENDAST fungerar när strängarna är korrekt NULL-terminerade. Om era strängar inte är det måste ni använda andra funktioner.

1.9.1 Längden av strängar

För att ta reda på en strängs längd kan funktionen strlen användas.

Använd strlen för att skriva en funktion som skriver ut varje tecken i en sträng på en egen rad. Anropa sedan den funktionen med alla kommandoradsparametrar.

Exempel på en körning:

./main test kod t e s t k o d

1.9.2 Kopiera strängar

För att kopiera strängar kan funktionen strcpy användas.

Den kopierar alla tecken från en sträng till en buffer som programmeraren ansvarar för är tillräckligt stor. Tecknen läggs till i början på buffern och en NULL-terminator skrivs då alla tecken kopierats.

Skriv ett program som kopierar sin första och enda parameter till en buffer och sen använder en loop för att ersätta alla mellanslag med bindesträck. I slutet av programmet ska den gamla och nya strängen skrivas ut.

Var noggranna med att se till att buffern har plats för tecknen innan ni kopierar.

Exempel på en körning (ni kan välja annat format på utdata om ni önskar, -> är bara ett förslag):

./main "text med mellanslag" text med mellanslag -> text-med-mellanslag

1.9.3 Konkatenera strängar

Att konkatenera eller slå ihop strängar kan vara användbart i många fall. I C kan man använda funktionen strcat för att lägga en sträng i slutet på en annan.

Den nya strängens första tecken ersätter NULL-terminatorn i den förra strängen och strcat skriver en ny NULL-terminator då alla tecken kopierats.

Skriv om programmet i förra uppgiften till att lägga ihop alla in-parametrar, separerade med mellanslag, till en sträng och sen ersätta mellanslag med bindestreck som i förra uppgiften.

Var noggranna med att alltid ha en NULL-terminator i både strängen ni skriver till och i den ni lägger till.

Exempel på en körning

./main text med mellanslag text med mellanslag -> text-med-mellanslag

1.9.4 Jämföra strängar

För att jämföra strängar kan man inte använda de vanliga == och != operatorerna som man kan använda för tal. Det har att göra med att strängar är vektorer och samma sak gäller för vektorer av andra typer än tecken. C tillhandahåller en funktion strcmp som man kan använda för att testa hur mycket två strängar skiljer sig åt. Om strcmp returnerar 0 är strängarna lika.

Skriv ett program som kollar hur många kommandoradsparametrar som är lika som den första kommandoradsparametern.

Exempel på körningar

./main foo bar baz 0

./main 5 1 2 3 4 5 6 1

./main 1 1 1 0 1 0 1 4

./main alice - bob alice joseph alice joseph bob alice 3

1.10 Krångligare If-satser

Många gånger är villkoren i if-satser enkla men i vissa fall är de mer komplexa, det kan vara bra att ha god koll på hur sammansatta uttryck i if-satser fungerar inte minst då man kan behöva förstå dem när man läser andras kod.

Ofta kan if-satser göras tydligare genom att beräkna deluttryck med hjälpfunktioner.

1.10.1 Om ett tal är i ett intervall, givet som strängar

Skriv ett program som tar 3 parametrar och kollar om den första ligger mellan de två andra.

Ledning: skriv en funktion som testar om ett tal är ett flyttal och använd atof för att göra om strängar du vet är flyttal till flyttal.

Använd endast en if-sats.

1.10.2 Om den längsta strängen är kortare än ett tal

Skriv ett program som kollar om någon av dess två parametrar är längre än 10 tecken.

Ledning: skriv en funktion maxString som returnerar längsta strängen.

Använd endast 1 if-sats i main/

1.10.3 Om ett tal under hundra är ett primtal

Skriv ett program som testar om ett tal under 100 är ett primtal.

Ett tal är inte ett primtal om något primtal under roten av talet delar talet.

Ledning: för att kolla om ett tal delar ett annat, använd n%x==0

Alla primtal under roten av 100 är 2 3 5 7.

Använd endast 1 if-sats.

1.11 Kommandoradsargumenthantering

Kommandoradsparametrar, som också användts flitigt i tidigare exempel, är väldigt användbara när man skriver program. Tidigare har bara ett fixt antal parametrar använts och alla har använts på samma sätt. Uppgifterna här behandlar sätt att använda parametrar olika och att tillåta ett variabelt antal parameterantal.

1.11.1 Läs in parametrar med känd ordning

Skriv en funktion som tar 3 parametrar: namn, deltagar-nummer och tid, där namn är en sträng, deltagar-nummer ett heltal och tid ett flyttal. I en verklig applikation skulle detta kanske sparas i en databas över tävlingsresultat eller liknande, men ni ska skriva ut informationen på skärmen med följande format:

Tävlande: Mary Jones, 77, tid: 14.47

1.11.2 Läs in flaggor som kan saknas

Skriv ett program som tar 5 frivilliga parametrar

-a eller --adam
-b eller --bertil
-c eller --ceasar
-d eller --david
-e eller --erik

Om antingen kortformen (med ett sträck) eller den längre formen finns räknas det som attflaggan är aktiv.

Observera att flaggorna kan komma i godtycklig ordning.

Använd följande kod för att testa er lösning.

#include <stdio.h>

/*eventuella egna funktioner här*/

int main(int argc,char**argv)
{
    /*sätt dessa till icke noll om respektive flagga finns på komandoraden*/
    int a=0,b=0,c=0,d=0,e=0;

    /*TODO er kod här, att använda funktioner kan vara smart*/

    printf("Adam: %s\n",a?"true":"false");
    printf("Bertil: %s\n",b?"true":"false");
    printf("Ceasar: %s\n",c?"true":"false");
    printf("David: %s\n",d?"true":"false");
    printf("Erik: %s\n",e?"true":"false");
    return 0;
}

1.11.3 Läs in flaggor med parametrar

Ibland vill man inte bara veta att en flagga är aktiv utan man vill, om den är aktiv, ha reda på ett värde den ska använda.

Skriv ett program som har tre flaggor en -v eller --verbose som inte tar några parametrar, en --length som tar en heltalsparameter och en -- som tar alla strängar efter sig på kommandoraden som parametrar.

Om verbose är satt ska antalet kommandoradsparametrar efter -- skrivas ut. Oavsett flaggor ska alla parametrar efter -- skrivas ut.

Om --length är satt ska antalet tecken som används för att skriva ut parametrar efter -- begränsas till värdet av --length.

Ledning: för att begränsa antalet tecken som skrivs ut bör först alla parametrar efter -- skrivas till en gemensam sträng. Sen bör en formatsträng skapas som om --length är satt ska innehålla en maxlängd (se 1.6.3), detta kan göras med sprintf till en buffer.

Anropa sedan printf med något liknande detta.

char parameterbuffer[65536];
char formatbuffer[256];

/*TODO fyll buffrarna enligt ovan*/

printf(formatbuffer,parameterbuffer);

1.12 Datastrukturer

C har begränsningen att man bara kan returera ett värde från en funktion, snarare än flera. Det kan tyckas vara en stor begränsning, men i praktiken kan den arbetas runt genom att definiera nya typer som slår samman flera värden eller vektorer av värden till ett värde. Den typen av struktur skrivs i C med syntaxen

typedef struct Namn{
    int en_variabel;
    double en_annan_variabel;
}Namn;

Detta skapar en ny typ, Namn, som byggs upp av två variabler (man kan ha godtyckligt antal variabler i en struct).

Exempel på användande:

#include <stdio.h>

typedef struct Pair{
    int a;
    int b;
}Pair;

Pair packPair(int c,int d)
{
    Pair p;
    p.a=c;
    p.b=d;
    return p;
}

int main(int argc,char**argv)
{
    Pair test=packPair(3,7);
    printf("%d %d\n",test.a,test.b);
    return 0;
}

1.12.1 Funktionen hitta intervall

Skriv en funktion som tar in en lista med heltal och returnerar intervallet de ligger i.

Använd en signatur på formen

/*definiera 'struct Interval' här*/

Interval interval(int vectorLength,int vektor[]);

Skriv ett kort program som sickar in en heltalsekvenser och testar att er funktion fungerar.

1.12.2 Beräkna medelvärde och standardavvikelse

Medelvärde och standardavvikelse är vanliga mått inom statistiken. Dessa kan uppskattas från mätvärden x₁, x₂,..., x_n med formlerna

$\displaystyle \bar{x}$ = $\displaystyle {\frac{{\displaystyle\sum_{i=1}^n{x_i}}}{{n}}}$

för medelvärdet och

σ = $\displaystyle \left\vert\vphantom{\sqrt{\frac{\displaystyle\sum_{i=1}^n{(x_i-\bar x)^2}}{n-1}}}\right.$ $\displaystyle \sqrt{{\frac{\displaystyle\sum_{i=1}^n{(x_i-\bar x)^2}}{n-1}}}$ $\displaystyle \left.\vphantom{\sqrt{\frac{\displaystyle\sum_{i=1}^n{(x_i-\bar x)^2}}{n-1}}}\right\vert$

för standardavvikelsen. Där $\bar{x}$ är medelvärdet och σ standardavvikelsen.

Skriv en funktion som beräknar medelvärdet och standardavvikelsen för en lista med flyttal. Skriv sen ett kort program för att testa funktionen.

1.12.3 Lösningen av en andragradsekvation

Skriv en funktion för att lösa en andragradsekvasion.

Den generella formen av en andragrads ekvation är

ax² + bx + c = 0

detta kan förkortas till

x² + px + q = 0, d $\displaystyle \ddot{{a}}$ r p = $\displaystyle {\frac{b}{a}}$ och q = $\displaystyle {\frac{c}{a}}$

vilket ger matematiska formeln för lösningen på formen

x = - $\displaystyle {\frac{p}{2}}$ ± $\displaystyle \sqrt{{\Bigl(\frac p 2\Bigr)^2-q}}$

Skriv en funktion med signaturen nedan där ni får inkoeffecienterna a, b och c.

Tips: börja med att skissa er lösning på papper så ni får formeln uttryckt i a, b och c.

Funktionen sqrt som beräknar kvadratroten finns färdig i math.h Om sqrt får in en negativ parameter returnerar den värdet NaN som ni kan tolka som att svaret inte är reellt (Ni behöver inte göra något för att detta ska funka)

typedef struct Roots{
    double root1;
    double root2;
}Roots;
Roots andragrads(double a,double b,double c);

1.13 Minnesallokering

Att alltid behöva bestämma storlek på vektorer i förväg kan vara mycket begränsande. För att slippa göra det har C funktionerna malloc, calloc, realloc och free.

malloc och calloc -- skapar vektorer med variabel storlek
realloc -- ändrar storlek på vektorer med variabel storlek
free -- tar bort vektorer med variabel storlek

Viktigt: när ni använder minnesallokering måste ni ta bort minnet med free när ni inte behöver det längre.

1.13.1 Vektorer med okänd längd

Skriv en funktion som returnerar en vektor med alla primtal under ett visst värde.

Använd signaturen nedan, en algoritm för att testa om tal är primtal hittar ni i uppgift 1.10.3

int* primtal(int maxnum);

1.13.2 Summera talen i två vektorer

Skriv en funktion som summerar n tal från två vektorer och returnerar en tredje vektor.

Exempel på användning:

int vec1[]={1,2,3,4,5};
int vec2[]={1,2,3,4};
int *vec3=vecSum(3,vec1,vec2);/*contains {2,4,6} */

2 Programstruktur

För att undvika fel är struktur viktigt när man programmerar. Detta innefattar saker som läslighet, att undvika upprepa sig och hur man letar efter fel metodiskt.

2.1 Indentering

Indentering är viktigt för läsbarheten och att skriva konsekvent indenterad kod minskar risken för dumma misstag som saknade måsvingar och liknande.

2.1.1 Slumpmässigt indenterat program

Fixa indentering och radmellanrum så att de är konsekventa i koden nedan.

#include <stdio.h>

int main(int argc,char**argv){
int bar=0;
        for(bar=1;bar<argc;bar++)
            printf("%s\n",argv[bar]);
            bar=0;
if(bar)
    return 0;
else return 1;
}

2.1.2 Tvetydigt indenterat program

Fixa indentering och radmellanrum så att de är konsekventa i koden nedan.

Notera att om man istället för att laga indenteringen la till måsvingar som gjorde uvarande indentering korrekt så ändras programmets betydelse.

#include <stdio.h>
#include <string.h>

int main(int argc,char**argv){

    if(argc==2)
        if(strcmp(argv[1],"test")==0)
            printf("ok\n");
    else
        printf("fel antal parametrar");
    return 0;
}

2.1.3 Ej indenterat program

Fixa indentering och radmellanrum så att de är konsekventa i koden nedan.

#include <stdio.h>

double circleArea(double d) { return d*d*3.1415; } /*program som anropas med en radie som parameter och skriver ut cirkelarean som den radien ger*/ int main(int argc,char**argv) { /* kontrollerar om antalet parametrar är korect om inte skrivs ett felmedelande ut */ if(argc==2) { double in; /* konverterar parametern till ett flyttal vid fel skrivs error medelande ut*/ if(sscanf(argv[1],"%lf",&in)==1) { /*anropar er funktion och skriver ut resultatet*/ printf("%lf\n",circleArea(in)); } else { fprintf(stderr,"Programparametern är inte en siffra\n"); return 2; } } else { fprintf(stderr,"Programmet kräver exakt 1 parameter\n"); return 1; } return 0; }

2.2 Felsökning

Även om man kan önska annorlunda så inträffar det mest hela tiden att program man skriver innehåller fel som man måste leta upp och fixa till. Ofta är felen relativt tydliga och uppstår varje gång ett program körs men ibland inträffar de bara ibland, det senare fallet är mycket svårare att hitta och fixa.

Ett enkelt men förvånansvärt enkelt verktyg för att hitta fel i program är att lägga in utskrifts rader mellan alla rader som det kan gå fel på där man skriver ut något så man vet vilken rad utskriften kommer från och värdet på de variabler som skulle kunna få felaktiga värden. Sen kan man leta igenom utskrifterna efter variabler som har konstiga värden och se vilken rad dom började bli konstiga på.

2.2.1 Oändlig loop

Undersök vad som är fel med programmet nedan, kommentarerna anger vad som är avsett att inträffa. Skriv sedan om programmet så att du fixar felet. I de fall tolkningar måste göras för att få ett fungerande program gör en rimlig tolkning och implementera den.

#include <stdio.h>

/*funktionen byter plats på första och andra elementet, tredje och fjärde elementet och så vidare
        med alla par av element, enstaka element som inte är med i ett par ignoreras*/
void swapPairs(int length,int pairs[]){
    int i;
    for(i=0;i!=length;i+=2){
        int tmp=pairs[i];
        pairs[i]=pairs[i+1];
        pairs[i+1]=tmp;
    }
}
int main(int argc,char**argv){
    int p[]={1,2,3,4,5};
    swapPairs(5,p);
    return 0;
}

2.2.2 Räknar fel

#include <stdio.h>

/*summerar alla tal i sekvencen*/
int sum(int length,int sequence[]){
    int i;
    int sum;
    for(i=1;i<length;i++){
        sum+=sequence[i];
    }
    return sum;
}
int main(int argc,char**argv){
    int s[]={10,9,8,7,6,5,4,3,2,1};
    printf("Will print the sum of numbers from 10 to 1, 55\n");
    printf("%d\n",sum(10,s));
    return 0;
}

2.2.3 Kommer inte in i if sats

#include <stdio.h>

/*skriver ut alla kommandoradsargument som är lika*/
int main(int argc,char**argv){
    int i,j;
    for(i=1;i<(argc-1);i++)
        for(j=i+1;j<argc;j++)
            if(argv[i]==argv[j])
                printf("Argument %d and %d is identical %s\n",i,j,argv[i]);
    return 0;
}

Anropa ovanstående med tex

./main 1 2 3 4 1 4 foo bar foo apa du är du

Koden ovan bör ge att 1, 4, foo och du är orden som är identiska.

2.3 Repetitions undvikande

En vanlig felkälla för vissa programmerare är att de kopierat kod till flera ställen i programmet, hittar ett fel i den koden och lagar felet i en eller några av kopiorna. En bra grundprincip när man programmerar är ``Upprepa dig inte'', om man lyckas fullt ut med den ansatsen får man dels mindre kod att skriva vilket gör koden enklare att skriva och läsa. Man kommer också undan problemet med att behöva fixa fel på flera ställen då samma fel bara finns på ett ställe och om man fixar det där så fixar man samtliga delar av programmet som använder den koden.

2.3.1 Gemensamma deluttryck

I koden nedan finns det en massa uttryck som upprepas, identifiera dem och skapa lokala variabler där du kan lagra deras värde en gång och använda det från och med då.

#include <stdio.h>

/*skriver ut alla kommandoradsargument som är lika*/
int main(int argc,char**argv){
    int vec[4][10];
    int sum=0;
    int i,j;
    for(i=0;i<4;i++)
        for(j=0;j<10;j++){
            vec[i][j]=i*j;
            if(vec[i][j]%2){
                vec[i][j]-=1;
            }
            sum+=vec[i][j];
        }
    return 0;
}

2.3.2 Upprepade loopar

I koden nedan finns det flera loopar över samma vektor, då ingen av looparna påverkar mer än det nuvarande elementet de behandlar kan ni kombinera dem till en gemensam loop.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(int argc,char**argv){
    int *alst=calloc(sizeof(int),argc-1);
    int i,sum=0;
    for(i=0;i<(argc-1);i++)
        sscanf(argv[i+1],"%d",&alst[i]);
    for(i=0;i<(argc-1);i++){
        char buf[10];//fler siffror än vad som krävs för att skriva 2 miljarder
        sprintf(buf,"%d",alst[i]);
        if(strcmp(argv[i+1],buf)){
            fprintf(stderr,"ERROR failed integer conversion\n");
            return -1;
        }
    }
    for(i=0;i<(argc-1);i++)
        sum+=alst[i];
    printf("%d\n",sum);
    return 0;
}

2.3.3 Möjlig funktion

I koden nedan finns det upprepad kod som kan brytas ut i en eller flera funktioner, identifiera och bryt kod så att det blir ett mer lättläsligt program.

%FIXME maybe better example and definatly test this code

#include <stdio.h>
#include <stdlib.h>

int main(int argc,char**argv){
    int *alst=calloc(sizeof(int),argc-1);
    int size=argc-1;
    int i;
    for(i=0;i<size;i++)
        sscanf(argv[i+1],"%d",&alst[i]);
    {
        double tmp=0;
        for(i=0;i<size;i++)
            tmp+=alst[i];
        for(i=0;i<size;i++)
            printf("%lf\t",alst[i]/tmp);

        printf("\n");
    }
    while(!feof(stdin)){
        size=0;
        alst=realloc(alst,size*sizeof(int));
        while(1==scanf("%d\n",&i)){
            alst=realloc(alst,(size+1)*sizeof(int));
            alst[size++]=i;
        }
        {
            double tmp=0;
            for(i=0;i<size;i++)
                tmp+=alst[i];
            for(i=0;i<size;i++)
                printf("%lf\t",alst[i]/tmp);

            printf("\n");
        }
    }
    free(alst);
    return 0;
}

3 Simulera fysik

Ett tillämpningsområde som vissa som läser denhär kursen kan komma att har är att skriva simuleringar av fysikaliska system. Fullskaliga fysikmotorer är komplexa och gås igenom på kurser på avancerad nivå, men enklare simuleringar kan kodas relativt enkelt.

För att få en grafisk representation av utdatat från följande uppgifter, spara den till en fil som heter in.dat, tex genom att omdirigera standard output, och kör följande gnuplot script.

set terminal postscript eps
set terminal postscript solid
set terminal postscript enhanced color
set data style linespoints

set output "out.eps"; plot "in.dat"

Gnuplot script kan köras genom att spara dem i en fil (här filen script) och köra

gnuplot script

i en terminal

Alltså för att visualisera utdatan från följande program, spara scriptet ovan i en fil script, kör ert program med (jag antar att programmet heter main)

./main > in.dat

Där in står för indata till scriptet, från ert program är det utdata. Se till att in.dat och script ligger i samma mapp och i den mappen kör

gnuplot script

Det gnuplot gör här är att rita ut streck mellan de x och y koordinater som ni skriver ut ur ert program. Utdatan finns i en fil som heter out.eps som ni kan öppna i något bildbehandlingsprogram, tex gv.

gv out.eps

Om ni lämnar en tom rad i gnuplots indata kommer den att avsluta strecket den håller på att rita och börja på ett nytt. Detta kan användas för att sätta flera kurvor i samma figur.

3.1 Konstant fart

Som ni kanske minns från gymnasiefysiken så håller ett objekt som inte utsätts för yttre krafter en konstant fart.

3.1.1 1D

I det enklaste fallet betraktar man ett fysikaliskt objekt som rör sig med konstant fart i en dimension.

Skriv ett program som simulerar ett objekt som rör sig längst x axeln med 3 m/s och börjar i origo.

Ni ska göra simuleringen i små steg, dvs räkna upp ert programs ide om tid med ett litet värde i den här uppgiften 0.01 sekunder, sen ska ni flytta ert objekt så långt som det skulle röra sig under dessa 0.01 sekunder. När ni sedan upprepar detta ett stort antal gånger blir resultatet att ni kan titta i er utdata och se var objektet är vi en viss tid.

Utdata ska vara på formen

#sekunder meter 0.00 0 0.01 0.03 0.02 0.06 0.03 0.09

och så vidare.

Kör simuleringen i en simulerad sekund.

3.1.2 2D

När man simulerar i 2 dimensioner behöver man hålla reda på både x och y koordinater men i övrigt liknar det 1 dimension ovan.

Gör en simulering likt i förra uppgiften med start position origo, och en hastighet i xled på 0.5 m/s och en hastighet i yled på 1 m/s.

Utdata ska var på formen x-koordinat y-koordinat

#x y 0 0 0.005 0.01 0.01 0.02 0.015 0.03

och så vidare.

Kör simuleringen i en simulerad sekund.

3.2 Fall i vakuum

En vanlig sak att simulera är saker som faller och för att vi inte ska behöva ta hänsyn till luftmotstånd antar vi här att vi faller i vakuum, det gör det naturligt att använda ett värde på gravitationsaccelerationen annat än det på jorden, så i följande tre uppgifter använder vi g_m = - 1.6 m/s² vilket är gravitationsaccelerationen på månen, minus betecknar att gravitationen är riktad nedåt mot månytan.

3.2.1 Start i vila över marken

Skriv ett program som simulerar ett objekt som accelererar mot marken med en hastighet av g_m = - 1.6 m/s², låt objektet börja på en höjd av 10m och starta i vila, avsluta simuleringen när objektet träffar marken.

För att simulera ett accelererande objekt behöver ni hålla reda på och uppdatera både position och hastighet. Detta kan göras på flera sätt men ett enkelt sätt som ger bra precision är att först uppdatera hastigheten och sen uppdatera positionen med den nya hastigheten.

Dvs för att räkna ut hastighet och position i nästa tidssteg använd

v(t + Δt)	= v(t) + a(t)Δt
r(t + Δt)	= r(t) + v(t + Δt)Δt

där v(t) betecknar hastigheten vid ett visst tidssteg v(t + Δt) betecknar hastigheten i nästa tidssteg. Samma ska för r(t) och a(t) etc fast för positioner och accelerationer. För er som är är obekanta med notationen Δt så är det alltså tiden mellan två tidssteg och t + Δt är alltså då nästa tidssteg då nuvarande tidssteg betecknas med t.

Notera att accelerationen a(t) = g_m i detta fall och här alltså är konstant.

3.2.2 Hopp från hög höjd

Skriv på samma sätt som ovan ett program som simulerar ett objekt i acceleration men nu har objektet även en hastighet i horisontell led. Startvillkoren är

g_m	= - 1.6 m/s²
v_x(0)	= 3m/s
v_y(0)	= 0m/s
r_x(0)	= 0
r_y(0)	= 10m

Där subscripten x och y betecknar horisontell och vertikal led respektive.

Återigen avsluta simuleringen när objektet slår i marken.

3.2.3 Projektilbana

Skriv en simulering likt den ovan fast med dessa start villkor

g_m	= - 1.6 m/s²
v_x(0)	= 10m/s
v_y(0)	= 10m/s
r_x(0)	= 0
r_y(0)	= 0m

se till att simuleringen faktiskt körs tills objektet återvänder till ytan och inte avslutas innan några tidssteg tagits.

3.3 Gravitation

Om man är längre ifrån objekt kan man inte längre betrakta gravitationsaccelerationen som ett uniformt nedåtriktat fält. Man måste ta hänsyn till objektets avstånd från kroppen som påverkar den med gravitation.

Den acceleration som en kropp orsakar på en annan på grund av gravitation (notera att den andra kroppen också får en acceleration vilket vi kommer att försumma i dessa uppgifter) kan skrivas som

g_k = $\displaystyle {\frac{{GM}}{{d^2}}}$

där

G	= 6.67*10^-11 Nm²/kg²
M	= massan på kroppen som påverkar objektet vi tittar på
d	= avståndet mellan objekten

Avståndet mellan två kroppar kan räknas ut genom att ta första kroppens x och y koordinat och subtrahera andra kroppens x och y koordinat från dem. De resulterande längderna kan tolkas som kateterna i en rätvinklig triangel där avståndet mellan kropparna är triangelns hypotenusa. Här kan pytagoras sats användas för att räkna ut hypotenusans längd.

d = $\displaystyle \sqrt{{\Delta x^2+\Delta y^2}}$

3.3.1 Liten sattelit

Skriv kod som simulerar en liten satellit som kretsar kring en planet, planeten har en massa på 10²⁶ kg satelliten rör sig med en hastighet av 10⁵ m/s parallellt med planetens yta på ett avstånd av 8.1670*10⁵ m. Använd lämpligt tidssteg och antal iterationer på tex 1 s och 150 iterationer.

Skriv ut satellitens koordinater i kilometer på formen x y

Exempel

816.7 0

Tips försäkra er om att gravitationsaccelerationen ni räknar med alltid är mot er planets centrum dvs origo.

3.3.2 Binärstjärnor

Skriv kod som simulerar två stjärnor som ligger i omloppsbana runt varandra. Stjärnorna ska vara lika tunga och ha en massa på 10²⁷ kg, de ska initialt ligga 8.1670*10⁵ m från origo på varsin sida, de börjar båda på x-axeln. Den initiala hastigheten ska vara 1.82*10⁵ m/s längst y-axeln för stjärnan som ligger högst på x axeln och -1.82*10⁵ m/s längst y-axeln för den andra stjärnan.

Skriv ut först alla resultat från första stjärnan följt av en blankrad och sen alla resultat av den andra stjärnan. Följ formatet för utskrift i förra uppgiften.

Kör simuleringarna i 1000 steg, om ni gjort rätt ska två relativt cirkulära banor visas.

Siffrorna ovan är inte realistiska utan valda för att ge enklare simuleringar.

Tips se till så att alla uppdateringar av positioner sker efter att gravitationen på båda kropparna räknats fram, så att inte den andra stjärnans acceleration räknas ut med den NYA positionen på den första stjärnan.

4 Ytterligare programmeringskoncept

Uppgifter som går igenom koncept i C och programmering som kan ses som något mer avancerade.

4.1 Interaktiv input

Även om det oftast är bäst att ta all indata till programmet som kommandoradsparametrar finns det fall där det kan vara lämpligt med en mer interaktiv input. För att möjliggöra detta kan man läsa tecken som användaren skriver i terminalen programmet körs under programmets körtid.

För att lösa från standard input i C, som om inget annat sägs är användarens terminal används funktionen scanf.

Precis som i fallet där man läser indata från kommandoradsparametrar är det väldigt viktigt att man kontrollerar att indata användaren skriver in är på det format man förväntar sig. Om man inte gör det kan man introducera svårhittade fel i programet.

4.1.1 Program som läser tal och strängar

Skriv ett program som läser in tal och strängar från kommandoraden. Programmet ska läsa in ett tecken (antingen s,d eller f) och sen beroende på vad det tecknet är läsa in en sträng (om tecknet är s), ett heltal (om tecknet är d) eller ett decimaltal (om tecknet är f).

Programmet ska skriva ut vad de läst in efter varje ny indatarad. Använd typerna int, double och char* för de olika typerna av indata.

Exempel på körning av färdigt program

./main d 50 50 f 7.33 7.33 s en apa var det en apa var det

4.1.2 Program som frågar användaren efter en godtyckligt lång sekvens

Skriv ett program som frågar användaren efter en godtyckligt lång sekvens av heltal, se till att ni kan allokera mer minne till sekvensen om den visar sig bli lång.

Låt varje tal komma på sin egen rad och skriv i slutet av programmet ut hur många tal det var och summan av dem.

4.1.3 Enkelt meny system

En variant på interaktiv input är enkla textbaserade meny system. Dessa kan skapas genom att skriva ut en text med vad man frågar efter och vilka alternativ man kan välja (och vad man skriver för att välja dem).

Implementera menysystemet som beskrivs nedan, använd en array för att lagra strängarna (sätt maxstorlek till något lämpligt tal säg 10 då de är lika med antalet siffror).

Huvudmeny

Vill du ta bort eller lägga till anteckningar?
1. Lägg till
2. Ta bort
3. Avsluta (alla anteckningar går förlorade)

Lägg till meny

Ange en siffra med anteckningsnummer du vill ge ett värde

Skriv in anteckning

Skriv in din anteckning

Ta bort meny

Ange en siffra med anteckningsnummer du vill ta bort

4.2 Pekare

En pekare är en variabel som lagrar minnesadressen av en annan variabel, det kan utnyttjas för att skriva funktioner som kan använda olika variabler beroende på vilken adress man sickar dem.

4.2.1 Funktionen swap

Skriv en funktioner som byter plats för två värden, dvs skriv funktionerna swapInt, swapDouble och swapChar.

Funktionerna ska ta två pekare och byta plats på vad de pekar på.

Exempel

double a=5,b=10;
swapDouble(&a,&b);
printf("%lf %lf\n",a,b);/*skriver ut 10 5*/

4.2.2 Pekare in i vektorer

Skriv en funktion som tar två pekare in i en vektor och skriver ut alla element i från den första pekaren till den sista pekaren.

Använd följande signatur

void printIntRange(int *p1,int *p2);

Använd följande kod för att testa er lösning

#include <stdio.h>

int main(int argc,char**argvs){
    int range[]={0,1,2,3,4,5,6,7,8,9};
    printIntRange(&range[0],&range[2]);/*prints 0 1 2 */
    printIntRange(&range[2],&range[5]);/*prints 2 3 4 5 */
    printIntRange(&range[8],&range[9]);/*prints 8 9 */
    printIntRange(&range[9],&range[4]);/*prints 9 8 7 6 4 */
    printIntRange(&range[2],&range[0]);/*prints 2 1 0 */
    return 0;
}

4.2.3 Datastrukturen Slice

Skriv en datastruktur som innehåller en pekare till var i en vektor en delvektor börjar och längden på delvektorn. Datastrukturen ska heta IntSlice och ha två fält start och length. Implementera en funktion sortIntSlice som sorterar en IntSlice i nummer ordning med minst först.

En algoritm ni kan använda för sortering är quicksort, för att göra det välj ett element i delvektorn och placera alla element som är mindre än de elementet i en delvektor före element och resterande element i en delvektor efter elementet. Anropa detta rekursivt på de nya delvektorerna.

4.3 Rekursion

Ett sätt man ofta kan se rukursion definieras som är "se rekursion", och det är en relativt träffande beskrivning. Rekursion är när vi använder en definition i själva definitionen, i vårt fall genom att låta funktioner anropa sig själva.

4.3.1 Fakultetsfunktionen

Skriv en funktion för att implementera fakultetsfunktionen x! med en rekursiv algorithm.

Några exempel på fakultetsfunktionen

0!	= 1
1!	= 1
2!	= 1*2
3!	= 123
4!	= 123*4
5!	= 12345

dvs den matematiska funktionen

0!	= 1
n!	= (n - 1)!*n där n är ett positivt heltal

och så vidare

Skriv ett program där ni testar er funktion.

4.3.2 Minsta talet i en sekvens

Skriv en funktion mins som returnerar det minsta talet i en sekvens, gör din lösning rekursiv och dela i varje anrop upp sekvensen i två delsekvenser och hantera dem rekursivt.

Använd följande signatur

double mins(double *start,double *end);

Identifiera ett lämpligt basfall och det rekursiva fallet och implementera sen funktionen. Skriv ett program som demonstrerar funktionen.

Jämför funktionen med den iterativa lösningen i uppgift 1.5.4, reflektera över respektive lösnings fördelar och nackdelar.

4.3.3 Matcha parenteser

Skriv en funktion som matchar parenteser, den ska när den hittat slutparentesen skriva ut allt mellan start och slut parentesen på en egen rad. Funktionen ska vara rekursiv.

Exemplet på körning av program som använder funktionen

./main "(en lite text (plus en kommentar) som handlar om uttryck (x*(y*y)) är ett uttryck)" (plus en komentar) (y*y) (x*(y*y)) (en lite text (plus en kommentar) som handlar om uttryck (x*(y*y)) är ett uttryck)

Tips gör ett nytt rekursivt anrop så fort ni hittar en ny start parentes.

4.3.4 Beräkna polynom

Skriv en funktion som räknar ut värdet av polynom med korrekta prioriterings regler. Dvs räkna ut parenteser först, sen multiplikation/division och sist addition och subtraktion.

Modifiera er kod ovan för att hitta parenteser, skriv en annan funktion som räknar ut multiplikation/division och en tredje som räknar ut addition, låt funktionerna anropa varandra för att lösa de delproblem som den aktuella funktionen inte kan hantera.

4.3.5 Binärsökning i sekvens

Givet en sorterad i stigande ordning sekvens av nummer ta reda på om ett specifikt nummer finns i sekvensen, gör detta genom dela upp sekvensen i två delar likt i 4.3.2 och se sen vilken av delarna som innehåller bara för stora eller för små tal. Anropa denna funktion rekursivt med den andra delen tills du identifierat talet du letade efter.

4.4 Listor

Listor är en vanlig datastruktur som används mycket inom programmering. En lista har till skillnad från en array ingen övre gräns på hur stor den kan bli men är å andra sidan långsammare att söka i.

4.4.1 Enkellänkad list

Skriv en enkellänkad list med följande metoder

IntList* new_IntList();
void delete_IntList(IntList*);
void IntList_add(IntList*,int);
int IntList_take(IntList*);

Add och take lägger till och tar bort i början av listan.

4.4.2 Listiteratorer

Utöka er lista i förra uppgiften så att man kan loopa eller rekursera över listan. Lägg till följande funktioner.

IntListIterator* IntList_iterator(IntList*);

där IntListIterator har följande metoder och iterator metoden returnerar en iterator som refererar början av listan

void IntListIterator_next(IntListIterator*);
int IntListIterator_end(IntListIterator*);
int IntListIterator_read(IntListIterator*);
void IntListIterator_write(IntListIterator*,int);

Där next flyttar iteratorn att peka på nästa element, end returnerar icke noll om vi står i slutet av listan och read och write läser respektive skriver till nuvarande position i listan.

4.4.3 Funktionenerna remove och insert

Utöka era iteratorer med metoder för att lägga till ett element efter det nuvarande elementet och för att ta bort det nuvarande elementet. om det nuvarande elementet tas bort blir iteratorn ogiltig. Kalla funktionerna IntListIterator_remove och IntListIterator_insert.

4.5 Träd och rekursion över dem

Om man förstått listor är steget inte så långt till att förstå en annan vanlig datastruktur kallad träd. Ett träd består av en rootnod (eller är möjligtvis tomt) som i sin tur har ett antal noder den pekar på kallat barn. Om man vill referera ett barn och alla dess eventuella barn rekursivt kan termen gren användas.

Ett exempel på när träd används i datorvärden är filsystemet med kataloger och filer, där finns en root map, i unix kallad / eller som i windows en root mapp per enhet vid namn C: etc. Kataloger utgör grenar i filsystemsträdet och deras barn är antingen andra kataloger eller filer.

4.5.1 Binärt träd

Ett binärt träd är ett träd som har max två barn per nod (definition från wikipedia). Givet datastrukturen nedan skriv en funktion insertSortInt som givet en nodpekare och en int sätter in int'en i trädet så att det är sorterat enligt, alla element under node left är mindre än elementet i noden, alla element som är större än elementet i noden finns under noden right vid insättning av element som redan finns i trädet gör inget. Pekare som inte pekar på en nod ska peka på null.

typedef struct BinaryIntNode{
    int element;
    BinaryIntNode *left;
    BinaryIntNode *right;
}BinaryIntNode;

Skriv ett program som sorterar en mängd heltal och sen besöker dem rekursivt i ordning och skriver ut dem.

5 Filhantering

En mycket vanlig sak för ett program att göra är att hantera filer av olika slag, det kan vara text filer som antingen förväntas läsas av människor eller datorer, bilder databaser. Ja listan blir lång.

5.1 Textfiler

Något som är mycket vanligt för datorprogram att hantera är filer som innehåller text i något encoding format. Rena text filer (inte formaterade text filer som word-dokument) har fördelen att de är relativt lätta att läsa för både datorer och människor.

5.1.1 Läs in 1000 första tecknen ur en textfil

Skriv ett program som öppnar en text fil och läser de 1000 första tecknen till en buffer. Om det inte finns 1000 tecken i filen läs så många som det finns. Skriv ut tecknen till skärmen för att kontrollera att ni gjort rätt.

5.1.2 Läs in en godtyckligt lång textfil

Sättet att läsa in ovan till en buffer av fix storlek fungerar bra om man har någon sorts ide om hur mycket av innehållet i en fil man är intresserad i. Om man däremot vill läsa in säg hela filen men inte vet hur stor den är så får man ta till andra metoder.

Skriv ett program som läser in en hel textfil till en buffer, om buffern visar sig vara för liten reallokera den tills all information får plats.

Tips, varje gång ni upptäcker att buffern är för liten dubbla dess storlek, realloc kan vara bra för det. För att ni enkelt ska kunna testa börja med en bufferstorlek på säg 100 byte, skriv sen ut varje gång ni ökar bufferns storlek och till hur mycket. Avsluta med att skriva ut den inlästa texten.

5.1.3 Skriv data till en textfil

Skriv ett program som skriver ner multiplikations tabellen för alla tal upp till ett givet tal. Den första kommandoradsparametern är filnamnet att skriva resultatet till och den andra är det givna talet.

5.1.4 Ersätta åäö

Skriv ett program som läser in en fil, ersätter alla å med å ä med ä och ö med ö om är det versaler ni ersätter ska det a eller o som finns i det ni ersätter med också vara stort.

Anledningen att man vill ersätta med just dessa sekvenser är att webbläsare kan visa dem som åäö oavsett vilken encoding man har filen i, detta är användbart tex om man har svenska namn i ett i övrigt engelskt dokument.

Ta två komandoradsparametrar, den första filnamnet på infilen och den andra filnamnet på utfilen.

5.1.5 Expandera tabbar

Skriv ett program som gör om tab tecken \t till mellanslag. Tabbarna ska expanderas så att radlängden från början av raden till slutet av den expanderade tabben är jämt delbart med 8.

Programmet ska ta två filnamn på kommandoraden och läsa från den första filen och skriva till den andra.

5.2 Formaterad data i textfiler

För att det ska vara lättare för datorer att hantera data i text filer har text filer ofta ett bestämt format som de följer och med det följer någon sorts underförstådd ide om vad datat som följer formatet betyder.

5.2.1 Topplista

Skriv ett program som tar tre kommandoradsparametrar, ett filnamn, ett personnamn och en siffra. Skriv personnamnet och siffran till filen efter eventuellt tidigare innehåll. Läs från filen den största siffran och personnamnet som hör till denna och skriv ut dessa.

Tips lagra varje par av siffra och namn radvis med siffran först och se till att det enda efter siffran är personnamnet.

5.2.2 Ini-parser

Ett vanligt format för enkla konfigurations filer är ini formatet. Iden med formatet är att ge värden till namngivna inställningar.

Skriv en parser för det subset av ini formatet som beskrivs nedan, er parser ska hitta alla inställningar samt deras värden och lagra dem i någon datastruktur. Läs sedan från standard in och skriv ut värdet på de inställningar som användaren matar in.

Beskrivning av subset av ini-formatet

Varje inställningsnamn, värde par står på en egen rad
Tomma rader är tillåtet
Inställningsnamn slutar vid först = tecknet
Mellanslag och TAB tecken i början och slutet av inställningsnamn och värdet ska ignoreras
Om flera inställningar heter samma använd det sista värdet

5.2.3 Skriv träd som xml

Skriv ett program som skriver ut trädet som generateNode skapar som xml, använd name som tagnamn och låt nodens barn och data vara nodens innehåll.

Xml är ett format för data som sparar data som en träd struktur. Det består av start taggar på formen <tagnamn> som påbörjar en nod och sluttaggar på forment </tagnamn> som avslutar dem, taggar måste avslutas i omvänd ordning som dom påbörjades, dvs den senast öppnade tagen måste stängas först. Mellan en start och en slut tag kan det finnas ytterligare noder med sina egna start och slut taggar.

typedef struct Node{
    struct Node **childlist;
    int numberOfChildren;
    char* name;
    char* data;
}Node;
/*name must be non null and valid for the lifetime of the node, it is not changed
        by the node. data is copied by the node and may be null*/
Node* newNode(char *name,char *data){
    Node* n=calloc(1,sizeof(Node));
    if(!name){
        fprintf(stderr,"Error: name is null\n");
        return 0;
    }
    n->name=name;
    if(data){
        n->data=malloc(strlen(data)+1);
        strcpy(n->data,data);
    }
    return n;
}
void freeNode(Node* node){
    if(node){
        int i;
        for(i=0;i<node->numberOfChildren;i++)
            freeNode(node->childlist[i]);
        if(node->childlist)
            free(node->childlist);
        if(node->data)
            free(node->data);
        free(node);
    }
}
/*transfer ownership of child to parent*/
void addNode(Node* parent,Node* child){
    if(!(parent&&child)){
        fprintf(stderr,"Error: parent or child is null\n");
        return;
    }
    parent->childlist=realloc(parent->childlist,(parent->numberOfChildren+1)*sizeof(Node*));
    parent->childlist[parent->numberOfChildren]=child;
    parent->numberOfChildren++;
}
Node* generateNode(){
    Node* html=newNode("html",0);
    {
        Node* head=newNode("head",0);
        Node* title=newNode("title","generetedTitle");
        addNode(head,title);
        addNode(html,head);
    }
    {
        Node* body=newNode("html",0);
        Node* h=newNode("h1","A Random Header");
        Node* p1=newNode("p","first paragraph");
        Node* b=newNode("b"," some bold text");
        Node* p2=newNode("p","second paragraph");
        addNode(p1,b);
        addNode(body,h);
        addNode(body,p1);
        addNode(body,p2);
        addNode(html,body);
    }
    return html;
}

Kalla filen ni sparar till text.xhtml och testa öppna i en webläsare. Glöm inte bort att anropa freeNode på den nod ni får tillbaka från generateNode.

5.2.4 Txt till xhtml

Skriv ett program som konverterar en styckeindelad text fil till xhtml.

Ta filnamnet som ska läsas ifrån som första kommandoradsparameter om det finns en andra kommandoradsparameter är det namnet på utfilen annars ska utfilen heta samma sak som infilen fast med .xhtml tillagt i slutet, som infilen slutar med .txt ska .txt tas bort.

Sätt titeln i xhtml dokumentet till infilsnamnet (med eventuellt borttaget .txt), om första bokstaven i titeln är en bokstav ska den vara en versal.

Om ett stycke är bara en rad långt anta att det är en rubrik och skriv det inom <h3> tagar, andra stycken skrivs inom <p> tagar. Ett nytt stycke påbörjas varje gång en rad med bara mellanslag eller tabbar eller en tom rad påträffas.

Börja er fil med

<!DOCTYPE html PUBLIC  "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
	<head>
		<title>
			ER TITEL
		</title>
		<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"/>
	</head>
	<body>

Där ni ersätter titeln med er titel. Därefter skriv in era rubriker och stycken och avsluta sen med

	</body>
</html>

5.3 Platformsberoende binärfiler

Om man inte bekymrar sig om att filer ska gå att läsa på andra typer qav hårdvara, andra versioner av programmet eller kompilatorn så kan man på väldigt enkla sätt använda binärfiler för att spara undan information från en programkörning till en annan. Detta är inte att rekommendera för information man kan behöva dela med sig av eller inte får komma bort men är helt ok om man sparar undan data som kan användas för att snabba upp kommande körningar av samma program eller för att inte förlora all data i händelse av strömavbrott.

5.3.1 Skriv en struct till disk

Om ni har en struct eller vektor av structar som inte innehåller pekare kan den sparas till disk genom att öppna filen för binär skrivning och sedan anropa fwrite med en pekare till structen eller vektorn.

Om det är en vektor som skrivs kan det vara lämpligt att skriva en int i början som talar om hur många element vektorn har.

Skriv ett program som sparar vektorer av structar på följande format till disk och som kan läsa tillbaka dem när programmet startar nästa gång.

typedef struct Vector3D{/*mathematical vector*/
doubel x,y,z;
}Vector3D;

Lägg till ett sätt att bestämma vilka filer man ska läsa in från början, ett sätt att bestämma vilken fil man ska skriva till och ett sätt att lägga till element i vektorn.

5.3.2 Skriv lista till disk

Om man istället för en vektor har en lista med saker man vill skriva till disk så kan man inte anropa fwrite på samma sätt längre. Då listor innehåller pekare som refererar till minnesadresser som man förmodligen inte kommer att få samma som förra körningen så måste man översätta pekarna till någon form av egna id nummer innan man skriver datat till disk.

En variant är att man rekurserar till slutet av listan och skriver sista noden till filen, skriver den som den är och returerar 0 som sitt eget id nummer, elementet före den i listan ersätter värdet på sin pekare med det returnerade värdet skriver sig till filen och returnerar det returnerade värdet pluss 1.

Skriv ett program som sparar en lista till disk och läser tillbaka den likt vektorerna i förra uppgiften.

5.3.3 Skriv träd till disk

Då träd också innehåller pekare har de samma problem som listor när de ska skrivas till disk.

Ungefär samma algoritm som beskrevs ovan kan också användas för träd, den modifikation som behövs är att en parameter måste läggas till i den rekursiva funktionen som anger vilket nästa id-numret är så att inte olika grenar i trädet får dupplikat av id nummer.

På samma sätt som ovan skriv ett program som kan spara och läsa träd från disk.

5.4 Behandling av filer som strömmar

I tidigare uppgifter då vi läst in filer har vi tittat på fallet då vi läser in hela filen i minnet på en gång och därefter använder innehållet. Det finns inget som säger att man måste göra så, det är ofta en bra ide att läsa en rad eller annan mindre bit i taget (ibland enskilda tecken).

5.4.1 Implementera sökning

Skriv ett program som söker efter ett ord eller en fras i en fil, ordet eller frasen är första kommandoradsparametern och de följande är filnamn att söka igenom För alla rader som innehåller ordet skriv utdata till stdout på formatet

filnamn:radnummer + raden som matchade

ett exempel på utdata

./main se foo.txt bar.txt foo.txt:4 - Han du se haren? foo.txt:6 - Du förvånar mig, ser man på bar.txt:17 essential data inkludes

5.4.2 Implementera search and replace i filer

Skriv ett program som söker efter ett ord eller en fras likt ovan som i dethär fallet kan sträcka sig över flera rader om frasen innehåller nyradstecken. Den frasen ska ersättas med en annan fras given som andra parameter. Parameter 3 och 4 respektive är in och utdatafiler.

5.4.3 Implementera ordräkning

Skriv ett program som räknar hur ofta varje ord finns i en fil, ett ord här är en sekvens av bokstäver som inte är mellanslag, tab eller nyradstecken.

I slutet av programmet ska alla ord och hur många gånger de förekom skrivas ut.

Programmet ska ta ett filnamn som kommandoradsparameter.

5.5 Unifiering av andra strömmar och filer

Som ni kanske redan har noterat från dokumentation om komandon likt fprintf behandlas filer och standard in/ut på samma sätt i C.

Detta kan utnyttjas genom att skriva program som tar indata på antingen standard in eller en fil och på samma sätt för utdata och standard out.

5.5.1 Program som läser från fil eller standard in

Skriv ett program som tar bort tomma rader från en serie filer, filerna ska antingen vara filer som angetts på kommandoraden eller om filnamnet - angetts standard in. Om standard in anges med än 1 gång avsluta programmet med ett felmedelande till standard error. Alla inte tomma rader ska skrivas till standard out.

Låt filtreringen av varje kommandoradsargument ske av en funktion som tar en fil som enda argument.

5.5.2 Program som tar kommandon

Skriv ett enkelt miniräknar program (tips använd lösaren från 4.3.4) som tar komandon från en fil. Utdata ska skrivas till stdout och felmedelanden till stderr.

Det första kommandoradsargumentet är antingen - för stdin eller namnet på filen programmet ska läsa från. Om det finns ett till kommandoradsargument ska alla komandon skrivas till den filen så att de kan köras igen senare (genom att starta programmet med det filnamnet som första parameter).

6 Simulera Organismer

Ett användbart område för programmering kan vara att simulera förenklade organismer för att skapa en bild av olika aspekter av organismers livscykler eller de ekosystem de lever i. Dessa simuleringar kan göras godtyckligt komplexa från mycket enkla till system som tar många manår att utveckla.

Vi ska här titta på några enkla exempel.

6.1 Simulera varelser

I enkla system kan man titta på en ensam varelses intag och förbrukning av näring.

6.1.1 Varelse som hittar mat slumpmässigt

Ta ett flyttal mellan 0 och 1 som indata, det representerar sannolikheten att hitta mat i ett givet tidssteg.

Skriv ett program där ni har en varelse representerad med ett heltal som mäter hur mycket energi organismen har. Låt organismen börja med 10 i energi och i en loop dra ifrån 1 från varelsens energi i varje varv. I samma loop använd funktioner i standard biblioteket för att generera ett slumptal mellan 0 och 1 och om det är mindre än sannolikheten öka varelsens energi med 5. Kör loopen tills varelsens energi är 0 då varelsen dör.

Varje gång varelsen hittar mat, dvs ökar sin energi, skriv ut varelsens totala energi och vilket tidssteg det är. När varelsen dör skriv ut vilket tidssteg den dog.

6.1.2 Två varelser som slåss

Skriv ett program som har två varelser, båda representerade av ett tal för hälsa, ett tal för hur sannolika de är att undvika sin motståndare och ett som anger hur mycket skada de gör med sina bett/slag. Sätt dessa värden olika för de två varelserna och skriv en loop där båda försöker slå varandra varje tidssteg. När en varelse inte har hälsa kvar avbryt loopen och skriv ut vem som vann och efter hur många tidssteg.

6.1.3 Stora varelser äter små varelser

Skapa två typer av varelser, den lilla varelsen ska fungera som varelsen i uppgift 1 med tillägget att den om den får mer än 20 energi delar upp sig i två varelser med 10 energi var.

Den större typen hanterar energi på samma sätt som den första typen men när den hittar mat ta en slumpmässig liten varelse och ta dess energi som den mat varelsen hittade, sannolikheten att en lite varelse hittas är 0.001*antaletsmåvarelser.

Skapa ett system med 100 små varelser och 10 stora, kör systemet i 10000 tidssteg och plotta populationerna för de båda varelsetyperna mot tiden, använd gnuplot som beskrivs här 3.

6.1.4 Varelser på grid

Skapa ett rutnät på 100x100 celler, på rutnätet placera 100 små och 10 stora varelser likt ovan.

Låt det med en viss sannolikhet varje tidssteg, prova börja på 0.001, bildas en matbit på varje ruta.

Låt varelserna förflytta sig slumpmässigt på rutnätet, om en varelse försöker gå till en ruta där en annan varelse av samma typ står, låt varelsen stå stilla i det tidssteget. Om en stor varelse försöker gå till en ruta med en liten varelse så äter den stora varelsen den lilla varelsen. Om en stor varelse försöker gå till en matbit står den kvar där den står. Om en lite varelse försöker gå till en matbit äter den lilla varelsen upp den och får 5 energi.

Mellan varje tidssteg skriv ut spelplanen till terminalen, separera tidsstegen med en rad med 100 '-' tecken. Skriv ut tomma rutor som mellanslag, matbitar som '%' tecken, stora varelser som '@' tecken och små varelser som '*' tecken.

Efter första tidssteget läs in en siffra med hur många tidssteg som ska köras, när dessa körts läs in en ny siffra med tidssteg, upprepa detta tills användaren skriver in 'q' i stället för en siffra.

Stabiliserar sig systemet med vissa mängder stora och små varelser? Om arter dör ut ändra konstanterna tills ni har ett system som låter alla arter överleva.

6.2 Generera växter

För att grafiskt kunna generera växter är det enklare om man först genererar en symbolisk representation av växterna, denna kan komplementeras med regler som beskriver hur växterna växer.

En sådan grafisk representation kallas L-System och bygger på att man har en lista med symboler, ofta bokstäver, och regler där man i en loop ersätter symboler med korta listor av andra symboler.

6.2.1 Läsa en omskrivningsregel från fil

Grundläggande för L-System är reglerna som säger något likt, när du går igenom strängen om du hittar en symbol 'A' byt ut den mot symbollistan "BAB", detta skrivs ofta som A→BAB.

Skriv en funktion som givet ett filnamn returnerar en lista med regler lästa från filen. Reglerna i filen är på formen, separerade av nyrader

			A->ABCD

Där 'A' är ett enskilt tecken "->" är en separator och "ABCD" är en godtyckligt lång lista av tecken. Alla utskrivsbara tecken i ASCII är godtagbara på positionerna som 'A' respektive "ABCD" innehar.

Ni kan lagra era inlästa regler i structar likt nedan

struct Rule{
    char symbol;
    char* replacement;//IMPORTANT remember allokation and free
};

Betänk att minne måste allokeras för replacement arrayen, och tas bort när structen är färdiganvänd.

Testa er funktion genom att skriva ett enkelt program som använder den och skriver ut vad ni läst in.

6.2.2 Applicera en omskrivningsregel

För att kunna generera något med ett L-System behöver man applicera sina regler.

Givet att ni har en regel A→B(\A)A(/A) och en start sträng "A". Applicera omskrivnings regeln på strängen n antal gånger där n är en parameter till den funktion ni applicerar regeln i.

Systemet bör generera följande

A
B(\A)A(/A)
B(\B(\A)A(/A))B(\A)A(/A)(/B(\A)A(/A))
B(\B(\B(\A)A(/A))B(\A)A(/A)(/B(\A)A(/A)))B(\B(\A)A(/A))B(\A)A(/A)(/B(\A)A(/A))(/B(\B(\A)A(/A))B(\A)A(/A)(/B(\A)A(/A)))

Om man applicerar omskrivningsregeln 3 gånger.

6.2.3 Applicera flera omskrivningsregler

Använd er av funktionen som läser in omskrivningsregler i 6.2.1 och skriv ett program som givet ett filnamn med regler, en start sträng och en siffra applicerar reglerna i filen på strängen lika många gånger som siffran anger.

Tänk på att inte applicera regler på symboler som i denna iteration är resultatet från en regel applikation. Detta kan göras genom att ni skriver en loop som loopar över alla symboler i strängen, om det finns en omskrivningsregel för symbolen, lägg till resultatet av omskrivningen till en ny sträng annars lägg symbolen ni läste till den nya strängen.

6.2.4 Rita systemet med utskriftsregler

Även om man kan göra mycket intressant teoretisk analys angående strängarna som genereras i 6.2 är det ofta betydligt mer tillfredställande att rita upp systemen grafiskt.

För att göra det kommer vi att använda gnuplot som beskrivs i 3. Vi behöver också någon sorts regler för hur vi ska tolka olika symboler i utritningen.

Hur utritningsregler kan se ut kan man definiera lite hur som helst, ni ska implementera definitionen nedan.

Alla utritningsfunktionener har tillgång till en stack av utritnings-state (lista de bara kan läsa och skriva sista positionen i), de kan lägga till element på stacken, ta bort element från stacken och läsa det översta elementet. De skriver utdata till standard out vilket kan antingen vara koordinater, tomma rader eller en kombination av dessa. Använd koordinatformaten som används i 3.

Det utritningsstate ni behöver hålla reda på är

koordinater, var är pennan just nu
rotation, vilket håll drar man sträck om man ritar framåt (tips vinkel från uppåt i radianer - negativ vinkel betyder rotation åt höger)
skala, hur mycket skiljer sig storleken från full storlek just nu

De regler ni ska implementera är

'(' kopiera översta elementet på stacken och lägg kopian på stacken.
')' ta bort översta elementet från stacken.
'\' rotera 45^o åt vänster och multiplicera skalan med 0.6
'/' rotera 45^o åt höger och multiplicera skalan med 0.6
'A' rita ett löv på skärmen, ett antal koordinater utskrivna så att det ser ut som ett löv, kom ihåg att ta hänsyn till skala och rotation
'B' rita ett streck framåt en längdenhet multiplicerat med skala

Utritningsfunktionerna bör vara funktioner som tar en referens till er stack och skriver ut de koordinater de ska skriva ut till standard out. Om ni sedan skriver en loop som anropar rätt utritningsfunktion för varje symbol i strängen (i ordning) kommer ni att kunna ge gnuplot ert utdata och få gnuplot att rita ut något växtlikt.

För att variera utseendet på växterna lägg till variationer på utritningsreglerna för nya symboler och skriv genereringsregler som använder sig av dessa symboler. Beroende på hur ni varierar utritningsregler och genereringsregler så kan många olika växttyper genereras.

7 Behandling av tabulär data

När man gör vetenskapliga experiment och eller undersökningar är det vanligt att man får data i tabell format. Datorer är bra på att behandla tabelldata på sådana format då det oftast bara är matematik på kolumner eller rader.

Vi kommer i det här uppgifterna att använda tabeller på formatet csv (comma separated values) vilket skiljer tabellrader med radbrytning och kolumner med ',' tecken.

7.1 Radvis behandling

När man behandlar tabelldata rad för rad kan man göra saker som att omorganisera kolumner, lägga till kolumner, ändra skala på värden, tex fot till meter.

7.1.1 Sortera kolumner

Givet en csv fil med kolumner på formatet (endast två månader med för enkelhetens skull)

jan 07,jan 08,jan 09,feb 07,feb 08, feb 09

Dessa ska sorteras i datum ordning, skriv en funktion som tar en rad som parameter och returerar det sorterade resultatet.

Ny ordning på ovanstående kolumner är alltså

jan 07,feb 07,jan 08,feb 08,jan 09,feb 09

7.1.2 Räkna ut nya kolumner

Givet en tabell med datum i första kolumnen och övriga kolumner som utgifter i olika kategorier. Summera utgifterna till en ny kolumn med totala utgifterna för den dagen.

2009-03-07,500,23,14,77

ska bli

2009-03-07,500,23,14,77,614

7.1.3 Sammanfatta och ta bort kolumner

Givet resulterande tabbelen i uppgift 7.1.1 skriv en funktion som summerar datat per år till formatet

07,08,09

7.2 Kolumnvis behandling

När man behandlar data kolumntvist kan man lätt göra saker som att räkna ut summan av varje kolumn eller för den delen medelvärde och varians för datat i kolumnerna.

7.2.1 Räkna ut summan av varje kolumn

Skriv ett program som läser in en tabell i minnet, sen sickar den till en funktion som räknar ut summan av varje kolumn och returnerar en tabell rad med den informationen. Skriv programmet så att ni kan testa med olika tabeller genom att ange deras filnamn på kommandoraden.

7.2.2 Räkna ut medelvärde och varians för varje kolumn

Skriv ett program som läser in en tabell i minnet, sen sickar den till en funktion som räknar ut medelvärde och varians av varje kolumn och returnerar en tabell rad med den informationen.

Medelvärdet och varians kan räknas ut som i uppgift 1.12.2.

Skriv programmet så att ni kan testa med olika tabeller genom att ange deras filnamn på kommandoraden.

7.3 Generell behandling

Om man gör beräkningar både kolumnvis och radvis kan man göra mer komplexa beräkningar, det kan ofta ta sig formen att man gör beräkningar i flera steg, dvs först göra någon radvis beräkning och få en ny tabell som resultat sen använda den nya tabellen i kombination med en kolumnbaserad beräkning av säg medelvärdet för att göra ytterligare radbaserade beräkningar.

7.3.1 Ändra skala på tabell

Given en tabell skriv ett program som skalar tabell värdena så att den tabellen med högst summa summerar till 1. Ni ska kunna hantera godtycklig csv fil som har flyttal i alla celler.

Dvs hitta ett värde att multiplicera tabellen med som om man multiplicerar med det värdet så blir största kolumnsumman 1. Multiplicera sedan med det värdet och skriv den nya tabellen till stdout.

7.3.2 Korrelation mellan resultat

Följande datafil innehåller resultaten från ett antal labbar som studenter gjort givna i poäng. Den första kolumnen, här kallad kolumn 0, innehåller summan av de övriga. Skriv ett program som räknar ut hur många procent av de som fått 4 eller mer på första labben som också fått 4 eller mer på sista labben, dvs hur stor korrelation har bra resultat på första uppgiften med bra resultat på sista uppgiften.

8 Problemlösning (svårare än övriga)

Uppgifterna i detta avsnitt är generellt sätt svårare och mer omfattande än de i tidigare avsnitt, det går troligtvis att klara kursen utan att lyckas lösa dem men om man satsar på högre betyg är det bra övning.

8.1 Parsning

Olika slags parsning är vanliga inom programmering och att kunna skriva enkla parsers kan komma att underlätta för många programerare.

8.1.1 Läs lite data ur stor xml

En xml fil är strukturerad med tagar omgivna av <> och matchande sluttagar på formen </> se exemplet nedan.

<entag>
	lite data
	<enundertag>
		mer data
	</enundertag>
	data
	<enundertag>
		mer data
		<enunderundertag>
			text
			<enundertag>
				mer text
			</enundertag>
		</enunderundertag>
	</enundertag>
	<enundertagavannantyp>
		mer data
	</enundertagavannantyp>
	data
</entag>

Xml har även något som kallas attribut som vi inte bryr oss om i den här uppgiften.

Er uppgift är att skriva en funktion som söker rätt på taggar i xml dokument som det ovan och visar vilka andra tagar som omsluter den tag ni söker efter.

Om ni söker efter enunderundertag i dokumentet ovan bör ni få följande utdata

entag/enundertag/enunderundertag

och om ni söker efter enundertag bör utdatat bli

entag/enundertag
entag/enundertag/enunderundertag/enundertag

8.2 Orankat träd

Ett orankat träd an ha hur många eller få barn som helst (i praktiken kan någon hög gräns finnas). Detta är till exempel fallet med katalogstrukturer och xml dokument.

Givet denna funktion som returnerar en nullterminerad vektor med filer i en mapp eller en tom vektor om det är en fil som skickas in. Skriv ett program som skriver ut alla filer med sina sökvägar.

#include <sys/types.h>
#include <dirent.h>

/*when done with the returned memmory it must be freed using free*/
char** listDir(char* name){
    DIR *dp=opendir(name);
    char** vec=calloc(1,sizeof(char*));
    int index=0;
    if(dp){
        struct dirent *ep;
        char* names=calloc(1,sizeof(char));
        int offset=0;
        while(ep=readdir(dp)){
            vec=realloc(vec,(index+2)*sizeof(char*));
            vec[index++]=(char*)offset;/*add pointer offset to item offset later*/
            vec[index]=0;
            int len=strlen(ep->d_name);
            names=realloc(names,offset+len+1);
            strcpy(names+offset,ep->d_name);
            offset+=len+2;/*advance offset one past the null terminator*/
        }
        closedir(dp);
        vec=realloc(vec,(index+1)*sizeof(char*)+offset);
        {
            char* tmp;
            tmp=memcpy(vec+(index+1),names,offset);
            free(names);
            names=tmp;
        }
        {
            int i;
            for(i=0;i<index;i++)
                /*add base pointer to offset*/
                vec[i]=(char*)((int)vec[i]+(int)vec+(index+1)*sizeof(char*));
        }
    }
    return vec;
}

Observera att funktionen ovan INTE är standard C utan plattformsspecifik. Om ni kör kod på andra plattformar än de unix system som institutionen för datavetenskap tillhandahåller kan koden behöva modifieras för att fungera.

Förväntad utdata av programmet

./main katalog katalog/fil katalog/underkatalog katalog/underkatalog/fil1 katalog/underkatalog/fil2 katalog/fil2 fil3 fil

Footnotes

... kursbok ¹: Förklaring av formatsträngar sidan 504 i, Problem Solving and Program Design in C, Sixth Edition -- Jeri R. Hanly, Elliot B. Koffman

Johan Granberg 2009-09-01

Contents

1 Programmeringskoncept

1.1 Minimala program

1.1.1 Hello world

1.1.2 Anropa program

1.1.3 Skriva ut uttryck

1.1.4 Variabler

1.2 Enkla matematiska uttryck

1.2.1 Cirkelarea

1.2.2 Hypotenusan i rätvinklig triangel

1.3 If-satser

1.3.1 Är talet negativt

1.3.2 Finns talet i intervallet

1.3.3 Vem är äldst

1.4 Funktioner

1.4.1 Min och max

1.4.2 Upphöjt i två

1.5 Vektorer (array)

1.5.1 Vektorer av char: Strängar

1.5.2 Byt plats på element: statisk längd

1.5.3 Byt plats på element: variabel längd

1.5.4 Hitta största och minsta talet i en sekvens

1.6 Utskrifter

1.6.1 Utskrifter av heltal och flyttal

1.6.2 Utskrifter av felmeddelanden

1.6.3 Begränsa stränglängd

1.7 Loopar

1.7.1 Funktionen summa

1.7.2 Lägga till i en NULL-terminerad buffer

1.7.3 Skriv ut alla kommandoradsargument

1.7.4 Multiplicera matriser

1.8 Typkonvertering och felhantering

1.8.1 Konvertera sträng till heltal

1.8.2 Konvertera sträng till flyttal

1.8.3 Misslyckade konverteringar

1.9 Stränghantering

1.9.1 Längden av strängar

1.9.2 Kopiera strängar

1.9.3 Konkatenera strängar

1.9.4 Jämföra strängar

1.10 Krångligare If-satser

1.10.1 Om ett tal är i ett intervall, givet som strängar

1.10.2 Om den längsta strängen är kortare än ett tal

1.10.3 Om ett tal under hundra är ett primtal

1.11 Kommandoradsargumenthantering

1.11.1 Läs in parametrar med känd ordning

1.11.2 Läs in flaggor som kan saknas

1.11.3 Läs in flaggor med parametrar

1.12 Datastrukturer

1.12.1 Funktionen hitta intervall

1.12.2 Beräkna medelvärde och standardavvikelse

1.12.3 Lösningen av en andragradsekvation

1.13 Minnesallokering

1.13.1 Vektorer med okänd längd

1.13.2 Summera talen i två vektorer

2 Programstruktur

2.1 Indentering

2.1.1 Slumpmässigt indenterat program

2.1.2 Tvetydigt indenterat program

2.1.3 Ej indenterat program

2.2 Felsökning

2.2.1 Oändlig loop

2.2.2 Räknar fel

2.2.3 Kommer inte in i if sats

2.3 Repetitions undvikande

2.3.1 Gemensamma deluttryck

2.3.2 Upprepade loopar

2.3.3 Möjlig funktion

3 Simulera fysik

3.1 Konstant fart

3.1.1 1D

3.1.2 2D

3.2 Fall i vakuum

3.2.1 Start i vila över marken

3.2.2 Hopp från hög höjd

3.2.3 Projektilbana

3.3 Gravitation

3.3.1 Liten sattelit

3.3.2 Binärstjärnor

4 Ytterligare programmeringskoncept