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;                                              

type      vettore=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.