
DIPARTIMENTO DI INFORMATICA Università di Torino

ESERCIZI CON SOLUZIONE - ultimo aggiornamento 11/03/02

ATTENZIONE: si consiglia di

PRIMA provare a fare questi esercizi;
POI, per ogni esercizio svolto, leggere con attenzione l'elenco degli "errori frequenti" relativo a quell'esercizio, riesaminando la propria soluzione per vedere se contiene errori;
INFINE confrontare la propria soluzione con la soluzione fornita dal docente.

ELENCO DEGLI ESERCIZI

(DAL PRIMO COMPITINO)
Definire una funzione C (ITERATIVA) che riceva come parametri una lista L e un intero z, e restituisca la somma dei nodi di L, escluso l'ultimo nod, minori o uguali di z. Specificare asserzione iniziale, asserzione finale, e invariante di ciclo. Dare la complessita' in tempo della funzione, motivando la risposta.
```
Esempio: L: 4 -> 8 -> 4 -> 4 -> 9 -> 7 -> 2 -> 1
         z: 7
         Risultato: 21 (4+4+4+7+2)

Esempio: L: 4 -> 8 -> 4 -> 4 -> 9 -> 7 -> 2 -> 8
         z: 7
         Risultato: 21 (4+4+4+7+2)
```
(DAL PRIMO COMPITINO)
Definire una funzione C (ITERATIVA) che riceva come parametri due liste L1 ed L2 di interi e restituisca una nuova lista R (si utilizzi la funzione newnode) costruita nel seguente modo:
- R contiene (nell'ordine) una copia del primo nodo di L1 seguita da una copia del primo nodo di L2, una copia del secondo nodo di L1 seguita da una copia del secondo nodo di L2, una copia del terzo nodo di L1 seguita da una copia del terzo nodo di L2, e cosi' via (quando una delle due liste finice, i nodi della lista che non e' finita sono copiati in coda ad R).
La funzione deve lasciare le due liste L1 ed L2 di input invariate. Specificare asserzione iniziale, asserzione finale, e invariante di ciclo. Dare la complessita' in tempo della funzione, motivando la risposta.
```
Esempio:   L1: 4 -> 8 -> 6 -> 2 -> 6 -> 0 -> 8
           L2: 7 -> 5 -> 9 -> 9 -> 1
Risultato: R:  4 -> 7 -> 8 -> 5 -> 6 -> 9 -> 2 -> 9 -> 6 -> 1 -> 0 -> 8
```

(DAL PRIMO COMPITINO)
Definire una funzione C (RICORSIVA) che riceva come parametro un array di interi A, due indici low e high, e restituisca il prodotto degli elementi di A[low...high] diversi da 0. Specificare asserzione iniziale e asserzione finale. Dare la complessita' in tempo e in spazio della funzione, motivando la risposta.

Esempio:       A:    9, 7, 3, 0, 3, 6, 9, 8
               low:  2
               high: 5
Risultato:     36 (=3*3*6)

Esempio:       A:    9, 7, 3, 1, 3, 6, 9, 8
               low:  4
               high: 3
Risultato:     0 (= elemento neutro del prodotto)

Esempio:       A:    9, 0, 0, 0, 0, 0, 0, 8
               low:  2
               high: 5
Risultato:     0 (= elemento neutro del prodotto)

(DAL SECONDO COMPITINO)
Data una lista di interi L1, definire (in C) una funzione RICOSIVA DI CODA (tail) che restituisca in output una nuova lista (si utilizzi la funzione newnode) che contiene (un duplicato di) tutti i nodi di L1 in ordine inverso. Si discuta la complessita' in spazio e tempo di tale funzione.
```
Esempio
     L1:        3 -> 1 -> 3 -> 5 -> 6 -> 9 -> 8
     Risultato: 8 -> 9 -> 6 -> 5 -> 3 -> 1 -> 3
```
(DAL SECONDO COMPITINO)
Date due liste di interi L1 e L2 ordinate (in ordine crescente) che non contengono elementi duplicati, definire (in C) una funzione RICORSIVA non necessariamente di coda (non necessariamente tail) che restituisce in output una nuova lista (si utilizzi la funzione newnode) che contiene (un duplicato di) tutti i nodi che occorrono sia in L1 che L2. Si discuta la complessita' in spazio e tempo di tale funzione.
```
Esempio 
     L1:        3 -> 4 -> 5 -> 7 -> 8 -> 9 -> 14
     L2:        0 -> 1 -> 2 -> 3 -> 5 -> 9 -> 10 -> 12 -> 14 -> 16
     Risultato: 3 -> 5 -> 9 -> 14
```

SOLUZIONE DEGLI ESERCIZI

Esercizio 1

Errori frequenti

Non considerare il caso in cui L e' la lista vuota.

Soluzione

/*
  AI: l contiene una lista di interi L, 
      z contiene un intero Z
  AF: Restituisce la somma dei nodi di L, escluso l'ultimo, che sono <= N
      (L non e' modificata)
*/
int e1 (node * l)
{
   int s = 0;

   if (l == NULL) return 0;

   /* 
      IC: l != NULL
           AND
          s == somma dei nodi di L <= Z, 
               dal primo fino a quello puntato da l escluso 
   */
   while (l->next != NULL) 
   {
      if (l->data <= z) s += l->data;
      l = l->next;
   }
  
   return s;
}

Esercizio 2

Errori frequenti

Relativamente alla prima soluzione: non considerare il caso in cui, dopo il primo ciclo while, la lista che contiene il risultato e' ancora vuota.

Una prima soluzione

/*
  AI: l1 e l2 sono due liste di interi L1 e L2 
  AF: Restituisce una nuova lista che contiene 
      la "fusione alternata" di L1 e L2,
      OVVERO:
      contiene (nell'ordine)
      una copia del primo nodo di L1
      seguita da
      una copia del primo nodo di L2,
      una copia del secondo nodo di L1
      seguita da
      una copia del secondo nodo di L2,
      e cosi' via (quando una delle due liste finisce, seguono le copie
      dei nodi della lista che non e' finita).
      L1 e L2 non sono modificate.
*/
node *e2i (node *l1, node *l2)
{
    node *head = NULL;
    node *tail = NULL;
    node *temp = NULL;

    /* 
       IC:  la sottolista S1 di L1 composta 
               dai nodi dal primo fino al nodo puntato da l1 (escluso),
               e
            la sottolista S2 di L2 composta 
               dai nodi dal primo fino al nodo puntato da l1 (escluso),
            hanno lo stesso numero di nodi;

            la lista head contiene la "fusione alternata" (delle copie)  
               dei nodi di S1
               e
               dei nodi di S2 

            tail contiene il puntatore all'ultimo nodo della lista head
             
    */
    while ((l1 != NULL) && (l2 != NULL))
    {
       temp = newnode();
       temp->data = l1->data;
       temp->next = newnode();
       temp->next->data = l2->data;
       temp->next->next = NULL;

       if (head == NULL) head = temp; 
       else tail->next = temp;

       tail = temp->next;  

       l1 = l1->next;
       l2 = l2->next;
    } 

    while (l1 != NULL)
    {
       temp = newnode();
       temp->data = l1->data;
       temp->next = NULL;

       if (head == NULL) head = temp; 
       else tail->next = temp; 

       tail = temp; 

       l1 = l1->next;
    }
    
    while (l2 != NULL)
    {
       temp = newnode();
       temp->data = l2->data;
       temp->next = NULL;

       if (head == NULL) head = temp; 
       else tail->next = temp; 

       tail = temp; 

       l2 = l2->next;
    }

    return head;   
}

La complessita' in tempo di questa funzione e' lineare nella somma delle lunghezze di L1 e L2.
Giustificazione:

Se L1 e L2 sono vuote non si entra in nessun ciclo.
Ad ogni iterazione del primo ciclo while si passa ad un nodo successivo di L1 e di L2. (Quando si esce dal ciclo almeno una delle due liste e' stata scandita completamente. Quindi alpiu' uno solo dei due cicli che seguono fara' almeno un'iterazione.)
Ad ogni iterazione del secondo ciclo while si passa ad un nodo successivo di L1.
Ad ogni iterazione del terzo ciclo while si passa ad un nodo successivo di L2.

Una seconda soluzione (PIU' COMPLICATA, MEGLIO LA PRIMA)

/*
  AI: l1 e l2 sono due liste di interi L1 e L2 
  AF: Restituisce una nuova lista che contiene 
      la "fusione alternata" di L1 e L2,
      OVVERO:
      contiene (nell'ordine)
      una copia del primo nodo di L1
      seguita da
      una copia del primo nodo di L2,
      una copia del secondo nodo di L1
      seguita da
      una copia del secondo nodo di L2,
      e cosi' via (quando una delle due liste finisce, seguono le copie
      dei nodi della lista che non e' finita).
      L1 e L2 non sono modificate.
*/
node *e2i (node *l1, node *l2)
{
    if (l1 == NULL) && (l2 == NULL)) return NULL;

    node *head = newnode();
    node *tail = head;


    if ((l1 != NULL) && (l2 == NULL)
    {
       head->data -> l1->data;
       l1 = l1->next;
    }
    else if ((l1 == NULL) && (l2 != NULL)
    { 
       head->data -> l2->data;
       l2 = l2->next;
    }
    else
    {
       head->data -> l1->data;
       head->next = newnode();
       tail = head->next;
       tail->data = l2->data;

       l1 = l1->next;
       l2 = l2->next;
    }

    /* 
       IC:  la sottolista S1 di L1 composta 
               dai nodi dal primo fino al nodo puntato da l1 (escluso),
               e
            la sottolista S2 di L2 composta 
               dai nodi dal primo fino al nodo puntato da l1 (escluso),
            hanno lo stesso numero di nodi;

            head != NULL

            la lista head contiene la "fusione alternata" (delle copie)  
               dei nodi di S1
               e
               dei nodi di S2 
               (ATTENZIONE: il campo next dell'ultimo nodo della lista head 
                            deve ancora essere inizializzato)

            tail contiene il puntatore all'ultimo nodo della lista head
    */

    while ((l1 != NULL) && (l2 != NULL))
    {
       node *temp = newnode();
       temp->data = l1->data;
       temp->next = newnode();
       temp->next->data = l2->data;

       tail->next = temp;
       tail = temp->next;

       l2 = l2->next;
       l1 = l1->next;
    }


    while (l1 != NULL)
    {
       tail->next = newnode();
       tail = tail->next;
       tail->data = l1->data;
       l1 = l1->next;
    }
    
    while (l2 != NULL)
    {
       tail->next = newnode();
       tail = tail->next;
       tail->data = l2->data;
       l2 = l2->next;
    }

    tail->next = NULL;
    return head;   
}

La complessita' in tempo di questa funzione e' lineare nella somma delle lunghezze di L1 e L2.
La giustificazione e' identica a quella data per la "prima versione".

Esercizio 3

Errori frequenti

Terminare la ricorsine con il test: low == high, invece che con: low > high.

Soluzione

/*
  AI: a[low..high] e' inizializzato 
  AF: Restituisce il prodotto degli elementi, diversi da 0, di a[low..high]
*/

int es3 (int a[], int low, int high)
{
   if (low > high) return 1;
   else if (a[low] != 0) return a[low] * es3(a,low+1,high);
   else return es3(a,low+1,high);
}

La complessita' in tempo di questa funzione e' lineare in (high-low+1). Giustificazione ad ogni richiamo ricorsivo la lunghezza della porzione di array da considerare diminuice di 1.
Anche la complessita' in spazio di questa funzione e' lineare in (high-low+1).

Esercizio 4

Errori frequenti

Confondere aspetti della prima e della seconda soluzione. Ad esempio:

Nella prima soluzione: omettere il ramo "then" dell'if, evitando quindi di ritornare un valore al termine della ricorsione.
Nella seconda soluzione: sbagliare il passaggio del parametro pr nella chiamata ricorsiva (ad esempio scrivendo &pr invece di pr).

Una prima soluzione

/*
  AI: l contiene una lista di interi L
  AF: Restituisce una lista cho contiene gli elementi di L in ordine inverso
      (L non e' modificata)
*/
node *e4i(node *l)
{
   return e4iAUX(l,NULL);
}

/*
  AI: l contiene una lista di interi L,
      r contiene una lista di interi R
  AF: Restituisce una lista cho contiene gli elementi di L in ordine inverso,
      seguiti dagli elementi di R
*/
node *e4iAUX(node *l, node *r)
{
   if (l ==NULL) return r
   else
   {
      node *temp = newnode();
      temp->data = l->data;
      temp->next = r;
      return e4iAUX(l->next, temp);
   }
}

Una seconda soluzione

/*
  AI: l contiene una lista di interi L
  AF: Restituisce una lista che contiene gli elementi di L in ordine inverso
      (L non e' modificata)
*/
node *e4ii(node *l)
{
   node *r = NULL;
   e4iiAUX(l,&r);
   return r;
}

/*
  AI: l contiene una lista di interi L,
      *pr contiene una lista di interi R
  AF: *pr contiene gli elementi di L in ordine inverso,
      seguiti dagli elementi di R
*/
void e4iiAUX(node *l, node **pr)
{
   if (l !=NULL) 
   {
      node *temp = newnode();
      temp->data = l->data;
      temp->next = *pr;
      *pr = temp;
      e4iiAUX(l->next, pr);
   }
}

Esercizio 5

Errori frequenti

Confondere aspetti della prima soluzione e della seconda soluzione.

Una prima soluzione

/*
  AI: l1 e l2  contengono due liste di interi L1 e L2 ordinate (in ordine
      crescente) senza ripetizioni
  AF: Restituisce una lista ordinata (in ordine crescente) senza ripetizioni 
      che contiene gli elementi comuni ad L1 e L2
*/
node *e5i(node *l1, node *l2)
{
   if ((l1 == NULL) || (l2 == NULL)) return NULL;
   else if (l1->data == l2->data)
   {  
      node *l3 = newnode();
      l3->data = l1->data;
      l3->next = e5i(l1->next,l2->next);
      return l3;
   }
   else if (l1->data < l2->data)
      return e5i(l1->next,l2);
   else
      return e5i(l1,l2->next);
}

La complessita' in tempo e in spazio e', nel caso peggiore, uguale alla somma delle due liste. Tale caso si verifica ad esempio quando le due liste hanno la lunghezze molto vicine e gli elementi sono "alternati" (ad es. L1: 1 -> 3 ->5 -> 7, e L2: 2 -> 4 -> 6 -> 8): ad ogni richiamo ricirsivo si avanza di un nodo su una sola delle due liste.

Una seconda soluzione (RICORSIVA DI CODA)

/*
  AI: l1 e l2  contengono due liste di interi L1 e L2 ordinate (in ordine
      crescente) senza ripetizioni
  AF: Restituisce una lista ordinata (in ordine crescente) senza ripetizioni 
      che contiene gli elementi comuni ad L1 e L2
*/
node *e5ii(node *l1, node *l2)
{
     return e5iAUX(l1,l2,NULL,NULL);
}

/*
  AI: l1 e l2  contengono due liste di interi L1 e L2 ordinate (in ordine
      crescente) senza ripetizioni,
      *head e *tail sono i puntatori alla testa e alla coda di una lista L3
  AF: Restituisce la lista otttenuta concatenando L3 e la
      lista ordinata (in ordine crescente) senza ripetizioni 
      che contiene gli elementi comuni ad L1 e L2
*/
node *e5iiAUX(node *l1, node *l2, node *head, node *tail)
{
   if ((l1 == NULL) || (l2 == NULL)) return head;
   else if (l1->data == l2->data)
   {  
      node *temp = newnode();
      temp->data = l1->data;
      temp->next = NULL;

      if (head == NULL) head = temp;
      else tail->next = temp;
      
      tail = temp;

      e5iiAUX(l1->next,l2->next,head,tail);
   }
   else if (l1->data < l2->data)
      e5iiAUX(l1->next,l2,head,tail);
   else
      e5iiAUX(l1,l2->next,head,tail);
}

[Ferruccio Damiani - DIDATTICA] [Corsi di Studi in Informatica]


	Last update: Mar 11, 2002