ESERCIZI CON SOLUZIONE - ultimo aggiornamento 04/09/02

• 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

1. (DAL COMPITO DELLO 08/07/02)
   Definire una funzione iterativa che, date due liste di interi L1 ed L2 (ordinate in ordine STRETTAMENTE crescente), restituisce in output 1 se i numeri contenuti nella seconda lista sono un sottoinsieme dei numeri contenuti nella prima lista, 0 altrimenti (ATTENZIONE: si definisca una funzione "ottimizzata" che sfrutti l'ipotesi di ordinamento). Si descriva l'invariante di ciclo. Si descriva inoltre la complessita' in tempo della funzione.

   Es.         
               L1: 2 -> 5 -> 8 >11
               L2: 5 -> 11
               Output:  1
   
               L1: 2 -> 5 -> 8 -> 11
               L2: 5 -> 7 -> 8
               Output: 0
   
   

2. (DAL COMPITO DELLO 08/07/02)
   Si definisca una funzione ricorsiva che svolga il compito descritto al punto (1). Si discuta la complessita' in spazio e tempo della funzione. Si dica inoltre se la ricorsione utilizzata e' di coda (tail) o no, motivando la risposta.

SOLUZIONE DEGLI ESERCIZI

Esercizio 1

Errori frequenti

Soluzione

/*
  AI: l1 contiene una lista di interi L1 ordinata in ordine STRETTAMENTE crescente, 
      l2 contiene una lista di interi L2 ordinata in ordine STRETTAMENTE crescente 
  AF: Restituisce:
       1, se i numeri contenuti in L2 sono un sottoinsieme dei numeri contenuti in L1 
       0, altrimenti
*/
int ese1 (node * l1, npde *l2)
{
   /* 
      IC: i nodi di L2 dal primo fino al nodo puntato da l2 ESCLUSO
          sono un sottoinsieme 
          dei nodi di L1 dal primo fino al nodo puntato da l1 ESCLUSO
   */
   while ((l1 != NULL) && (l2 != NULL))
   {
      if (l1->data == l2->data) {
         l1 = l1->next;
         l2 = l2->next;
      } 
      else if (l1->data < l2->data)
         l1 = l1->next;
      else
         return 0;
    }
    return (l1 == NULL);
} 

• Se L1 e' vuota non si entra nel ciclo.
• Ad ogni iterazione del ciclo while si passa ad un nodo successivo di L1.

Esercizio 2

Errori frequenti

...
return 0;
if (l1->data > l2->data) ...

...
if (l2 == NULL) return 0;
else return 1;
if (l1->data > l2->data) ...

Soluzione

/*
  AI: l1 contiene una lista di interi L1 ordinata in ordine STRETTAMENTE crescente, 
      l2 contiene una lista di interi L2 ordinata in ordine STRETTAMENTE crescente 
  AF: Restituisce:
       1, se i numeri contenuti in L2 sono un sottoinsieme dei numeri contenuti in L1 
       0, altrimenti
*/
int ese2 (node * l1, npde *l2)
{
   if (l2 != NULL) return 1;
   else if (L1 == NULL) return 0;
   else if (l1->data == l2->data) return ese2(l1->next,l2->next);
   else if (l1->data < l2->data) return ese2(l1->next,l2);
   else return 0;
} 

• Se L1 e L2 sono vuote non ci sono richiami ricorsivi.
• Ad ogni richiamo ricorsivo si passa ad un nodo successivo di L1.

Per quanto riguarda la complessita' in spazio, valgoo le stesse considerazioni fatte per la complessita' in tempo.

La funzione e' ricorsiva di coda (ogni richiamo ricorsivo e' l'ultima operazione effettuata prima del ritorno del valore [PER MAGGIORE CHIAREZZA SUGGERISCO DI RIPORTARE LA DEFINIZIONE DI FUNZIONE RICIORSIVA DI CODA]). Quindi un compilatore "ottimizzante" potrebbe trasformare la ricorsione di coda in una itezazione, ottenendo una complessita' in spazio costante.