Programmazione I    (canale P-Z) a.a. 2007-2008
Docente: R. Silvestri     Esercitatore: A. Carosi     Tutor: J. Stefa
Prova intermedia del 15 novembre 2007

Avvertenze: non usare variabili globali; definire tutte le funzione ausiliarie usate; è consentito usare le funzioni della libreria standard; se una soluzione non è scritta in modo chiaro ed ordinato non sarà presa in considerazione.

Esercizio 1 (max 8 punti)
Scrivere una funzione, con prototipo void MinMax(float A[], long n), che modifica il vettore di input A, di n elementi di tipo float, scambiando di posizione il valore minimo e il valore massimo di A. Si può asssumere che i valori di A siano tutti distinti. Ad esempio, se A = [2.5, 5, 1.2, 3, 8] allora la funzione lo modifica così [2.5, 5, 8, 3, 1.2].
Esercizio 2 (max 12 punti)
Scrivere una funzione, con prototipo long LenS(const char T[], const char C[]), che ritorna la lunghezza della più lunga sottostringa della stringa T che è composta solamente di caratteri che appaiono nella stringa C. Ad esempio, se T = "La terra e' arata dal ratto trattato" e C = "taralli" allora la funzione ritorna 7 (la sottostringa più lunga è "trattat").
Esercizio 3 (max 10 punti)
Scrivere un programma che prende in input un intero n e stampa una matrice nxn di caratteri '0', '1' che si deduce dai seguenti esempi:
   n = 1   n = 2   n = 3   n = 4   n = 5   n = 6    n = 8      n = 9
   1       11      010     0110    00100   001100   00011000   000010000
           11      111     1111    01110   011110   00111100   000111000
                   010     1111    11111   111111   01111110   001111100
                           0110    01110   111111   11111111   011111110
                                   00100   011110   11111111   111111111
                                           001100   01111110   011111110
                                                    00111100   001111100
                                                    00011000   000111000
                                                               000010000
Esercizio 4 (max 9 punti)
Scrivere una funzione, con prototipo int Saddle(int n, const float M[][n]), che ritorna l'indice j (0 <= j < n) tale che il massimo valore della riga j è uguale al minimo valore della colonna j. Se un tale indice non esiste, la funzione ritorna -1. Ad esempio, se M è la matrice 4x4:
     3  4  19  1
     2  7  18  5
    10  3  12  7
     5  6  15  8
allora la funzione ritorna 2.
Esercizio 5 (max 10 punti)
Scrivere una funzione, con prototipo long *Ric(const int V[], long n, int x, long *nj), che ritorna un vettore allocato dinamicamente che contiene gli indici j del vettore V (di n interi) tali che V[j] = x e restituisce in *nj il numero di tali indici. Se il valore x non appare in V, la funzione ritorna NULL e restituisce in *nj il valore 0. Ad esempio, se V = [7, 2, 8, 7, 7, 4] e x = 7 allora la funzione ritorna il vettore [0, 3, 4] e restituisce in *nj il valore 3.



Soluzioni

Soluzioni esercizio 1

void MinMax(float A[], long n)
{
    long i, pmin = 0, pmax = 0;    //pmin conterra' la posizione del minimo
    float min = A[0], max = A[0];  //e pmax quella del massimo.
    for (i = 1 ; i < n ; i++) {    //determina il minimo, il massimo e
        if (A[i] < min) {          //le relative posizioni.
            min = A[i];
            pmin = i;
        }
        if (A[i] > max) {
            max = A[i];
            pmax = i;
        }
    }
    A[pmin] = max;                //scambia le posizioni del minimo
    A[pmax] = min;                //e del massimo.
}

Un'altra soluzione:

void MinMax(float A[], long n)
{
    long i, pmin = 0, pmax = 0;    //pmin e pmax conterranno le posizioni del minimo e del massimo.
    for (i = 1 ; i < n ; i++)      //determina pmin e pmax
        if (A[i] < A[pmin]) pmin = i;
        else if (A[i] > A[pmax]) pmax = i;
    float x = A[pmin];             //scambia tra loro le posizioni del minimo e del massimo.
    A[pmin] = A[pmax];
    A[pmax] = x;
}
Soluzioni esercizio 2

/* funzione ausiliaria che ritorna vero o falso a seconda che il 
   carattere ch appaia o meno nella stringa C */
int IsInC(char ch, char C[])
{
    long i = 0;
    while (C[i] != '\0' && C[i] != ch) i++;
    return (C[i] == ch);
}
long LenS(const char T[], const char C[])
{
    long max = 0, curr = 0, k = 0;
    while (T[k] != '\0') {                 //per ogni carattere di T
        if (IsInC(T[k], C)) curr++;        //se appare in C, incrementa la lunghezza corrente
        else {                             //altrimenti aggiorna eventualmente la
            if (curr > max) max = curr;    //lunghezza massima finora trovata e
            curr = 0;                      //riporta a zero la lunghezza corrente.
        }
        k++;
    }
    if (curr > max) max = curr;            //aggiorna eventualmente la lunghezza massima
    return max;
}

Un'altra soluzione:

long LenS(const char T[], const char C[])
{
    long max = 0, curr = 0, k = 0;
    while (T[k] != '\0') {                   //per ogni carattere di T
        long i = 0;                          //controlla se appare in C
        while (C[i] != '\0' && C[i] != T[k]) i++;
        if (C[i] == T[k]) {                  //se appare in C,
            curr++;                          //incrementa la lunghezza corrente e 
            if (curr > max) max = curr;      //aggiorna la lunghezza massima finora trovata.
        } else curr = 0;                     //altrimenti azzera la lunghezza corrente      
        k++;                          
    }
    return max;
}
Soluzioni esercizio 3

#include <stdio.h>

int main()
{
    int n, r, c;
    scanf("%d", &n);                    //leggi la dimensione n della matrice
    int s = (n - 1)/2, d = n/2;             //s contiene la posizione del primo 1
    for (r = 0 ; r < n ; r++) {             //della riga e d la posizione dell'ultimo
        for (c = 0 ; c < n ; c++)
            if (c < s || c > d) printf("0");
            else printf("1");
        printf("\n");
        if (r < (n - 1)/2) { s--; d++; }    //aggiorna s e d per la prossima riga
        else if ( r >= n/2) { s++; d--; }
    }
    return 0;
}

Un'altra soluzione:

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);                        //leggi la dimensione n della matrice
    int M[n][n], r, c, s = (n - 1)/2, d = n/2;
    for (r = 0 ; r <= (n - 1)/2 ; r++) {        //definisci la prima meta' delle righe
        for (c = 0 ; c < n ; c++)
            M[r][c] = (c < s || c > d ? 0 : 1);
        s--; 
        d++;
    }
    for ( ; r < n ; r++)                        //definisci la seconda meta' delle righe
        for (c = 0 ; c < n ; c++)               //ribaltando le righe della prima meta'
            M[r][c] = M[n - 1 - r][c];
    for (r = 0 ; r < n ; r++) {                 //stampa la matrice
        for (c = 0 ; c < n ; c++) printf("%d", M[r][c]);
	printf("\n");
    }
    return 0;
}
Soluzioni esercizio 4

int Saddle(int n, const float M[][n])
{
    float min, max;
    int i, j;
    for (i = 0 ; i < n ; i++) {      //per ogni i, calcola il massimo della  
        min = max = M[i][i];         //riga i e il minimo della colonna i
        for (j = 0 ; j < n ; j++)
            if (M[i][j] > max) max = M[i][j];
            else if (M[j][i] < min) min = M[j][i];
        if (min == max) return i;    //se il massimo e il minimo sono uguali, ritorna i
    }
    return -1;           //se non c'e' un indice che soddisfa la condizione ritorna -1
}

Un'altra soluzione:

int Saddle(int n, const float M[][n])
{
    int i, j;
    for (i = 0 ; i < n ; i++) {          //per ogni indice i (di riga o di colonna)
        float max = M[i][0];                 //calcola il massimo della riga i
        for (j = 1 ; j < n ; j++) 
            if (M[i][j] > max) max = M[i][j];
        float min = M[0][i];                 //calcola il minimo della colonna i
        for (j = 1 ; j < n ; j++)
            if (M[j][i] < min) min = M[j][i];
        if (min == max) return i;            //se sono uguali, ritorna i
    }
    return -1;         //se non c'e' un indice che soddisfa la condizione ritorna -1
}
Soluzioni esercizio 5

long *Ric(const int V[], long n, int x, long *nj)
{
    long i, m = 0;
    long *ind = NULL;
    for (i = 0 ; i < n ; i++)            //calcola in m il numero di indici
        if (V[i] == x) m++;              //in cui appare x
    if (m > 0) {
        ind = malloc(m*sizeof(long));       //alloca un vettore per mantenere 
        long k = 0;                         //gli m indici
        for (i = 0 ; i < n ; i++)           //e registra gli indici nel vettore
            if (V[i] == x) ind[k++] = i;
    }
    *nj = m;                             //restituisci in *nj il numero di indici
    return ind;                          //ritorna il vettore allocato oppure NULL
}

Un'altra soluzione:

long *Ric(const int V[], long n, int x, long *nj)
{
    long i, m = 0;
    long *ind = NULL;
    for (i = 0 ; i < n ; i++)                //per ogni indice del vettore V
        if (V[i] == x) {                     //se contiene il valore x
            ind = realloc(ind, (m + 1)*sizeof(long));     //rialloca il vettore degli indici
            pos[m++] = i;                                 //per mantenere un indice in piu'
        }
    *nj = m;                                 //restituisci in *nj il numero di indici
    return ind;                              //ritorna il vettore allocato oppure NULL
}






-- RiccardoSilvestri - 20 Nov 2007

Topic revision: r1 - 2007-11-20 - RiccardoSilvestri






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback