26: Let’s code2! (Esercizi tratti da temi d’esame)

Molte persone che si accingono a studiare il linguaggio C per la prima volta sono matricole universitarie che devono sostenere l’esame di informatica. Siccome il modo per capire se si è appreso quanto si è studiato è mettersi alla prova con la pratica, ci sembrava utile provare a svolgere degli esercizi e dare qualche consiglio per affrontare gli esami.

Anzitutto, la regola numero uno per passare gli esami (dopo essere passati sui libri e tentato di capire gli argomenti) è “sfondarsi” di temi d’esame: fatene più che potete(sopratutto se sono strutturati sempre nella stessa maniera)!! In questo modo saprete bene quali sono gli argomenti e potete anche iniziare a capire come gestire il vostro tempo (NON dimenticate di portarvi un orologio all’esame, è di vitale importanza).

I seguenti esercizi sono tratti dai temi d’esame del corso di “Fondamenti di informatica” della facoltà di “Ingegneria Informatica” del Politecnico di Milano. Ricordo che per quanto riguarda la programmazione, ci sono mille modi diversi di arrivare a una soluzione, quindi non è detto che se la vostra soluzione non è la stessa sia sbagiata.

ESERCIZIO 1  (codice binario/esadecimale, virgola fissa e mobile)

a) Indicare la rappresentazione in complemento a 2, utilizzando 10 bit, dei numeri:
A = +59 (base 10)
B = – 81 (base 10)

b) Eseguire la somma A+B in binario dei numeri interi A= -5 e B= -30 codificati in complemento a 2 su 6
bit. Mostrare il risultato in binario prodotto dall’unità aritmetico-logica e indicare quale sia il numero
decimale corrispondente al numero binario prodotto (usare sempre 6 bit). Infine riportare il valore dei
bit di carry (riporto) e di overflow dopo l’operazione dando breve motivazione del valore assegnato.

c) Indicare il valore in base 8 e 16 corrispondente al numero -75 in base 10

d) Indicare quale numero decimale rappresenta la seguente sequenza di bit codificata in complemento a 2:
1111.0110.0010

e)Data la definizione della variabile double v= – 55,6, descrivere la sua rappresentazione in virgola
mobile in base allo standard IEEE754 semplice precisione FP64 descritto a lezione; definire prima il numero nel formato normalizzato intermedio (TRONCARE parte decimale allaterza cifra decimale). Codificare poi il numero normalizzato usando il formato FP64. Indicare quale sia il vero valore (in base 10) descritto dalla sequenza di bit memorizzata in S, M ed E (si consiglia di esprimere la mantissa in termini frazionari).

f) Si consideri l’intervallo di numeri reali compresi tra 1.050.000 e 2.000.000 e la loro codifica in FP64.
Scrivere l’espressione che determina la distanza minima tra due numeri reali (vicini) realmente
rappresentati dalla codifica specificata.
I numeri in questo intervallo sono del tipo 1,xx *220 quindi la variazione del bit meno significativo
(52esimo) comporta una distanza in 1,xx di 2-52 , pertanto la distanza tra i due numeri reali adiacenti sarà?

SOLUZIONE

a) Procediamo eseguendo la divisione della parte intera (quella positiva) del numero per 2
Div1 : 59 / 2 = 29 resto di 1
Div2 : 29 / 2 = 14 resto di 1
Div3 : 14 / 2 = 7 resto di 0
Div4 : 7 / 2 = 3 resto di 1
Div5 : 3 / 2 = 1 resto di 1
Div6 : 1 / 2 = 0 resto di 1
Prendiamo il resto delle divisioni dal basso verso l’alto e il risultato sarà= 111011. Siccome la consegna ci chiede di utilizzare 10 bit, metteremo degli zeri a sinistra: 0000111011.

Stesso procedimento con il numero -81; prendiamo la sua parte intera e cominciamo a dividere per 2
Div1 : 81 / 2 = 40 resto di 1
Div2 : 40 / 2 = 20 resto di 0
Div3 : 20 / 2 = 10 resto di 0
Div4 : 10 / 2 = 5 resto di 0
Div5 : 5 / 2 = 2 resto di 1
Div6 : 2 / 2 = 1 resto di 0
Div7 : 1 / 2 = 0 resto di 1

81 = 1010001 , usando 10 bit diventa 0001010001
Ora, dal momento che il numero che volevamo trasformare era -81 dobbiamo fare il complemento a 2. Ricordatevi il passaggio al complemento a 2 consta di due passaggi:
1) Fare il complemento a 1 dei bit, ovvero, trasformare gli 1 in 0 e gli 0 in 1.(0001110 diventa 1110001)
2) Sommare 1 al risultato ottenuto (1110001 + 1 = 1110010)

Riprendiamo il nostro numero: 0001010001
Facendo il complemento a 1 diventa : 1110101110
Infine sommiamo un 1 : 1110101110 + 0000000001 = 1110101111

b)
111011 A
100010 B
________
(1)011101 Risultato binario
Corrispondente valore decimale (base 10): +29
Il risultato appare sbagliato perchè abbiamo effettuato un troncamento. Infatti il testo ci chiede espressamente di usare solo 6 bit quando in realtà la soluzione ne richiede 7 . Se avessimo avuto a disposizione il settimo bit allora il non ci sarebbe stato il bit di overflow e il risultato sarebbe stato -35.
bit carry: 1
bit overflow: 1
Breve motivazione di carry e overflow:
-carry 1 perché 2 negativi generano sempre riporto nella somma
-overflow perché primo bit operandi discorde da primo bit risultato

c) Prendiamo il modulo di -75 e lo trasformiamo in binario
Div1 : 75 / 2 = 37 resto di 1
Div2 : 37 / 2 = 18 resto di 1
Div3 : 18 / 2 = 9 resto di 0
Div4 : 9 / 2 = 4 resto di 1
Div5 : 4 / 2 = 2 resto di 0
Div6 : 2 / 2 = 1 resto di 0
Div7 : 1 / 2 = 0 resto di 1

75 = 1001011
Per trasformare il numero da binario ad ottale raggruppiamo i bit in gruppi da 3 a partire da destra e se mancano bit a sinistra aggiungiamo degli 0
001 001 011 => 1 1 3
Ricordate che siamo partiti da un numero negativo, quindi = -113 (base 8)
Stessa cosa se vogliamo trasformare il numero da binario ad esadecimale con l’unica differenza che questa volta i gruppi sono fatti da 4 bit.
0100 1011 => 8 F
-75 = -4B (base 16)

d) 1111.0110.0010
Il numero binario ha come primo bit un 1 quindi è un numero negativo. Facciamo il complemento a 2.
0000.1001.1101 + 0000.0000.0001 = 0000.1001.1110
1 * 2^7 + 1 * 2^4 + 1 * 2^3 + 1 * 2^2 + 1 * 2^1 = 158
Quindi il risultato è uguale a -158

e)-1,737 *25
S (1 bit di segno): 1
M (52 bit per la mantissa – fermarsi ai primi 6 bit): 101111
E (11 bit per l’esponente): 10000000100
-55,5

f) 2-52 * 220

ESERCIZIO 2

Siano date le seguenti definizioni
struct el {int numero; int posizione;};
struct din {struct el dati; struct din * prox);
struct din *LIS=NULL; 

Scrivere un programma in C che definisce le seguenti funzioni:
a) La funzione Ricerca che riceve come parametri un numero intero N>=0, una posizione (-1 o un valore
>=0) e il descrittore di un file aperto (di tipo FILE *) che contiene una serie di numeri interi (si
consiglia un file binario). La funzione verifica la correttezza dei parametri e in caso contrario si ferma
e ritorna -1. La funzione cerca nel file il numero N: nel caso in cui pos=-1 la funzione si ferma al
primo che incontra e ritorna, come parametro, l’indirizzo del primo byte che memorizza il numero
trovato nel file. Se la posizione è >= 0 ricerca se esiste nel file il numero N memorizzato all’indirizzo
ricevuto nel parametro posizione e una volta trovato ricerca il prossimo valore N memorizzato nel file
del quale ritorna l’indirizzo del primo byte. Se la ricerca non ha successo per qualsiasi motivo
restituisce -1.
b) La funzione main chiede al terminale di inserire il valore di N finché non viene introdotto un numero >= 0. Poi, utilizzando le precedenti funzioni ricerca nel file FILE.DAT (se non esiste termina
l’esecuzione) tutte le istanze del numero N presenti nel file, estraendone per ognuno la posizione nel
file e inserendo ogni coppia <numero, posizione> nella lista LIS. Se l’inserimento in lista fallisce o
quando tutte le coppie sono state caricate in lista il programma termina la propria esecuzione.
Si supponga che i valori letti al terminale siano numeri interi che non generano overflow.

SOLUZIONE

a) Dopo aver letto attentamente il testo, ragioniamoci su. Il testo ci dice già quali saranno i parametri da dare alla nostra funzione Ricerca. Dovremo scrivere tutti i casi per cui i parametri passati della funzione non siano quelli richiesti, e in tal caso ritornare -1 (fallimento operazione). Dobbiamo trovare il numero N nel file, quindi ci servirà una variabile che ci dica se lo abbiamo trovato, ci serviaranno delle variabili che ci indichino la posizione all’interno del file e una per la lettura. Ovviamente dovremo essere a conoscenza delle operazioni sui file.

 #include <stdio.h> //le mettiamo per completezza
#include <stdlib.h>
struct el {int numero; long int posizione;}; //dati che ci dava già il testo
struct din {struct el dati; struct din *prox;};
struct din *LIS=NULL;

int Ricerca (int N, FILE *id, int pos) //intero, descrittore e posizione, come ci diceva il testo
{
int val; long int newpos; int trovato; //val e trovato le uso per dire se ho trovato N, newpos per la posizione (è in long int)
if (N <0) 
   return -1; //N deve essere >=0
if (pos <-1) 
  return -1; //pos deve essere >=0 oppure =-1
if (id==NULL) 
   RETURN -1; //deve esistere il file!
if (pos==-1) //se pos=-1 la funzione si ferma al primo N che incontra nel file
{ 
   rewind (fp); 
   trovato=0; //ci posizioniamo all'inizio del file
   fread(&val, sizeof(int), 1 , id); //uso la funzione di lettura del file, usando val per trovare N
   while ((!trovato) && (!feof(id))) //finché non lo trovo e non arrivo alla fine del file
   { 
      if (val==N) 
         trovato=1; //se val=N porto a 1 la variabile trovato (ho trovato il numero che cercavo)
      newpos=ftell(id)- sizeof(int); /*calcolo la posizione nel file con la funzione ftell che dice la posizione attuale ma tolgo
                                       la dimensione di un intero */
      fread(&val, sizeof(int), 1 , id); //continuo a leggere
   }
   if (trovato) 
      return newpos; 
   else 
      return -1; //se ho trovato N ritorno la posizione
}
else 
{ //se pos è >=0
   fseek(id, pos, SEEK_SET); //ci spostiamo alla posizione pos
   fread(&val, sizeof(int), 1 , id); //leggo il file
   if (val==N) //se trovo il primo N
   {
      trovato=0; 
      fread(&val, sizeof(int), 1 , id);  //continuo a leggere
      while ((!trovato) && (!feof(id))) //finché non sono alla fine del file o non trovo un altro N
      { 
         if (val==N) //se trovo un altro N
         {
            trovato=1; //metto trovato=1 e calcolo la posizione corrente
            newpos=ftell(id)- sizeof(int); 
         } 
         else 
            fread(&val, sizeof(int), 1 , id); //altrimenti continuo a leggere
      }
      if (trovato) 
         return newpos;  //se trovato=1 ritorno la posizione
      else 
         return -1; //altrimenti ritorno -1
   }
   else 
      return -1;
}
} 

b) Dovremo controllare che il numero inserito sia maggiore di zero, chiedendo all’utente con le oppurtune printf/scanf. Il testo sostanzialmente ci chiede di invocare la funzione che abbiamo creato prima, ci dice anche cosa dobbiamo passare per parametri e dove dobbiamo metterli. Dobbiamo anche essere in grado di inserire un elemento in una lista (nella lista che ci diceva).

 int main()
{ FILE *fd; int N, pos; struct el temp; //usiamo un descrittore, N, posizione e l'elemento della lista
do{ 
   printf("introdurre N"); 
   scanf("%d",&N); 
}while (N<=0); /*finché N è minore di zero
continuiamo a chiedere all'utente di reinserirlo */
fd = fopen("DATI.DAT", "rb"); //apro il file
if (fd==NULL) //se il file è inesistente, scrivo messaggio di fallimento operazione
{ 
   printf("\nErrore nell'apertura del file! "); 
   exit(0); 
}
pos= Ricerca (N, fd, -1); //chiamo la funzione Ricerca
while (pos!=-1) finché pos è diverso da -1 
{ 
   temp.numero= N; temp.posizione=pos ; //inserisco l'elemento nella lista
   pos = Ricerca (N, fd, pos);//continuo a cercare
}
printf("finito"); 
fclose(fd); //ho finito e chiudo il file
} 

ESERCIZIO 3

Scrivere una funzione C chiamata Sposta che riceve come parametro la lista LIST così definita

struct elem {char str[21]; struct elem *next;}; struct elem *LIST=NULL; 

La lista conterrà un numero arbitrario non conosciuto di elementi e dopo l’esecuzione dovrà essere
ritornata, eventualmente modificata, al programma chiamante come parametro.
La funzione legge da terminale una stringa carattere per carattere e termina la lettura quando legge il
carattere ‘\n’; la stringa letta deve essere caricata nella variabile char TEST[21] e se la dimensione della
stringa è superiore a quella della variabile essa deve essere troncata opportunamente.
La funzione poi cerca tutti gli elementi della lista che hanno nel campo str il valore contenuto nella
stringa TEST e li sposta in fondo alla lista. Infine la funziona ritorna, sempre come parametro, il numero
di elementi che sono stati spostati.

SOLUZIONE

Leggiamo attentamente il testo. Dobbiamo scrivere la funzione Sposta che ritorna l’elemento della lista, quindi dovrà essere del tipo “struct elem”. Dovremo passarle la lista e il numero di elementi spostati, passati per indirizzo perché andremo a modificarli.  Dovrò prima chiedere a terminale dei caratteri da mettere nell’array, finchè non inserisco il carattere \n o finché l’array non sarà pieno. Scandirò poi la lista alla ricerca dell’array che ho compilato e sposterò gli elementi che troverò in fondo alla lista. Poi Vediamo allora:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct elem {char str[21];struct elem *next;}; //dato dal testo

struct elem * Sposta(struct elem * l, int *spostati)
{
char TEST[21], c; int i, fine;
struct elem *ultimo = NULL, *tmp = NULL, *coda = NULL, *prec = NULL; //tutte liste di supporto per spostare gli elementi
*spostati = 0;
if (l == NULL || l -> next == NULL)  //se la lista è NULL o è presente un solo elemento non si deve spostare nulla
{ 
   printf("Lista identica"); 
   return l;
}
//altrimenti
fine = 0; 
i=0;
do{
   printf("Carattere (invio per terminare): "); //leggo da terminale tutte le lettere finché non leggo \n
   scanf("%c", &c);
   if (c != '\n') 
   {
      TEST[i] = c; 
      i++; 
      scanf("%c", &c); 
   } // se c!=\n metto la lettera nel vettore TEST
   else 
      fine = 1; //altrimenti incremento fine (che mi serve per stabilire quando finisco)
}while (i < 21 && !fine); //lo faccio fino a che non inserisco \n oppure finché raggiungo la fine del vettore TEST[i] = '\0';  
//aggiungo il carattere terminatore alla stringa //Ricerca e spostamento ultimo = l; 
//posizionamento sull’ultimo elemento della lista iniziale per determinare dove fermare la scansione 
while(ultimo -> next != NULL) 
{ 
   ultimo = ultimo -> next; 
}/*coda indica l’ultimo elemento della lista 
durante l’elaborazione; all'inizio la coda coincide con l'ultimo elemento, ma poi punterà all’ultimo spostato*/
coda = ultimo;
/*tmp serve per scandire la coda dal primo elemento sino al penultimo della
lista originale. L'ultimo non è considerato perché comunque non cambierebbe posizione*/
tmp = l;
while(tmp != ultimo) //finché non arrivo alla fine della lista
{ 
   if (strcmp(tmp->str, TEST) == 0) //strcmp è una funzione che serve per confrontare le stringhe
   {  //sposto l'elemento alla fine della lista
      coda -> next = tmp; //tmp diventa il nuovo ultimo
      coda = coda -> next;
      tmp = tmp -> next; //tmp passa al prossimo
/*l’elemento individuato va eliminato dalla precedente posizione nella lista. Si
hanno due casi: l'elemento era il primo è il primo della lista e quindi va
cambiata la testa di lista oppure è in mezzo e quindi il precedente che puntava
a lui deve ora puntare al prossimo di quello estratto (attualmente puntato da tmp)*/
      if (prec == NULL) 
         l = l -> next; //prec rimane NULL
      else 
         prec -> next = tmp; //prec rimane sull'elemento corrente
         //sistemazione campo next dell'elemento spostato in coda
      coda -> next = NULL; (*spostati)++;
   }//fine spostamento
   else //se elemento non è quello cercato passa al prossimo
   {
      prec = tmp; 
      tmp = tmp -> next;
   }
}//end while
return l; //ritorno la lista
}
int main() {
struct elem *LIST = NULL; int spostati = 0; //inizializzo la lista e l'indice di elementi spostati
LIST = Sposta(&LIST, &spostati);
} 

ESERCIZIO 4

Definire una matrice globale di 20 righe e 10 colonne di interi e scrivere una funzione C chiamata INS
che riceve come parametro la matrice e procede a caricarla riga per riga a partire dalla prima con numeri
richiesti al terminale. Il numero letto da terminale è inserito nella matrice solo se non è uguale ad uno di
quelli già inseriti in precedenza, altrimenti la funzione ne richiede un altro al terminale finchè l’utente
non introduce un numero nuovo.
La funzione poi calcola la somma dei valori memorizzati in ogni colonna e determina quale sia la colonna
con la somma più bassa. Infine la funzione ritorna al programma chiamante, come parametri, la matrice
caricata e l’indice della colonna con la somma più bassa.

SOLUZIONE

Per definire la matrice useremo le define. Chiederemo a terminale i numeri da inserire (mi serviranno due indici per scandire la matrice e una variabile per acquisire il carattere), controllando che non ci siano duplicati (mi servono altri due indici per riscandire la matrice). Infine calcolo la somma della colonna e stabilirò quella più bassa, per farlo avrò bisogno di almeno due variabili, una in cui calcolo la somma e l’altra per confrontarla con i risultati precedenti. Mi servirà anche un’altra variabile per tenere conto dell’indice della colonna.

#include &lt;stdio.h&gt;
#define ROWS 20
#define COLS 10
int INS (int mat[ROWS][COLS]) 
{
int i, j, num, x, y, duplicato, somma, somma_min, j_min;
printf("Inserimento dati nella matrice\n");
for (i = 0; i &lt; ROWS; i++) 
{
   for (j = 0; j &lt; COLS; j++) //per ogni elemento della matrice
      do{
            printf("[%d, %d]: ", i, j); 
            scanf("%d", &amp;num); //chiedo all'utente cosa inserire nella matrice
            duplicato = 0;
            for (x = 0; x &lt;= i &amp;&amp; !duplicato; x++)
               for (y = 0; (x != i || y &lt; j) &amp;&amp; y &lt; COLS &amp;&amp; !duplicato; y++) //riscandisco la matrice
                  if (mat[x][y] == num)
                     duplicato = 1; //se trovo un elemento = a quello che ho inserito, allora ho un duplicato
            if (!duplicato) 
               mat[i][j] = num; //altrimenti lo inserisco nella matrice
            else 
               printf("Numero %d non valido... inserirne un altro\n", num); //se duplicato=1, devo inserire un altro numero
         }while(duplicato == 1);
}//fine primo for
/* il controllo deve avvenire su tutti gli elementi delle righe precedenti quella nella quale 
stiamo caricando il dato e per quella corrente ci si deve invece fermare all’elemento precedente a quello corrente. 
La condizione di controllo dei due for risolve questo problema. Tuttavia è accettabile anche una soluzione che scandisce completamente, 
con un doppio for, le righe precedenti alla riga corrente e infine un for che scandisce la parte necessaria della riga corrente*/
//calcolo la somma della prima colonna e inizializzo il minimo di riferimento.
somma_min = 0;
for (i = 0; i &lt; ROWS; i++) 
   somma_min = somma_min + mat[i][0];
j_min=0;
for (j = 1; j &lt; COLS; j++) 
{
   somma = 0;
   for (i = 0; i &lt; ROWS; i++) 
      somma = somma + mat[i][j];
   if ( somma_min &gt; somma) 
   { 
      j_min = j; 
      somma_min = somma;
   }
}
return j_min;
} 
Please follow and like us: