Table of Contents
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 n1 e n2 si inizializza un array di k+1 elementi indicizzati da 0 a n2 - n1 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 n1 a n2
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.