Sistemi di Calcolo

Corso di Laurea in Ingegneria Informatica e Automatica - A.A. 2017-2018

HomePage | Avvisi | Diario lezioni | Programma | Materiale didattico | Esami | Forum | Login

Esercitazione 3 - 4 novembre 2016 (120 min)


Esercizio 1

Tradurre in IA32 la seguente funzione C che realizza l'algoritmo di ricerca binaria su array ordinati. Scrivere la soluzione nel file es1.s.

es1.c
int binsearch(int* v, int n, int x) {
    int m = 0;                   // restituisce 1 <=> x รจ nell'array ordinato v di dimensione n
    while (m<n) {
        int k = (m+n) >> 1;      // indice dell'elemento a meta' fra m ed n
        if (x == v[k]) return 1; // x e' in posizione k => trovato
        if (x > v[k]) m = k+1;   // x puo' essere a destra fra k+1 ed n
        else n = k;              // x puo' essere a sinistra fra m e k
    }
    return 0;
}


Usare il seguente programma di prova:

es1-main.c
#include <stdio.h>

int binsearch(int* v, int n, int x);

int main() {
    int res, v[] = { 1, 3, 4, 9, 12 }, n = sizeof(v)/sizeof(int);

    res = binsearch(v, n, 0);
    printf("%d (corretto: 0)\n", res);

    res = binsearch(v, n, 3);
    printf("%d (corretto: 1)\n", res);

    res = binsearch(v, n, 5);
    printf("%d (corretto: 0)\n", res);

    res = binsearch(v, n, 12);
    printf("%d (corretto: 1)\n", res);

    res = binsearch(v, n, 13);
    printf("%d (corretto: 0)\n", res);

    res = binsearch(v, 1, 1);
    printf("%d (corretto: 1)\n", res);

    res = binsearch(v, 0, 1);
    printf("%d (corretto: 0)\n", res);

    return 0;
}


Esercizio 2

Scrivere una funzione void cancspazi(char* s) che elimina tutti gli spazi da una stringa s e tradurla poi in IA32. Scrivere la soluzione nel file es2.s.

Usare il seguente programma di prova:

es2-main.c
#include <stdio.h>

void cancspazi(char* s);

int main() {
    char s1[] = "obi wan kenobi ";
    char s2[] = "obiwankenobi";
    char s3[] = "  leila    luke ";
    char s4[] = "";
    cancspazi(s1);
    cancspazi(s2);
    cancspazi(s3);
    cancspazi(s4);
    printf("\"%s\" (corretto: \"obiwankenobi\")\n", s1);
    printf("\"%s\" (corretto: \"obiwankenobi\")\n", s2);
    printf("\"%s\" (corretto: \"leilaluke\")\n", s3);
    printf("\"%s\" (corretto: \"\")\n", s4);
    return 0;
}


Compilare come al solito con gcc -m32 -g es2.s es2-main.c -o es2. In caso di problemi debuggare con gdb.

Esercizio 3

Tradurre in IA32 le seguenti tre funzioni C che, combinate, realizzano un semplice algoritmo di ordinamento (bubblesort). Scrivere la soluzione nel file es3.s.

es3.c
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int makepass(int* v, int n) {
    int cont = 0;
    while (--n>0)
        if (v[n-1]>v[n]) {
            swap(v+n-1, v+n);
            cont = 1;
        }
    return cont;
}

void bubblesort(int* v, int n) {
    while (makepass(v,n));
}


Scrivere tutte le funzioni assembly nello stesso file es3.s:

es3.s
.globl swap
.globl makepass
.globl bubblesort

swap: ...
    ret

makepass: ...
    ret

bubblesort: ...
    ret


Sviluppare il programma incrementalmente, testando le funzioni una alla volta con i seguenti tre main.

Main di prova per la funzione swap:
es3-main1.c
#include <stdio.h>

void swap(int* x, int* y);

int main() {
    int a = 10, b = 20;
    swap(&a, &b);
    printf("a=%d, b=%d\n", a, b); // deve stampare: a=20, b=10
    return 0;
}


Main di prova per la funzione makepass:
es3-main2.c
#include <stdio.h>

int makepass(int* v, int n);

void print(int* v, int n) {
    int i;
    for (i=0; i<n; ++i) printf("%d ", v[i]);
    printf("\n");
}

int main() {
    int v[] = { 2, 3, 4, 5, 1 };
    int n = sizeof(v)/sizeof(int);
    print(v, n);
    makepass(v, n);
    print(v, n); // deve stampare 1 2 3 4 5
    return 0;
}


Main di prova per la funzione bubblesort:
es3-main3.c
#include <stdio.h>

void bubblesort(int* v, int n);

void print(int* v, int n) {
    int i;
    for (i=0; i<n; ++i) printf("%d ", v[i]);
    printf("\n");
}

int main() {
    int v[] = { 9, 1, 3, 2, 5 };
    int n = sizeof(v)/sizeof(int);
    print(v, n);
    bubblesort(v, n);
    print(v, n); // deve stampare 1 2 3 5 9
    return 0;
}


Valid XHTML 1.0 Transitional :: Valid CSS :: Powered by WikkaWiki
Page was generated in 0.0736 seconds