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.

Soluzioni 23/06/2011

Esercizio (Sequenza di Solomon-Golomb):


Testo:

La sequenza autodefinente di Solomon-Golomb è l'unica sequenza monotona non decrescente di interi positivi a tale che in a ci sono esattamente elementi di valore 1. Per chiarire, con un esempio, questo è un segmento iniziale della sequenza:

1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 9...

quindi ad esempio vi sono 5 elementi consecutivi pari a 9.

  1. Scrivere una funzione con prototipo:
    void generate(int v[], int n)

    che dato un intero ed un vettore (con numero di elementi ) riempie con i primi elementi della successione.

  2. Scrivere un programma completo che utilizzando la funzione generate e quante altre lo studente ritiene utili, legge dalla linea di comando la matricola del candidato , calcola la radice quadrata approssimata per difetto delle ultime 5 cifre della matricola aumentata di 16, costruisce una matrice 4x4 con i valori: e stampa: la matrice e la somma dei quadrati degli elementi diagonali.

Soluzione (da leggere solo dopo aver provato a svolgere l'esercizio).

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void generate(int v[], int n)
{
	// la sequenza e' definita per i>=1 per comodita
	// ignoriamo il primo elemento del vettore v[0]
	v[0] = 0;
	int i = 1;
	int value = 1;
	do {
		v[i++] = value;    			// scriviamo almeno un valore pari a value
		int count = v[value] - 1;   // value e' ripetuto per v[value]-1 volte
		while (count-- > 0)
			v[i++] = value;
		value++;					// passiamo al successivo.
	} while (i < n);
}

int main(int argc, char *argv[])
{
	if (argc < 2)
	{
		printf("programma matricola\n");
		return 1;
	}

	int m = atoi(argv[1]);
	int	n = sqrt(m % 100000 + 16);
	printf("m = %d\n",m);
	printf("n = %d\n",n);
        // creo un vettore dinamico di dimensione n+2
	int *v = malloc(sizeof(int)*n+2);

	generate(v,n);

	// for (int i=0; i<=n; i++) printf("%d ",v[i]);

	int mat[4][4];
	int count = n;
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			mat[i][j] = v[count--];

	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++)
			printf("%d ", mat[i][j]);
		printf("\n");
	}
	printf("\n");

	int s = 0;
	for (int i=0; i<4; i++)
		s += mat[i][i]*mat[i][i];
	printf("%d\n",s);
        // prima di finire il programma restituiamo la memoria:
    free(v);
	return 0;
}