Lezione di Venerdi' 15/02/02 - ultimo aggiornamento: 19/02/02

Preparazione al primo compitino.

CHE COSA E' STATO FATTO A LEZIONE

Esercizio 1

Definire una funzione C (iterativa) che dati una lista ordinata (ordine decrescente) L ed un intero x, restituisca il numero dei nodi di L maggiori di x. Specificare asserzione iniziale, asserzione finale, e invariante di ciclo. Dare la complessita' in tempo della funzione, motivando la risposta.

Esempio:        L1:  15 -> 11 -> 11 -> 9 -> 9 -> 7 -> 6 -> 4 -> 3 -> 3
                x=7
Risultato:      5

Una soluzione all'esercizio 1

/*
  AI: - l contiene una lista di interi L ordinata in ordine decrescente
      - x contiene un intero X
  AF: Restituisce il numero dei nodi di L maggiori di X
*/
int es1 (node *l)
{
    int c = 0; 

    /* 
       IC: (i nodi di L dal primo fino nodo puntato da l (escluso) somo > X)
             AND
           (c contiene il numero di tali nodi)
    */
    while ((l != NULL) && (l->data > x))
    {
        c++;
        l = l->next;
    }

    return c;   
}

• Ad ogni iterazione del ciclo si passa ad un nodo successivo di L. (Siccome L e' ordinata in ordine decresente, quando si esce e' stata visitata la sola porzione iniziale di L formata da nodi > x). Il corpo del ciclo ha complessita' O(k), dove k e' una costante.

Esercizio 2

Definire in C una funzione (iterativa) che, date in due liste L1 ed L2 di interi, restituisca una nuova lista R1 (si utilizzi la funzione newnode) definita nel seguente modo:

• R1 contiene (nell'ordine) i nodi di L1 che sono maggiori o uguali dei nodi di L2 in posizione corrispondente (o tali che non ci sono nodi in posizione corrispondente in L2).

Esempio:        L1:  8 -> 1 -> 8 -> 5 -> 6 -> 9 -> 8 -> 3 -> 2 -> 11 -> 10
                L2:  8 -> 8 -> 3 -> 8 -> 2 -> 5 -> 6 -> 3 -> 3
Risultato:      R1:  8 ->      8 ->      6 -> 9 -> 8 -> 3      -> 11 -> 10

Una soluzione all'esercizio 2

Per prima cosa scriviamo la funzione usando dello pseudo-codice.

/*
  AI: l1 e l2 contengono due liste di interi L1 e L2
  AF: Restituisce una nuova lista che contiene (nell'ordine) 
      i nodi di  L1 che sono maggiori o uguali 
      dei nodi di L2 in posizione corrispondente 
      (o tali che non ci sono nodi in posizione corrispondente in L2)
*/
node *ese2  (node *l1, node *l2)
{
    node *head = NULL;
    node *tail = NULL;

    /*
       IC:  (la lista head, contiene (nell'ordine)
             i nodi di L1 dal primo fino al nodo puntato da l1 (escluso)
             che sono maggiori o uguali 
             dei nodi di L2 in posizione corrispondente)
            AND
            tail contiene il puntatore all'ultimo nodo della lista head
    */
    while ((l1 != NULL) && (l2 != NULL))
    {
       if (l1->data >= l2->data)
           << COPIA IL NODO IN TESTA AD l1 IN CODA ALLA LISTA head >>

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

    while (l1 != NULL)
    {
     << COPIA IL NODO IN TESTA AD l1 IN CODA ALLA LISTA head >>

     l1 = l1->next;
    }

    return head;  
}

Ora possiamo raffinare lo preudo-codice (si nodi che lo stesso frammento di codice occorre in due punti diversi della funzione).

• Prima versione del codice raffinato

  {
     node *temp = newnode();
     if (head == NULL) head = temp;
                  else tail->next = temp;
     tail = temp;
     tail->data = l1->data;
  }
  

  (volendo, e' possibile dichiarare temp all'inizio della funzione).
• Seconda versione del codice raffinato

  insert(l1->data, &head, &tail);
  

  dove insert e' la funzione:

  /*
    AI: *phead e *ptail sono rispettivamente puntatori al primo e all'ultimo
        nodo di una lista L (se e' e vuota sono entrambi a NULL)
    AF: n e' stato inserito in coda a L 
        (e *phead e *ptail sono stati modificati di conseguenza)
  */
  void insert (int n, node **phead, node **ptail)
  {
     node *temp = newnode();
     if (*ph == NULL) *phead = temp;
                  else (*ptail)->next = temp;
     *ptail = temp;
     (*ptail)->data = n;
  }
  

• Se L1 e' vuota si termina senza entrare nei cicli.
• Ad ogni iterazione del primo ciclo while si passa ad un nodo successivo di L1. (Quando si esce dal ciclo almeno una delle due liste e' stata scandita completamente.) Il corpo del ciclo ha complessita' O(k), dove k e' una costante.
• Ad ogni iterazione del secondo ciclo while si passa ad un nodo successivo di L1. Il corpo del ciclo ha complessita' O(k), dove k e' una costante.

Esercizio 3

Definire una funzione C (ricorsiva) che riceve come parametro un array di interi B, due indici first e last, e restituisce la somma degli elementi di B [first...last]. Specificare asserzione iniziale e asserzione finale. Dare la complessita' in tempo e in spazio della funzione, motivando la risposta.

Esempio:       B:      4, 9, 3, 1, 3, 6, 7, 2
               first = 2
               last  = 5

Risultato:      13

Una soluzione all'esercizio 3

/*
  AI: first e last sono indici validi per b
  AF: Restituisce la somma tutti gli elementi di b[first..last]
*/
int ese3 (int[] b, int first, int last)
{
  if (first > last)
     return 0;
  else
     return b[first]+ese3(b,first+1,last);
}

• Se first > last si la funzione termina.
• Ad ogni richiamo ricosivo first e' amentato di 1 e last e' lasciato invariato.

Una seconda soluzione all'esercizio 3 (con ricorsione di coda)

/*
  AI: first e last sono indici validi per b
  AF: Restituisce la somma tutti gli elementi di b[first..last]
*/
int ese3 (int[] b, int first, int last)
{
  aux(b,first,last,0);
}


/*
  AI: first e last sono indici validi per b, acc e' contiene un intero N
  AF: Restituisce la somma di N e di tutti gli elementi di b[first..last]
*/
int aux (int[] b, int first, int last, int acc)
{
  if (first > last)
     return acc;
  else
     return aux(b,first+1,last,acc+b[first]);
}