Corso di Fondamenti di Informatica A

Soluzione agli esercizi proposti in laboratorio

Esercitazione n. 5

Esercizio

Scrivere un modulo in C, vet_io.c che:

contenga una procedura leggi_vet che legge da tastiera un vettore di interi
contenga una procedura stampa_vet che stampa su video un vettore di interi

Soluzione:

File vet_io.h:

void leggi_vet(int v[], int n);
void stampa_vet(int v[], int n);

File vet_io.c:

#include <stdio.h>
#include "vet_io.h"
void leggi_elem(int *E, int index)
{
printf("v[%d] = ",index);
scanf("%d",E);
}
void leggi_vet(int v[], int n)
{
int i;
for (i=0; i<n; i++)
leggi_elem(&v[i],i);
}
void stampa_vet(int v[], int n)
{
int i;
for (i=0; i<n; i++) printf("%d ",v[i]);
}

Non e` necessario sportare tutte le procedure e funzioni che ci sono nel modulo. Ad esempio, la procedura leggi_elem non viene esportata (cioe` inserita nel file header). Questo significa che sara` possibile invocarla solo all'interno del modulo vet_io, e non all'interno dei file che includono il file header vet_io.h

Esercizio

Progettare un programma C che, utilizzando il modulo vet_io,

Legga da tastiera un vettore di valori interi
Calcoli la media dei valori pari presenti nel vettore
Stampi il risultato

Si strutturi opportunamente il programma in procedure e funzioni

Soluzione:

(Il progetto deve contenere anche il file vet_io.c)

#include <stdio.h>
#include "vet_io.h"

#define N 10
/* La dimensione massima del vettore e' N. Attenzione: non viene segnalato nessun errore dal compilatore/linker e neppure durante l'esecuzione se la dimensione viene superata.
*/

float media_pari(int v[], int n);

main()
{
int vett[N];
float media;
leggi_vet(vett,N);
printf("\nE' stato introdotto il vettore:\n");
stampa_vet(vett,N);
printf("\n"); /* a capo */
media = media_pari(vett,N);
printf("Media elementi pari = %f\n",media);
}

float media_pari(int v[], int n)
{
int i,np=0;
float somma=0.0;
for (i=0; i<n; i++)
     if (v[i]%2==0)
     {
      somma = somma + v[i];
      np++;
     }
return somma/np;
}

Esercizio:

Aggiungere al modulo vet_io una procedura che legge un vettore di interi ordinato in modo crescente. Si progetti poi un programma C che:

Legga da tastiera un vettore V di valori ordinati in senso crescente
Legga un elemento E da tastiera
Effettui la ricerca binaria dell'elemento E sul vettore V. La ricerca deve essere effettuata con una funzione definita ricorsivamente che restituisce la posizione dell'elemento nel vettore oppure un valore negativo se l'elemento non è presente.
Visualizzi a video il risultato della ricerca

Soluzione:
Il modulo vet_io modificato:

File: vet_io.h

void leggi_vet(int v[], int n);
void stampa_vet(int v[], int n);
void leggi_vet_ord(int v[], int n);

File: vet_io.c

#include <stdio.h>
#include "vet_io.h"
#define TRUE 1
#define FALSE 0
void leggi_elem(int *E, int index)
{
printf("v[%d] = ",index);
scanf("%d",E);
}
void leggi_vet(int v[], int n)
{
int i;
for (i=0; i<n; i++)
     leggi_elem(&v[i],i);
}
void stampa_vet(int v[], int n)
{
int i;
for (i=0; i<n; i++) printf("%d ",v[i]);
}
void leggi_vet_ord(int v[], int n)
{
int i, errore=FALSE, ultimo;
leggi_elem(&v[0],0);
ultimo=v[0];
for (i=1; i<n; i++)
{ do
   { leggi_elem(&v[i],i);
     if (v[i]<=ultimo)
        { errore=TRUE;
          printf("Inserisci un valore maggiore di %d\n",ultimo);
        }
     else errore = FALSE;
   } while (errore);
   ultimo=v[i];
}
}

File: eserc.c

#include "vet_io.h"
#define N 5
int ric_bin(int v[], int e, int l, int h);
main()
{
   int v[N], p, e;
   leggi_vet_ord(v,N);
   printf("Elemento da cercare: ");
   scanf("%d",&e);
   p=ric_bin(v,e,0,N);
   if (p>=0)
      {printf("%d trovato in posizione %d\n",e,p);}
   else printf("%d non trovato");
}
int ric_bin(int v[], int e, int l, int h)
{   int m;
    if (l>h)
       return -1; /* elemento non trovato */
    m=(l+h)/2;
    if (v[m]==e) { return m;} /* elemento trovato in pos. m*/
    if (v[m]<e)
       { return ric_bin(v,e,m+1,h); }
    else return ric_bin(v,e,l,m-1);
}

Esercizio: Naive Sort

Dato un vettore di elementi di un certo tipo, sul quale è definita una relazione d'ordine totale (ad esempio, tipo float), l'algoritmo di ordinamento Naive sort (o selection sort, o ordinamento per minimi successivi) ad ogni passo seleziona il minimo nel vettore e lo pone nella prima posizione, richiamandosi ed escludendo dal vettore il primo elemento.

Scrivere un programma C che utilizza il modulo vet_io. Un ulteriore modulo vet_sort contiene (ed esporta, nel corrispondente file header vet_sort.h) le seguenti procedure e funzioni:

Procedura minimo, ricorsiva, che, dati un vettore ed un indice Start, restituisce il più piccolo elemento del vettore successivo a Start e la sua posizione nel vettore.
Procedura Naive_sort che ordina, tramite una procedura ricorsiva, il vettore usando l'algoritmo Naive Sort.

La funzione main, che si troverà su un modulo esercizi.c esegue la lettura di un vettore e stampa la versione ordinata del vettore.

Soluzione:

File: vet_sort.h

void minimo(int v[], int Num, int start, int *min, int *minpos);
void naive_sort(int v[], int Num, int start);

Si noti il passaggio per riferimento dei parametri min e minpos; sono dei parametri di output per la procedura, quindi non potrebbero essere passati per valore.

File: vet_sort.c

#include "vet_sort.h"
void scambia(int *a, int*b)
{ int app;
app=*a; *a= *b; *b=app;
}
/*
Questa procedura considera (implicitamente) degli elementi del vettore v
soltanto quelli compresi fra start e Num.
*/
void minimo(int v[], int Num, int start, int *min, int *minpos)
{ int min1, minpos1;
if (start==Num) // il vettore contiene un solo elemento
    { *min=v[start];
      *minpos=start;
    }
else
     { // calcolo il minimo sul resto del vettore
       minimo(v,Num,start+1,&min1,&minpos1);
       // se il minimo del resto e` piu` piccolo del primo elem del vettore
       if (min1<v[start])
          { *min=min1;
            *minpos=minpos1; }
       else
          { *min=v[start];
            *minpos=start; }
     }
}
/* ordina il vettore da Start a Num */
void naive_sort(int v[], int Num, int start)
{int min, posmin;
if (Num>start) // Se il vettore ha piu` di 1 elemento
{
   // calcola il minimo dopo Start
   minimo(v, Num,start+1,&min,&posmin);
   /* se il minimo sul resto del vettore e` piu` piccolo del primo elemento,
    lo scambia col primo elemento. Quindi, il piu` piccolo elemento del
    vettore viene portato in testa */
   if (min<v[start])
      { scambia(&v[posmin],&v[start]); }
   /* resta da ordinare il vettore da start+1 in avanti */
   naive_sort(v,Num,start+1);
}
}

Anche qui non abbiamo esportato (cioe` inserito nel file header) le procedure che non servivano negli altri moduli. Ad esempio, la procedura scambianon viene esportata. Si poteva anche non esportare la procedura minimo.

File: Esercizi.c

#include "vet_io.h"
#include "vet_sort.h"
#define N 5
main()
{ int v[N];
   leggi_vet(v,N);
   naive_sort(v,N-1,0);
   stampa_vet(v,N);
}

Nel progetto dovranno essere contenuti tutti e tre i file esercizi.c, vet_sort.c e vet_io.c.

Esercizio

Scrivere una funzione C che, data una stringa A ed una stringa B, calcoli il numero di occorrenze della stringa A in B. Ad esempio, se B="tre tigri contro tre tigri" ed A="tr", deve restituire 3.

Soluzione:

#include <stdio.h>

#define N 81

int findstr(char stringa[], char substringa[]);

main()
{
char s1[N],s2[N];
int nocc;

printf("Inserire stringa: ");
scanf("%s",s1);
/* per inserire stringhe che contengono spazi: gets(s1); */
printf("Inserire sottostringa da cercare: ");
scanf("%s",s2);
nocc = findstr(s1,s2);
printf("\n%s compare %d volte in %s\n",s2,nocc,s1);
}

int findstr(char stringa[], char substringa[])
{
int nocc=0,i,j,k;
for (i=0; stringa[i] != '\0'; i++)
{
j=0;
k=i;
while ((stringa[k]==substringa[j]) && (substringa[j] != '\0') && (stringa[k] != '\0'))
{
k++;
j++;
}
if (substringa[j]=='\0') nocc++;
}
return nocc;
}