Compito di esame 2 luglio 2003

Primo esercizio

Testo

Scrivere una funzione che riceve come parametro una lista e trova la posizione in cui la somma degli elementi dalla posizione in poi è di valore massimo.

Per esempio, nella lista 4 7 5 3 il valore da calcolare è 1, dato che la somma massima si ottiene prendendo tutti gli elementi. Nella lista 4 -9 3 -6 2 -1 il valore da restutuire è 5, dal momento che la somma massima si ottiene sommando gli elementi a partire dal quinto (infatti 2-1=1, mentre tutte le altre somme hanno valore minore: -6 +2 -1=-5, 3 -6 +2 -1=-2 ecc.

Nel caso in cui ci siano più posizioni ``massime'' nella lista (es. nella lista 0 0 0 -2 -1 le tre posizioni 1 2 e 3 danno la stessa somma) si restituisca una di queste posizioni.

Valutazione per questo esercizio:

• 6 punti per algoritmo con raffinamenti
• 6 punti per la descrizione a parole dei raffinamenti
• 6 punti per il codice finale

Driver e file di prova

int posizioneMaxSomma(TipoLista)

Il nome del file che contiene la lista che viene passata alla funzione va dato da linea di comando (da prompt dei comandi, si fa 2lug03-driver nomefile, mentre dal TurboC si può impostare il nome del file nel menu Run->Arguments). Alcuni possibili file di prova, con i valori che devono risultare, sono i seguenti:

Soluzione

Il problema richiede il calcolo della posizione in una la cui somma da quel punto in poi è massima. Si tratta quindi di trovare la posizione di un elemento massimo, cosa che si può fare con il solito algoritmo:

si assume che il massimo elemento sia il primo
per ogni elemento della lista:
  controlla se l'elemento e' maggiore del massimo

Una versione più completa di questo algoritmo si ottiene notando che i dati di cui abbiamo bisogno sono il valore della somma e quello della posizione dell'elemento massimo.

il massimo elemento e' il primo
per ogni elemento della lista:
  se e' maggiore del massimo:
    aggiorna il valore del massimo
    aggiorna la posizione del massimo

Fino a questo momento, l'algoritmo non dipende dal tipo di metrica usata; in altre parole, lo stesso algoritmo è corretto anche per il calcolo del massimo valore in una lista. Questa funzione si realizza facilmente come segue:

int posizioneMax(TipoLista l) {
  TipoLista s;
  int maxVal, maxPos;
  int pos;

  if(l==NULL)
    return 0;

  maxVal=l->val;
  maxPos=1;

  s=l->next;
  pos=2;

  while(s!=NULL) {
    if(s->val>maxVal) {
      maxVal=s->val;
      maxPos=pos;
    }

    pos++;
    s=s->next;
  }

  return maxVal;
}

La funzione da realizzare differisce da questa soltanto per il fatto che va cercato l'elemento di massima somma, e non l'elemento il cui valore s->val è massimo. Per realizzare questa funzione ci basta scrivere una seconda funzione di calcolo della somma (vista a lezione), e poi sostituire a s->val il valore di ritorno di questa funzione:

int posizioneMaxSomma(TipoLista l) {
  TipoLista s;
  int maxSomma, maxPos;
  int somma, pos;

  if(l==NULL)
    return 0;

  maxSomma=sommaLista(l);
  maxPos=1;

  s=l->next;
  pos=2;

  while(s!=NULL) {
    somma=sommaLista(s);
    if(somma>maxSomma) {
      maxSomma=somma;
      maxPos=pos;
    }

    pos++;
    s=s->next;
  }

  return maxPos;
}

La soluzione dell'esercizio si ottiene quindi usando una funzione già vista (la somma degli elementi di una lista) e modificando un algoritmo noto (il calcolo della posizione di un elemento massimo).

Secondo esercizio

Testo

Illustrare il metodo di progettazione delle funzioni ricorsive, usando un esempio. Punteggio massimo per questo esercizio: 6 punti.

Soluzione

Non si riporta qui il metodo di progettazione delle funzioni ricorsive. Si nota soltanto che il concetto fondamentale era quello di assumere che una chiamata alla funzione stessa, se fatta su un problema più semplice, è corretta.

Non era invece richiesta la spiegazione di quello che succede in memoria quando si chiama una funzione ricorsiva. Le risposte in cui veniva invece spiegato solo questo sono state considerate nulle.

Terzo esercizio

Testo

Dire cosa succede quando viene chiamata la seguente funzione.

void Modifica(TipoLista l) {
  if(l!=NULL)
    l->val=0;
  l=malloc(sizeof(struct NodoLista));
  l->val=0;
  l->next=l;
}

Usare figure se necessario. Il punteggio massimo per questo esercizio sarà di 6 punti.

Soluzione

Se la lista passata non è vuota, nel campo val del primo elemento viene scritto il valore 0.

Indipendentemente dal valore iniziale della lista, viene creata una struttura in cui vengono scritti il valore 0 e il valore di l, per cui la struttura contiene come secondo elemento il proprio indirizzo.

Soltanto la prima modifica risulta visibile nella funzione chiamante, mentre la prima comporta soltanto la perdita di una zona di memoria allocata ma non più accessibile.