Programmeringsmetodik: Lösningar till tentamen 2010-11-04

Observera att detta är ett förslag på lösningar. Det finns andra lösningar som också är korrekta.

Testfiler

data4.txt: Exemplet från tentan, med 4 mätvärden. Den ska ge resultatet x=8, y=47, value=0.750000. Körtiden med programmen nedan är knappt märkbar.

data1k.txt: En testfil med 1000 mätvärden, med sensorsidan 1000000, som ska ge resultatet x=17, y=42, value=1.200000. Körtiden med programmen nedan är knappt märkbar.

data2M.txt (obs: 43 megabyte): En testfil med 2000000 mätvärden, med sensorsidan 1000000, som ska ge resultatet x=17, y=42, value=2.000000. Körtiden med hashtabell-programmet nedan (uppgift 2) är några sekunder. Med list-programmet (uppgift 1) tar det 1-2 timmar, beroende på hur snabb dator man har.

1. Uppgift för betyget 3 respektive G

Ladda ner: list-brightest.c

/* list-brightest.c */

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

struct Pixel {
    int x;
    int y;
    double brightness;
    struct Pixel *next;
};

struct Pixel *first = NULL;

struct Pixel *find_pixel(int x, int y) {
    struct Pixel *p = first;
    while (p != NULL) {
        if (p->x == x && p->y == y)
            return p;
        p = p->next;
    }
    return NULL;
}

struct Pixel *new_pixel(int x, int y) {
    struct Pixel *p = (struct Pixel *)malloc(sizeof(struct Pixel));
    if (p == NULL) {
        fprintf(stderr, "Memory full. Couldn't allocate space for another pixel.\n");
        exit(EXIT_FAILURE);
    }
    p->x = x;
    p->y = y;
    p->brightness = 0;
    p->next = first;
    first = p;
    return p;
}

void add_measurement(int x, int y, double value) {
    struct Pixel *p = find_pixel(x, y);
    if (p == NULL)
        p = new_pixel(x, y);
    p->brightness += value;
}

struct Pixel *find_brightest_point(void) {
    struct Pixel *p = first;
    struct Pixel *brightest_pixel_so_far = NULL;
    double brightest_value_so_far = 0.0;

    while (p != NULL) {
        if (p->brightness > brightest_value_so_far) {
            brightest_value_so_far = p->brightness;
            brightest_pixel_so_far = p;
        }
        p = p->next;
    }
    return brightest_pixel_so_far;
}

int main(void) {
    char file_name[1000];
    FILE *tsin;
    int x, y;
    double brightness;
    long int number;
    struct Pixel *brightest_pixel;

    printf("Data file name: ");
    fgets(file_name, sizeof file_name, stdin);
    /* Get rid of the trailing newline character from fgets */
    if (file_name[strlen(file_name) - 1] == '\n')
        file_name[strlen(file_name) - 1] = '\0';
    tsin = fopen(file_name, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Couldn't read the data file '%s'.\n", file_name);
        fprintf(stderr, "Possible cause: %s (error code %d).\n", strerror(errno), errno);
        exit(EXIT_FAILURE);
    }

    number = 0;
    printf("Reading data from from '%s'...\n", file_name);
    while (fscanf(tsin, "%d %d %lf", &x, &y, &brightness) == 3) {
        add_measurement(x, y, brightness);
        ++number;
    }
    fclose(tsin);
    printf("Finished reading %ld measurements from '%s'.\n", number, file_name);

    printf("Finding brightest point...\n");
    brightest_pixel = find_brightest_point();
    printf("Brightest point: x=%d, y=%d, value=%f\n",
           brightest_pixel->x, brightest_pixel->y, brightest_pixel->brightness);

    return EXIT_SUCCESS;
}

2. Uppgift för betyget 4 respektive VG

Ladda ner: hash-brightest.c

/* hash-brightest.c */

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

#define HASH_TABLE_SIZE (3*1000*1000 + 1)

struct Pixel {
    int x;
    int y;
    double brightness;
    struct Pixel *next;
};

/* Automatically set to all NULL, so we don't need to initialize */
struct Pixel *hash_table[HASH_TABLE_SIZE];

unsigned int hash_pixel(int x, int y) {
    return (x + y) % HASH_TABLE_SIZE;
}

struct Pixel *find_pixel(int x, int y) {
    unsigned int bucket = hash_pixel(x, y);
    struct Pixel *p = hash_table[bucket];
    while (p != NULL) {
        if (p->x == x && p->y == y)
            return p;
        p = p->next;
    }
    return NULL;
}

struct Pixel *new_pixel(int x, int y) {
    unsigned int bucket = hash_pixel(x, y);
    struct Pixel *p = (struct Pixel *)malloc(sizeof(struct Pixel));
    if (p == NULL) {
        fprintf(stderr, "Memory full. Couldn't allocate space for another pixel.\n");
        exit(EXIT_FAILURE);
    }
    p->x = x;
    p->y = y;
    p->brightness = 0;
    p->next = hash_table[bucket];
    hash_table[bucket] = p;
    return p;
}

void add_measurement(int x, int y, double value) {
    struct Pixel *p = find_pixel(x, y);
    if (p == NULL)
        p = new_pixel(x, y);
    p->brightness += value;
}

struct Pixel *find_brightest_point(void) {
    int bucket;
    struct Pixel *brightest_pixel_so_far = NULL;
    double brightest_value_so_far = 0.0;

    for (bucket = 0; bucket < HASH_TABLE_SIZE; ++bucket) {
        struct Pixel *p = hash_table[bucket];
        while (p != NULL) {
            if (p->brightness > brightest_value_so_far) {
                brightest_value_so_far = p->brightness;
                brightest_pixel_so_far = p;
            }
            p = p->next;
        }
    }
    return brightest_pixel_so_far;
}

int main(void) {
    char file_name[1000];
    FILE *tsin;
    int x, y;
    double brightness;
    long int number;
    struct Pixel *brightest_pixel;

    printf("Data file name: ");
    fgets(file_name, sizeof file_name, stdin);
    /* Get rid of the trailing newline character from fgets */
    if (file_name[strlen(file_name) - 1] == '\n')
        file_name[strlen(file_name) - 1] = '\0';
    tsin = fopen(file_name, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Couldn't read the data file '%s'.\n", file_name);
        fprintf(stderr, "Possible cause: %s (error code %d).\n", strerror(errno), errno);
        exit(EXIT_FAILURE);
    }

    number = 0;
    printf("Reading data from from '%s'...\n", file_name);
    while (fscanf(tsin, "%d %d %lf", &x, &y, &brightness) == 3) {
        add_measurement(x, y, brightness);
        ++number;
    }
    fclose(tsin);
    printf("Finished reading %ld measurements from '%s'.\n", number, file_name);

    printf("Finding brightest point...\n");
    brightest_pixel = find_brightest_point();
    printf("Brightest point: x=%d, y=%d, value=%f\n",
           brightest_pixel->x, brightest_pixel->y, brightest_pixel->brightness);

    return EXIT_SUCCESS;
}

3. Uppgift för betyget 5

Ingen lösning än.


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 5 november 2010