Sol151107PZ0708 < Programmazione1

Tags: view all tags
<div align="center"><big><b>Programmazione I &nbsp; &nbsp;(canale P-Z) a.a. 2007-2008<br>
</b></big>
Docente: R. Silvestri &nbsp; &nbsp; Esercitatore: A. Carosi &nbsp; &nbsp;
Tutor: J. Stefa<br>
Prova intermedia del 15 novembre 2007
</div>

<i>Avvertenze: non usare variabili globali; definire tutte le funzione ausiliarie usate; &egrave;
consentito usare le funzioni della libreria standard; se una soluzione non &egrave; scritta in modo
<b>chiaro ed ordinato</b> non sar&agrave; presa in considerazione.</i>

<dl><b>Esercizio 1 (max 8 punti)</b>   
<dd>Scrivere una funzione, con prototipo <tt>void !MinMax(float A[], long n)</tt>, che modifica il vettore di input <tt>A</tt>, di <tt>n</tt> elementi di tipo <tt>float</tt>, scambiando di posizione il valore minimo e il valore massimo di <tt>A</tt>. Si pu&ograve; asssumere che i valori di <tt>A</tt> siano tutti distinti.
Ad esempio, se <tt>A = [2.5, 5, 1.2, 3, 8]</tt> allora la funzione lo modifica cos&igrave;
<tt>[2.5, 5, 8, 3, 1.2]</tt>.</dd>
</dl>
<dl><b>Esercizio 2 (max 12 punti)</b>   
<dd>Scrivere una funzione, con prototipo <tt>long !LenS(const char T[], const char C[])</tt>, che ritorna la lunghezza della pi&ugrave; lunga sottostringa della stringa <tt>T</tt> che &egrave; composta solamente di caratteri che appaiono nella stringa <tt>C</tt>. Ad esempio, se <tt>T = "La terra e' arata dal ratto trattato"</tt> e <tt>C = "taralli"</tt> allora la funzione ritorna <tt>7</tt> (la sottostringa
pi&ugrave; lunga &egrave; <tt>"trattat"</tt>).</dd>
</dl>
<dl><b>Esercizio 3 (max 10 punti)</b>   
<dd>Scrivere un programma che prende in input un intero <tt>n</tt> e stampa una matrice <tt>nxn</tt> di caratteri <tt>'0'</tt>, <tt>'1'</tt> che si deduce dai seguenti esempi:
<tt><pre>
   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
</pre></tt>
</dd>
</dl>
<dl><b>Esercizio 4 (max 9 punti)</b>   
<dd>Scrivere una funzione, con prototipo <tt>int Saddle(int n, const float M[][n])</tt>, che ritorna l'indice <tt>j</tt> (<tt>0 <= j < n</tt>) tale che il massimo valore della riga <tt>j</tt> &egrave;
uguale al minimo valore della colonna <tt>j</tt>. Se un tale indice non esiste, la funzione ritorna <tt>-1</tt>. Ad esempio, se <tt>M</tt> &egrave; la matrice <tt>4x4</tt>:
<tt><pre>
     3  4  19  1
     2  7  18  5
    10  3  12  7
     5  6  15  8
</pre></tt>
allora la funzione ritorna <tt>2</tt>.
</dd>
</dl>
<dl><b>Esercizio 5 (max 10 punti)</b>   
<dd>Scrivere una funzione, con prototipo <tt>long *Ric(const int V[], long n, int x, long *nj)</tt>,
che ritorna un vettore allocato dinamicamente che contiene gli indici <tt>j</tt> del vettore <tt>V</tt> (di <tt>n</tt> interi) tali che <tt>V[j] = x</tt> e restituisce in <tt>*nj</tt> il numero di
tali indici. Se il valore <tt>x</tt> non appare in <tt>V</tt>, la funzione ritorna <tt>NULL</tt>
e restituisce in <tt>*nj</tt> il valore <tt>0</tt>. Ad esempio, se <tt>V = [7, 2, 8, 7, 7, 4]</tt> e 
<tt>x = 7</tt> allora la funzione ritorna il vettore <tt>[0, 3, 4]</tt> e restituisce in 
<tt>*nj</tt> il valore <tt>3</tt>.
</dd> 
</dl>

<br>
<br>

<div align="center"><big><b>Soluzioni<br></b></big></div>

<dl><b>Soluzioni esercizio 1</b> 
<br>
<br>
<dd><tt><pre>
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.
}
</pre></tt></dd>
<br>
<dd><i>Un'altra soluzione:</i></dd>
<br>
<dd><tt><pre>
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;
}
</pre></tt></dd>
</dl>
<dl><b>Soluzioni esercizio 2</b> 
<br>
<br>  
<dd><tt><pre>
/* 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' &amp;&amp; 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;
}
</pre></tt></dd>
<br>
<dd><i>Un'altra soluzione:</i></dd>
<br>
<dd><tt><pre>
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' &amp;&amp; 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;
}
</pre></tt></dd>
</dl>
<dl><b>Soluzioni esercizio 3</b> 
<br>
<br>  
<dd><tt><pre>
#include &lt;stdio.h&gt;

int main()
{
    int n, r, c;
    scanf("%d", &amp;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;
}
</pre></tt></dd>
<br>
<dd><i>Un'altra soluzione:</i></dd>
<br>
<dd><tt><pre>
#include &lt;stdio.h&gt;

int main()
{
    int n;
    scanf("%d", &amp;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;
}
</pre></tt></dd>
</dl>
<dl><b>Soluzioni esercizio 4</b> 
<br>
<br>  
<dd><tt><pre>
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
}
</pre></tt></dd>
<br>
<dd><i>Un'altra soluzione:</i></dd>
<br>
<dd><tt><pre>
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
}
</pre></tt></dd>
</dl>
<dl><b>Soluzioni esercizio 5</b> 
<br>
<br>  
<dd><tt><pre>
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
}
</pre></tt></dd>
<br>
<dd><i>Un'altra soluzione:</i></dd>
<br>
<dd><tt><pre>
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
}
</pre></tt></dd>
</dl>

<br>
<br>
<br>
<br>
<br>



-- Users.RiccardoSilvestri - 20 Nov 2007