Luglio 2018 Archive

Tema

Descrivere un algoritmo che, dati n numeri interi compresi nell’intervallo da 0 a k, svolga un’analisi preliminare del suo input e poi risponda nel tempo O(1) a qualsiasi domanda su quanti degli n interi ricadono nell’intervallo [a..b] con a e b interi. Il vostro algoritmo dovrebbe impiegare un tempo È(n+k) per l’analisi preliminare.

Svolgimento

Nota: descrivere = scrivere.

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

#define N_ELEMENTS 20
#define MAX_ABS_VALUES 50

int *prepare(int values[], int size, int *min, int *max) {
	int i;
	int * aux;
	if(size == 0) {
		return NULL;
	}
	*min = values[0];
	*max = values[0];
	for(i = 0; i < size; i++) {
		if(values[i] < *min) *min = values[i]; if(values[i] > *max) *max = values[i];
	}
	aux = malloc(sizeof(int) * (*max - *min + 1));
	for(i = 0; i < *max - *min + 1; i++) aux[i] = 0;
	for(i = 0; i < size; i++) {
		aux[values[i] - (*min)]++;
	}
	for(i = 1; i < *max - *min; i++) aux[i] = aux[i] + aux[i-1];
	return aux;
}


int main(int argc, char *argv[])
{
	int *values; // contiene i valori non ordinati
	int min; // il valore più piccolo
	int max; // il valore più grande
			 // la dimensione del vettore di appoggio è data da min - max
	int *aux; // l'array ausiliario dell'integer sort
	int i;
	int da, a; // il minimo e massimo tra i valori chiesti all'utente
	int ind_da, ind_a; // gli indici più vicini a da e a
	
	values = malloc(sizeof(int) * N_ELEMENTS);
	srand(time(0));

	for(i = 0; i < N_ELEMENTS; i++)
		values[i] = rand() % (MAX_ABS_VALUES * 2) - MAX_ABS_VALUES;

	aux = prepare(values, N_ELEMENTS, &min, &max);

	for(i = 0; i < max - min; i++) printf("%d: %d\t", i+min, aux[i]);

	printf("\nInserire il primo elemento: ");
	scanf("%d", &da);
	printf("Inserire il secondo elemento: ");
	scanf("%d", &a);

	if(a - da < 0) { a = da+a; da = a-da; a = da-a;} // scambio gli elementi se a < da

	printf("La quantità di numeri compresi tra %d e %d e' %d\n", da, a, (a>=max?aux[max-min-1]:aux[a-min]) - (da<=min?0:aux[da-min-1]));

	system("PAUSE");
	return 0;
}

Commento all'algoritmo

L'algoritmo è una variante dell'integer sort.

Dati n numeri compresi tra n₁ e n₂ si inizializza un array di k+1 elementi indicizzati da 0 a n₂ - n₁ e inizializzati a zero.

Esempio (vettore n):

6

-7

5

-1

8

0

4

-2

-8

3

Per ogni elemento in n si incrementano gli indici corrispondenti come nell'integer sort:

Esempio (vettore k):

Ind:	-8	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8
Val:	1	1	0	0	0	0	1	1	1	0	0	1	1	1	1	0	1

poi si cumula la somma da n₁ a n₂

Ind:	-8	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8
Val:	1	2	2	2	2	2	3	4	5	5	5	6	7	8	9	9	10

Questo richiede ancora un costo Θ(n+k).

In tempo O(1) si estrae l'elemento precedente di A (o zero se A è il primo) e si sottrae all'elemento B.

Esempio:

A = -2

B = 3

k[A-1] = 3

k[B] = 5

k[B] - k[A-1] = 2

Se A o B sono rispettivamente minore del più piccolo e maggiore del più grande è sufficiente considerare il primo e l'ultimo elemento.

Come richiesto, il tempo di preparazione è Θ(n+k) e quello di consultazione è O(1).

Commento al codice

Si è deciso di separare la procedura principale (il tema d'esame) da quella di appoggio, contenente l'inizializzazione e le richieste all'utente.

La chiamata prevede il ritorno di tre valori: l'array k e il minimo e il massimo. Questi due valori sono due int nella procedura di appoggio, che sono passati come puntatori alla procedura principale.

Due costanti indicano la dimensione dell'array e l'intervallo di numeri che è possibile inserire in senso assoluto (es. 5 => da -5 a +5) ottenendo un intervallo di n*2+1 valori.

Nella procedura principale, i valori di minimo e massimo vanno inizializzati con uno dei valori dell'array, poi con un ciclo si valuta se abbassare il minimo o alzare il massimo.

È necessario anche inizializzare i valori dell'array k a zero, perché c'è una probabilità non nulla che alcuni valori non compaiano mai (soprattutto se |n| è piccolo e |k| è grande).

Rispetto all'integer sort è necessario un ulteriore ciclo per calcolare il valore cumulato, che però non ha impatti sul costo asintotico.

Nella procedura principale, a parte il popolamento dell'array con valori casuali, è degno di nota il sistema per gestire la richiesta di valori minori del minimo o maggiori del massimo, che per sintesi è reso con l'utilizzo di operatori ternari.