Fondamenti di Informatica (SSE)
             soluzioni prova scritta del 6 giugno 2000
                        programma 1999-2000

1 Scrivere un programma C che legge da tastiera un testo e stampa
  sia il numero di parole che il numero medio di lettere per
  parola.
  
  Il testo viene letto come una sequenza di stringhe di
  caratteri, in cui ciascuna stringa contiene al massimo 80
  caratteri e termina con un carattere di ritorno a capo (invio).
  Una stringa di caratteri vuota (viene premuto il solo tasto
  invio) segnala la fine del testo.
  
  Una parola è definita come una sequenza ininterrotta di lettere
  (indifferentemente maiuscole o minuscole) delimitata a destra e
  sinistra da caratteri non alfabetici (spazi, punteggiatura o
  altro) o dall'inizio/termine della stringa.
  
  Il codice C deve essere completato da una descrizione succinta
  dell'algoritmo utilizzato.

La soluzione proposta è un programma iterativo che ad ogni
iterazione
-   legge una riga di testo (contenente un numero ignoto di
  parole, e un numero qualsiasi di caratteri non alfabetici tra ogni
  coppia di parole consecutive)
-   chiama una funzione che conta le parole su quella riga
-   chiama una funzione che conta i caratteri alfabetici su quella
  riga.
Dopo l'ultima iterazione vengono stampati i risultati richiesti.

La riga viene letta usando la funzione gets(char *), che è in
grado di leggere stringhe che contengono spazi, e assegna alla
stringa parametro la sequenza di caratteri letta, in cui viene
aggiunto il terminatore '\0'.


#include <stdio.h>
#include <conio.h>
#define LENGTH 80

typedef char t_riga[LENGTH+1];
     /* un carattere in più per il terminatore '\0' */
	 /* la funzione seguente restituisce   1 se il carattere passato è una
lettera maiuscola o minuscola,   0 altrimenti*/

int lettera(char c){   
	if ((c>='a') && (c<='z') || (c>='A') && (c<='Z'))
        return 1;
    else
        return 0;
}


/* la funzione num_parole restituisce il numero di parole sulla
riga passata   come parametro.   Un inizio di parola è
contraddistinto da un carattere alfabetico preceduto
   da un carattere non alfabetico.
   Il carattere predecessore viene memorizzato nella variabile
prec.
   La variabile prec viene inizializzata a ' ' (spazio) per far sì
che venga
   conteggiata anche l'eventuale parola ad inizio riga
*/
int num_parole(t_riga a)
{
    int n=0, i;
    char prec=' ';

    for(i=0; a[i]!='\0'; i++)
    {
        if(lettera(a[i]) && !lettera(prec))
            n++;
        prec = a[i];
    }
    return n;
}


/* la funzione num_lettere conta il numero
   di caratteri alfabetici nella riga passata
*/
int num_lettere(t_riga a)
{
    int n=0, i;

    for(i=0; a[i]!='\0'; i++)
        if(lettera(a[i]))
            n++;
    return n;
}


main()
{
    t_riga riga;
    int n_lett=0, n_par=0;
    float media;

    clrscr();
    printf("Digita testo\n");
    do {
        gets(riga);
        n_par += num_parole(riga);
        n_lett += num_lettere(riga);
    } while(riga[0] != '\0');
    media=(n_lett*1.0)/n_par;  /* il prodotto per 1.0 permette di
ottenere
                                  risultati frazionari */
    printf("\nil testo contiene %d parole e %f lettere per
parola\n",
             n_par, media);
    return 0;
}


2 Descrivere i costrutti disponibili nel linguaggio C per
  realizzare programmi iterativi.

Vedi testo di Bellini, Guidi, Guida al linguaggio C, McGraw-Hill,
paragrafi 3.1, 3.4, 3.5.


3 Descrivere le modalità di codifica binaria dei numeri interi.
Vedi testo di Ceri, Mandrioli, Sbattella, Informatica arte e
mestiere, McGraw-Hill, paragrafi 11.1


4 Illustrare il funzionamento della parte di sistema operativo
  destinata alla gestione dei processi.
Vedi testo di Ceri, Mandrioli, Sbattella, Informatica arte e
mestiere, McGraw-Hill, sottoparagrafi 13.2.1, 13.2.2, 13.2.3

               Programma anni accademici precedenti

1 Descrivere l'algoritmo di ordinamento per fusione (merge-sort)
  e discuterne la complessità computazionale.

program merge;
const    nmax=100;
typevettore=array[1..nmax] of integer;
var a: vettore;
    na: integer;

procedure leggi_vettore(var v:vettore; var n:integer);
          var i:integer;
begin
     write('scrivi la dimensione del vettore: ');readln(n);
     for i:=1 to n do begin
         write('v(',i,')=');readln(v[i])
     end
end;


procedure combina(var v:vettore;inizio, medio, fine:integer);
(*combina i sottovettori v[inizio..medio] e v[medio+1..fine] *)
     var c:vettore;
         i1,i2,i,j:integer;
begin
     i1:=inizio;i2:=medio+1;i:=1;
     repeat
         if v[i1]<v[i2] then begin
            c[i]:=v[i1]; i1:=i1+1
         end else begin
            c[i]:=v[i2]; i2:=i2+1
         end;
         i:=i+1
     until (i1>medio) or (i2>fine);
     for j:=i to fine-inizio+1 do
         if i1>medio then
            c[j]:=v[i2+j-i]
         else
            c[j]:=v[i1+j-i];
     for i:=inizio to fine do
         v[i]:=c[i-inizio+1]
end;

procedure merge_sort(var v:vettore; inizio,fine:integer);
          var medio:integer;
begin
     if inizio<fine then begin
        medio:=(inizio+fine) div 2;
        merge_sort(v,inizio,medio);
        merge_sort(v,medio+1,fine);
        combina(v,inizio,medio,fine)
     end
end;

procedure stampa(v:vettore;n:integer);
     var i:integer;
begin
     for i:=1 to n do
            writeln(v[i])
end;

begin (*main*)
      leggi_vettore(a,na);
      merge_sort(a,1,na);
      writeln('il vettore ordinato e'':');
      stampa(a,na);
      readln
end (*main*).
  
Per la complessità del merge sort vedi testo di Cormen, Leicerson,
Rivest, Introduzione agli algoritmi, Jackson, paragrafo 4.1
  

2 Scrivere un programma Pascal che legge da tastiera gli elementi
  di una matrice bidimensionale di reali e decide se la matrice
  contiene almeno un elemento che sia maggiore della somma di
  tutti gli altri elementi sulla stessa riga.
  Il codice Pascal deve essere completato da una descrizione
  succinta dell'algoritmo utilizzato.

program verifica;  const NMAX=10;type
matrice=array[1..NMAX,1..NMAX] of real;var a:matrice;
somma: real;      nr,nc,i,j,im,jm:integer;
trovato:boolean;procedure leggi_matrice(var p,q:integer; var
v:matrice);                  var i,j:integer;
        begin
         write('scrivi il numero di righe (max 10): ');
             readln(p);
         write('scrivi il numero di colonne (max 10): ');
             readln(q);
         for i:=1 to p do begin
                 for j:=1 to q do
             read(v[i,j]);
                 readln;
         end
        end;

begin
        leggi_matrice(nr,nc,a);
        trovato:=false;
        i:=1;
        repeat
            somma:=0;
            for j:=1 to nc do
                somma:=somma+a[i,j];
            for j:=1 to nc do
                if a[i,j]>somma-a[i,j] then begin
                   trovato:=true;
                   im:=i;
                   jm:=j
                end;
            i:=i+1
        until trovato;
        if trovato then
            writeln('elemento trovato in posizione
(',im,',',jm,')')
        else
            writeln('elemento non trovato')
end.


Per i quesiti 3 e 4 si veda la soluzione per l'a.a. 1999-2000.