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.