Università degli Studi di Udine
Corsi di laurea in Ing. Elettronica Gestionale Fondamenti di programmazione
13 novembre 2015 - Prova intermedia
Matricola ____________________________
Nome ____________________________
Cognome ____________________________
Aula ____ Fila (dalla cattedra) ____ Posto (dalla porta) ___
Esercizio 1 (1 punto)
Dovete chiamare la funzione swap per scambiare gli elementi v[i] e v[i+1] del vettore v. Indicare la o le istruzioni corrette:
[X] swap (&v[i], &v[i+1]);
[ ] swap (v[i], v[i+1]);
[ ] swap (*v[i], *v[i+1]);
[ ] swap (&(v+i), &(v+1));
[ ] swap (*(v+i), *(v+1));
Esercizio 2 (1 punto)
Che risultato si ottiene al termine dell’esecuzione del seguente frammento di codice?
i = 2;
i += i*i++;
[X] il risultato è indefinito [ ] i = 4
[ ] i = 6 [ ] i = 8 i = 2;
i += i*i--;
[X] il risultato è indefinito [ ] i = 2
[ ] i = 4 [ ] i = 6 i = 2;
i += i*++i;
[X] il risultato è indefinito [ ] i = 6
[ ] i = 8 [ ] i = 10 i = 3;
i += i*--i;
[X] il risultato è indefinito [ ] i = 5
[ ] i = 7 [ ] i = 9
Esercizio 3 (3 punti)
La funzione riempi_sottocubo legge da tastiera i valori con cui inizializzare una porzione cubica di un vettore tridimensionale di interi di dimensioni 10 x 10 x 10. La fuzione restituisce le coordinate del vertice e la lunghezza del lato del sottocubo inizializzato.
Si scriva il prototipo di tale funzione e un esempio di chiamata completando il codice seguente.
/* prototipo */
_________ riempi_sottocubo (______________________________________________);
/* chiamata */
int x_vertice, y_vertice, z_vertice, lato;
int c[10][10][10];
lato = _______________________________________________________
/* prototipo */
int riempi_sottocubo (int cubo[10][10][10], int *px, int *py, it *px);
/* chiamata */
int x_vertice, y_vertice, z_vertice, lato;
int c[10][10][10];
lato = riempi_sottocubo (c, &x_vertice, &y_vertice, &z_vertice);
Esercizio 4 (4 punti)
Un vettore contiene i valori delle monete utilizzate in una data valuta (per esempio, per l’euro, espressi in centesimi:
int valore[] = { 1, 2, 5, 10, 20, 50, 100, 200 }). Si assuma che i valori in tale vettore siano già ordinati in ordine crescente.
La funzione componi_importo stampa la quantità di ciascuna moneta necessaria per comporre un certo importo, utilizzando monete i cui valori disponibili sono passati in un vettore del tipo sopra descritto, insieme alla sua dimensione.
L’algoritmo utilizzato riduce l’importo residuo da comporre utilizzando i valori delle monete disponibili a partire dal massimo e passando alle monete di valore inferiore quando l’importo residuo risulta minore della moneta attualmente considerata.
Si completi la funzione componi_importo e si risponda alle domande riportate nel seguito.
void componi_importo (int importo, int valore[], int n) {
int i, importo_residuo, conta_monete;
importo_residuo = importo;
conta_monete = 0;
i = n-1;
while (_________________ > 0 && i >= 0) {
if (______________________ >= valore[i]) {
______________________ -= ____________;
_______________++;
} else {
printf ("%d da %d\n", conta_monete, valore[i]);
______--;
___________________ = 0;
} }
printf ("%d da %d\n", conta_monete, valore[i]);
if (importo_residuo > 0)
printf ("resto %d\n", importo_residuo);
return;
}
La condizione valore[0] > 1 è necessaria o sufficiente affinché venga stampato un resto? ________________
(necessaria)
La condizione valore[0] == 1 è necessaria o sufficiente affinché non venga stampato un resto?
_________________ (sufficiente)
void componi_importo (int importo, int valore[], int n) {
int i, importo_residuo, conta_monete;
importo_residuo = importo;
conta_monete = 0;
i = n-1;
while (importo_residuo > 0 && i >= 0) {
if (importo_residuo >= valore[i]) {
importo_residuo -= valore[i];
conta_monete++;
} else {
printf ("%d da %d\n", conta_monete, valore[i]);
i--;
conta_monete = 0;
} }
printf ("%d da %d\n", conta_monete, valore[i]);
if (importo_residuo > 0)
printf ("resto %d\n", importo_residuo);
return;
}
Esercizio 5 (3 punti)
La funzione ricorsiva int fibonacci_r (int n) restituisce Fn, cioè il termine n- esimo della successione di Fibonacci (la cui definizione è riportata nel riqudro). La si completi.
int fibonacci_r (int n) {
if ___________
____________
if ____________
_____________
return _____________________________;
}
2 1
1 0
1 0
n n n n
F F F F F f
int fibonacci_r (int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci (n-1) + fibonacci (n-2);
}
Esercizio 6 (2 punti)
Cosa stampa la seguente funzione?
void f1 (void) {
int i = 2;
char s[16] = "testodiprova";
s[i--] = s[7];
s[2 * ++i] = '\0';
printf ("%s", s);
return;
} tept
void f2 (void) {
int i = 3;
char s[16] = "testodiprova";
s[i++] = s[7];
s[2 * --i] = '\0';
printf ("%s", s);
return;
} tespod
void f3 (void) {
int i = 4;
char s[16] = "testodiprova";
s[i++] = s[7];
s[2 * --i] = '\0';
printf ("%s", s);
return;
}
testpdip
void f4 (void) {
int i = 5;
char s[16] = "testodiprova";
s[i++] = s[7];
s[2 * --i] = '\0';
printf ("%s", s);
return;
}
testopipro
Esercizio 7 (5 punti)
Si scriva la funzione prima_pari_poi_dispari che riceve come argomenti un vettore di interi e la sua dimensione e sposta nel vettore tutti i numeri pari prima dei dispari. Non è consentito utilizzare un vettore temporaneo.
Suggerimento: si utilizzi una versione modificata dell’algoritmo bubblesort in cui lo scambio avviene se l’elemento corrente del vettore è dispari e quello successivo è pari. Si assuma già disponibile la funzione void swap (int *pa, int *pb).
Esempio: { 5, 3, -8, 0, 1, 6, 7, 9, 0, -1, -7, 0, -4} → { -8, 0, 6, 0, 0, -4, 5, 3, 1, 7, 9, -1, -7 }
void prima_pari_poi_dispari (int v[], int dim) {
int contatore_scambi, i;
do {
contatore_scambi = 0;
/* per ogni elemento del vettore (fino al penultimo) */
for (i = 0; i < dim-1; i++) {
/* se elemento[i+1] e` pari e elemento[i] e` dispari scambia elemento[i] ed elemento[i+1] */
if (v[i+1] % 2 == 0 && v[i] % 2 != 0) {
swap (&v[i], &v[i+1]);
contatore_scambi++;
} }
} while (contatore_scambi > 0); /* while (e` stato effettuato almeno uno scambio) */
return;
}
Si scriva la funzione prima_dispari_poi_pari che riceve come argomenti un vettore di interi e la sua dimensione e sposta nel vettore tutti i numeri dispari prima dei pari. Non è consentito utilizzare un vettore temporaneo.
Suggerimento: si utilizzi una versione modificata dell’algoritmo bubblesort in cui lo scambio avviene se l’elemento corrente del vettore è pari e quello successivo è dispari. Si assuma già disponibile la funzione void swap (int *pa, int *pb).
Esempio: { 5, 3, -8, 0, 1, 6, 7, 9, 0, -1, -7, 0, -4} → { 5, 3, 1, 7, 9, -1, -7, -8, 0, 6, 0, 0, -4 } void prima_dispari_poi_pari (int v[], int dim)
{
int contatore_scambi, i;
do {
contatore_scambi = 0;
/* per ogni elemento del vettore (fino al penultimo) */
for (i = 0; i < dim-1; i++) {
/* se elemento[i+1] e` dispari e elemento[i] e` pari scambia elemento[i] ed elemento[i+1] */
if (v[i+1] % 2 != 0 && v[i] % 2 == 0) {
swap (&v[i], &v[i+1]);
contatore_scambi++;
} }
} while (contatore_scambi > 0); /* while (e` stato effettuato almeno uno scambio) */
return;
}
Si scriva la funzione prima_mutipli_di_tre_poi_altri che riceve come argomenti un vettore di interi e la sua dimensione e sposta nel vettore tutti i numeri multipli di tre prima degli altri. Non è consentito utilizzare un vettore temporaneo.
Suggerimento: si utilizzi una versione modificata dell’algoritmo bubblesort in cui lo scambio avviene se l’elemento corrente del vettore è positivo o nullo e quello successivo è negativo. Si assuma già disponibile la funzione void swap (int *pa, int *pb).
Esempio: { 5, 3, -8, 0, 1, 6, 7, 9, 0, -1, -7, 0, -4} → { 3, 0, 6, 9, 0, 0, 5, -8, 1, 7, -1, -7, -4 }
void prima_multipli_di_tre_poi_altri (int v[], int dim) {
int contatore_scambi, i;
do {
contatore_scambi = 0;
/* per ogni elemento del vettore (fino al penultimo) */
for (i = 0; i < dim-1; i++) {
/* se elemento[i+1] e` multiplo di tre e elemento[i] no scambia elemento[i] ed elemento[i+1] */
if (v[i+1] % 3 == 0 && v[i] %3 != 0) {
swap (&v[i], &v[i+1]);
contatore_scambi++;
} }
} while (contatore_scambi > 0); /* while (e` stato effettuato almeno uno scambio) */
return;
}
Si scriva la funzione prima_zeri_poi_altri che riceve come argomenti un vettore di interi e la sua dimensione e sposta nel vettore tutti i valori nulli prima degli altri. Non è consentito utilizzare un vettore temporaneo.
Suggerimento: si utilizzi una versione modificata dell’algoritmo bubblesort in cui lo scambio avviene se l’elemento corrente del vettore è diverso da zero e quello successivo è zero. Si assuma già disponibile la funzione void swap (int
*pa, int *pb).
Esempio: { 5, 3, -8, 0, 1, 6, 7, 9, 0, -1, -7, 0, -4} → { 0, 0, 0, 5, 3, -8, 1, 6, 7, 9, -1, -7, -4 } void prima_zeri_poi_altri (int v[], int dim)
{
int contatore_scambi, i;
do {
contatore_scambi = 0;
/* per ogni elemento del vettore (fino al penultimo) */
for (i = 0; i < dim-1; i++) {
/* se elemento[i+1] e` zero e elemento[i] non e` zero scambia elemento[i] ed elemento[i+1] */
if (v[i+1] == 0 && v[i] != 0) {
swap (&v[i], &v[i+1]);
contatore_scambi++;
} }
} while (contatore_scambi > 0); /* while (e` stato effettuato almeno uno scambio) */
return;
}
Esercizio 8 (3 punti)
Quanto byte occupano i seguenti dati?
char dato; _____________ 1 char dato[2]; _____________ 2
"ciao" _____________ 5
"" _____________ 1
"0" _____________ 2
"\n" _____________ 2 '0' _____________ 1 '\n' _____________ 1 '\0' _____________ 1
Esercizio 9 (4 punti)
Si scriva la funzione prossimo_anno_bisestile che restituisce il primo anno bisestile successivo a quello passato come argomento. Si ricorda che un anno è bisestile se divisibile per 4 ma non per 100, oppure per 400.
int prossimo_anno_bisestile (int anno) {
do {
anno++;
} while (!bisestile(anno));
return anno;
}
int bisestile (int anno) {
if ( ( ((anno % 4) == 0) && ((anno % 100) != 0) ) || ((anno % 400) == 0) ) return 1;
else
return 0;
}
Si scriva la funzione ultimo_anno_bisestile che restituisce l’ultimo anno bisestile precedente a quello passato come argomento. Si ricorda che un anno è bisestile se divisibile per 4 ma non per 100, oppure per 400.
int ultimo_anno_bisestile (int anno) {
do {
anno--;
} while (!bisestile(anno));
return anno;
}
int bisestile (int anno) {
if ( ( ((anno % 4) == 0) && ((anno % 100) != 0) ) || ((anno % 400) == 0) ) return 1;
else
return 0;
}
Esercizio 10 (4 punti)
La funzione int fibo_plus_plus (int n) calcola il termine di indice n di una variante della successione di Fibonacci, definita come indicato nel riquadro. Si assuma che la funzione sia sempre chiamata con n ≥ N.
In pratica, per i primi N valori è sufficiente memorizzare in un vettore di dimensione N gli indici degli elementi del vettore stesso, per i successivi è necessario calcolare la somma del contenuto del vettore e, successivamente, scalarne gli elementi di una posizione rimpiazzando l’ultimo con il valore della successione appena calcolato.
Nell’implementazione riportata nel seguito alcune istruzioni sono presentate in più versioni. Si indichi quali sono quelle corrette.
#define N 20
int fibo_plus_plus (int n) {
int i, cnt, f, v[n];
/* inizializza il vettore */
for (i = 0; i <= N; i++) v[i]=i;
for (cnt = N; cnt <= n; cnt++) {
f = somma_vettore (v[], N);
scala_vettore (v[], N);
v[N-1] = f;
}
return f;
}
void scala_vettore (int v[], int n) {
int i;
for (i = 0; i <= n; i++) v[i-1] = v[i];
return;
}
int somma_vettore (int v[], int n) {
int i, somma = 0;
for (i = 0; i <= n; i++) somma =+ v[i];
return somma;
}
Dato un intero N > 0,
altrimenti F
N n se i
F n
N n i
n N
i
n 1
1
0
#define N 20
int fibo_plus_plus (int n) {
int i, cnt, f, v[N];
/* inizializza il vettore */
for (i = 0; i < N; i++) v[i]=i;
for (cnt = N; cnt <= n; cnt++) {
f = somma_vettore (v, N);
scala_vettore (v, N);
v[N-1] = f;
}
return f;
}
void scala_vettore (int v[], int n) {
int i;
for (i = 1; i < n; i++) v[i-1] = v[i];
return;
}
int somma_vettore (int v[], int n) {
int i, somma = 0;
for (i = 0; i < n; i++) somma += v[i];
return somma;
}