Soluzioni 15/01/2014

Esercizio 2:

Dato un vettore A di interi, esiste un indice del vettore con , tale che vale la proprietà :

Scrivere una funzione che trova il valore dell'indice ed il valore e lo stampa.

Soluzione:

Qual'è il senso della proprietà P? è chiaro che è l'indice del massimo dell'array, quindi trovarlo è molto semplice: basta effettuare una ricerca lineare. Però P ci dice di più, il vettore non è ordinato ma è formato da due parti ordinate, una crescente, una descrescente, e non solo è massimo, ma possiamo trovarlo con un test locale, che coinvolge solo i suoi vicini. Possiamo quindi scrivere un codice più efficiente se sfruttiamo queste proprietà. In particolare se un indice non soddisfa la proprietà espressa in P per , siamo sicuri di poter escludere una parte consistente del vettore a destra o sinistra di , con un metodo stile ricerca dicotomica (alias bisezione).

Ecco il codice finale dell'implementazione ricorsiva:

int trovak(int l, int h, int v[])
{   
      // k è in [l,h)

      if (h < l) return 0;

      int mid = (l+h)/2;
      printf("test %d\n",mid);

      if (v[mid-1] < v[mid] && v[mid] > v[mid+1])
         return mid;
      else {
          if (v[mid] <= v[mid+1])
              return trovak(mid+1,h,v); // k in [mid+1,h)

          if (v[mid-1] >= v[mid])
              return trovak(l,mid,v);   // k in [l,mid)
          return 0;
      }
}

La struttura della funzione è molto simile a quella vista per la ricerca dicotomica, si comincia escludendo alcune situazioni degeneri sui valori di . Sappiamo generalmente che l'indice sarà sempre contenuto nell'intervallo aperto a destra [l,h) e che quindi sempre. Se h = l+1, allora k=l; quindi l'istruzione alla riga 5 serve più che altro per segnalare un errore se la funzione viene chiamata con parametri errati (cosi come il return di linea 18).

Dato l'intervallo [l,h), estraiamo un valore in questo intervallo, in particolare il valore di mid viene scelto pari al punto centrale, per avere due partizioni (circa) della stessa dimensione. Verifichiamo se per caso mid soddisfa la relazione su indicata dalla proprietà P. Se è cosi, siamo fortunati, abbiamo trovato (righe 10, 11), e finiamo.

In caso contrario l'if della riga 10 non è verificato, quindi è necessariamente vera la sua negazione: applicando De-Morgan, e cambiando il senso dei maggiori/minori si ha: . Questo OR, ci dice che vi sono due casi: nel primo caso (v[mid-1] >= v[mid]) siamo nella parte destra del vettore, quindi siamo sicuri che il valore di è minore di mid, e possiamo cambiare h, nell'altro caso, siamo nella parte sinistra del vettore e possiamo cambiare . Nel testo è richiesto di stampare e , cosa che può essere aggiunta alla funzione, o meglio fatto dal chiamante.

La versione iterativa può essere derivata banalmente.

Appello

ATTENZIONE:

Appello straordinario di Programmazione:

Scritto per fuori corso, data: 19/11 ore 9:00 aula da definire. Se ci sono problemi di conflitto con altri esami segnalate nei commenti, ISCRIZIONE OBBLIGATORIA via email o in commento, con matricola, nome, cognome. Per chi vuole fare orale/presentazione progetto, stessa data, pomeriggio. Confermare partecipazione. Diffondere notizia, please.