Fondamenti di Programmazione    (canale E-O) a.a. 2009-2010
Docente: R. Silvestri     Esercitatori: P. Wollan e T. Mancini
Esercizi del 6 novembre 2009
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 9 punti)
Scrivere un programma che prende in input un intero n e stampa una matrice nxn di caratteri '-' e '+' che si deduce dai seguenti esempi:
   n = 1   n = 2   n = 3   n = 4   n = 5   n = 8      n = 9   
   +       ++      -+-     -++-    --+--   ---++---   ----+----
           ++      +++     ++++    -+++-   --++++--   ---+++---
                   -+-     ++++    +++++   -++++++-   --+++++--
                           -++-    -+++-   ++++++++   -+++++++-
                                   --+--   ++++++++   +++++++++
                                           -++++++-   -+++++++-
                                           --++++--   --+++++--
                                           ---++---   ---+++---
                                                      ----+----
Esercizio 2 (max 8 punti)
Scrivere una funzione, void minmax(float A[], int n), che modifica il vettore di input A, di dimensione n, 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, 0.2, 3, 8] allora la funzione lo modifica così [2.5, 5, 8, 3, 0.2].
Esercizio 3 (max 10 punti)
Scrivere una funzione, int maxsubstr(char *s, char *sc), che ritorna la lunghezza della più lunga sottostringa della stringa s che è composta solamente di caratteri che appaiono nella stringa sc. Ad esempio, se s = "Troppo corto" e sc = "porto" allora la funzione ritorna 5 (la sottostringa più lunga è "roppo").
Esercizio 4 (max 11 punti)
Scrivere una funzione int saddle(int n, float M[n][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 11 punti)
Scrivere una funzione, int *occ(int V[], int n, int x, int *nj), che ritorna un vettore allocato dinamicamente che contiene gli indici j del vettore V (di dimensione n) 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.


Soluzione esercizio 1
#include <stdio.h>

int main() {
    int n;
    printf("inserire un intero: ");
    scanf("%d", &n);
    int plus = 2 - (n % 2);     // numero di '+' nella prima riga
    int r, c;
    for (r = 0 ; r < n ; r++) {
        int minus = (n - plus)/2;   // numero di '-' prima e dopo i '+'
        for (c = 0 ; c < minus ; c++) printf("-");
        for (c = 0 ; c < plus ; c++) printf("+");
        for (c = 0 ; c < minus ; c++) printf("-");
        printf("\n");
        if (r < n/2) plus += 2;     // numero di '+' della prossima riga
        else plus -= 2;
        if (plus > n) plus = n;
    }
    return 0;
}
Soluzione esercizio 2
void minmax(float A[], int n) {
    int i, imin = 0, imax = 0;   /* imin e imax conterranno le posizioni
                                    del valori minimo e massimo. */
    for (i = 1 ; i < n ; i++) {
        if (A[i] < A[imin])
            imin = i;
        if (A[i] > A[imax])
            imax = i;
    }
    float x = A[imin];     // scambia il minimo con il massimo
    A[imin] = A[imax];
    A[imax] = x;
}
Soluzione esercizio 3
/* funzione ausiliaria che ritorna true se il carattere c appare nella
 * stringa s, altrimenti ritorna false. */
int charinstr(char c, char *s) {
    int i = 0;
    while (s[i] != '\0' && s[i] != c) i++;
    return (s[i] == c);
}

int maxsubstr(char *s, char *sc) {
    int i, len = 0, max = 0;
    for (i = 0 ; s[i] != '\0' ; i++) {
        if (charinstr(s[i], sc)) {
            len++;
            if (len > max) max = len;
        } else
            len = 0;
    }
    return max;
}
Soluzione esercizio 4
/* funzione ausiliara che ritorna il massimo della riga r della matrice M */
float maxR(int n, float M[n][n], int r) {
    float max = M[r][0];
    int i;
    for (i = 1 ; i < n ; i++)
        if (M[r][i] > max) max = M[r][i];
    return max;
}

/* funzione ausiliaria che ritorna il minimo della colonna c della matrice M */
float minC(int n, float M[n][n], int c) {
    float min = M[0][c];
    int i;
    for (i = 1 ; i < n ; i++)
        if (M[i][c] < min) min = M[i][c];
    return min;
}

int saddle(int n, float M[n][n]) {
    int j = 0;
    while (j < n && maxR(n, M, j) != minC(n, M, j))
        j++;
    if (j < n) return j;
    else return -1;
}
Soluzione esercizio 5
#include <stdlib.h>

int *occ(int V[], int n, int x, int *nj) {
    int *occArray = NULL, numocc = 0, i;
    for (i = 0 ; i < n ; i++) {
        if (V[i] == x) {
            occArray = realloc(occArray, (numocc + 1)*sizeof(int));
            occArray[numocc++] = i;
        }
    }
    *nj = numocc;
    return occArray;
}