Fondamenti di Informatica (SSE)

soluzioni della
prova scritta del 28 giugno 2000

1 Scrivere un programma C per "pulire" una matrice di interi con R righe e R colonne.

Il programma deve:

· leggere da tastiera gli interi da memorizzare nella matrice (guidando l'utente con opportuni messaggi),

· successivamente spostare verso le prime colonne tutti gli elementi diversi da 0, mantenendoli nello stesso ordine in cui compaiono all'interno di ciascuna riga (se si ritiene utile si può utilizzare una matrice di appoggio, ma si consiglia di evitarlo),

· stampare, riga per riga, gli elementi diversi da 0.

Esempio:

se viene letta la seguente matrice

9	58	0	0	12	0	5	0
0	0	66	3	55	0	7	32
19	0	0	67	0	0	5	0
22	11	0	9	0	4	5	0

il programma deve modificare la matrice ottenendo

9	58	12	5	0	0	0	0
66	3	55	7	32	0	0	0
19	67	5	0	0	0	0	0
22	11	9	4	5	0	0	0

e poi stampare

9 58 12 5

66 3 55 7 32

19 67 5

22 11 9 4 5

Il codice C deve essere completato da una descrizione succinta dell’algoritmo utilizzato.

Soluzione

Il programma proposto di seguito utilizza una matrice sovradimensionata, quindi chiede all’utente il numero di righe e di colonne, che non devono essere maggiori delle dimensione della matrice.

Una volta ottenute le dimensioni, legge da tastiera gli elementi della matrice e passa alla “pulizia”

La matrice viene esaminata riga per riga: sulla riga i-esima, si scandiscono gli elementi, ed ogni volta che si incontra un elemento diverso da 0 lo si assegna all’elemento di posizione pos.

All’inizio dell’esame di ciascuna riga il valore di pos viene inizializzato a 0, e poi incrementato ogni volta che si incontra un elemento diverso da 0.

Alla fine della scansione della riga, si riempie di elementi 0 la parte rimanente della riga.

#include<stdio.h>

#include<conio.h>

#define R 10

#define C 10

main()

{

int mat[R][C];

int righe, colonne, i, j, pos;

clrscr();

do {

printf("Quante righe ? (max %d) ", R);

scanf("%d", &righe);

} while( (righe<1) || (righe>R) );

do {

printf("Quante colonne ? (max %d) ", C);

scanf("%d", &colonne);

} while( (colonne<1) || (colonne>C) );

clrscr();

for(i=0; i<righe; i++)

for(j=0; j<colonne; j++) {

printf("Elemento [%d][%d] : ", i, j);

scanf("%d",&mat[i][j]);

}

for(i=0; i<righe; i++) {

pos=0;

for(j=0; j<colonne; j++)

if(mat[i][j] != 0) {

mat[i][pos] = mat[i][j];

pos++;

}

while(pos<colonne)

mat[i][pos++] = 0;

}

clrscr();

for(i=0; i<righe; i++) {

for(j=0; (j<colonne) && mat[i][j]!=0); j++)

printf("%5d", mat[i][j]);

printf("\n");

}

return 0;

}

Una soluzione alternativa poteva essere un programma che utilizzasse su ciascuna riga una procedura del tipo “bubble-sort”, che scambia due elementi di posto i e i+1 solo se quello di posto i è 0 e quello di posto i+1 è diverso da 0.

2 Illustrare come si definisce e come si richiama una funzione nel linguaggio C, descrivendo le modalità di passaggio dei parametri.

Soluzione:

Vedi testo di Bellini, Guidi, Guida al linguaggio C, capitolo 6 (in particolare 6.8) e paragrafo 8.6

3 Descrivere l'architettura della Unita Centrale di Elaborazione (CPU), con particolare riferimento ai registri interni ed al loro utilizzo durante l'esecuzione di un programma.

Soluzione:

Vedi testo di Ceri, Mandrioli, Sbattella, Informatica: arte e mestiere, paragrafi 2.3.3 e 2.4

4 Illustrare i metodi conosciuti per la soluzione di equazioni di ricorrenza.

Soluzione:

Vedi testo di Cormen, Leicerson, Rivest, Introduzione agli algoritmi, paragrafo 4.3