La versione più recente è stata modificata il 2007-07-13 14:38:32 da GaS
Aggiunzioni:
Soluzione esame Luglio 2007
Il partition del quicksort risulta adatto ai nostri scopi, dobbiamo quindi modificare quello che è il quicksort in maniera da effettuare solo i calcoli che ci necessitano limitando la complessità.
La soluzione trovata risulta essere O(n) in quanto la relazione di ricorrenza per tale algoritmo è:
T(n) = T(n/2) + O(n) per n>1e T(1) = 0
Pseudo-pseudo-codice:
Omissioni:
Soluzione esame Luglio 2007
Il partition del quicksort risulta adatto ai nostri scopi, dobbiamo quindi modificare quello che è il quicksort in maniera da effettuare solo i calcoli che ci necessitano limitando la complessità:
Pseudo-pseudocodice:
La versione più vecchia di questa pagina è stata modificata il 2007-07-13 14:31:46 da GaS []
Vista della pagina:
Soluzione esame Luglio 2007
Dato un insieme
V = (v_0, ..., v_{n-1}) di
n numeri, si definisce
k-mo minimo di V l'elemento
v_j tale che comunque preso v in V_{n-k} si ha che v_j >= v AND v_j < w dove |V_k| = k, |V_{n-k}| = n-k e V = V_k U V_{n-k}.
Si richiede di implementare in linguaggio
C un algoritmo che dato
V, trovi il suo
k-mo minimo (
k dato da input) effettuando nel caso medio O(n) confronti tra numeri.
Si preveda che l'algoritmo possa leggere il vettore V da un file binario che memorizza come primo elemento
n (come intero) e a seguire i valori di V come
double.
Commentare opportunamente il codice implementato.
TRADUZIONE
Dato un insieme con n elementi, trovare il k-mo minimo vuol dire trovare quell'elemento che si trova in posizione k nell'insieme ordinato.
METODO
Dato l'insieme V per trovare il k-mo minimo quello che si deve utilizzare è un algoritmo di tipo "quick-select".
Quello che risulta evidente è che il nostro k-mo minimo è un "pivot" del quicksort, solo che è un pivot fissato!
Il partition del quicksort risulta adatto ai nostri scopi, dobbiamo quindi modificare quello che è il quicksort in maniera da effettuare solo i calcoli che ci necessitano limitando la complessità:
Pseudo-pseudocodice:
K_minimo(S,left,right,k)
if (la cardinalità dell insieme S è > 1) then
begin
i := partition(S,left,right)
if (i = k) then
stampa("Il k-mo minimo é S[k]")
else
begin
if (i<k) then
K_minimo(S,left,i-1,k)
else
K_minimo(S,i+1,right,k)
end
end
else
stampa("Il k-mo minimo é S[k]")
SOLUZIONE GaS
/****************************************************************************/
/* LIBRERIE */
/****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
/****************************************************************************/
/* MACRO */
/****************************************************************************/
#define SWAP(a,b) {void *tmp; tmp = *a; *a = *b; *b = tmp;}
#define COMPARE(a,b) ( (*(double *)a > *(double *)b) )
/****************************************************************************/
/* FORWARD DECLARATIONS */
/****************************************************************************/
int partition(void **S,int l,int r);
void k_minimo(void **v,int l,int r, int k);
/****************************************************************************/
/* MAIN */
/****************************************************************************/
int main()
{
double *V, /* vettore dove carico i double */
**sp; /* puntatore agli elementi del vettore V */
int n, /* numero di elementi del vettore */
i, /* indice di scorrimento */
k; /* k-mo minimo da cercare */
FILE *f;
/* === LETTURA FILE =================================================== */
f = fopen("file.exam","rb");
fread(&n,sizeof(int),1,f);
V = (double *) malloc (n*sizeof(double));
fread(V,sizeof(double),n,f);
fclose(f);
/* ============================================== FINE LETTURA FILE === */
sp = (double **) malloc (n*sizeof(double *)); /* inizializzo il punt a V*/
printf("Vettore V: \n");
for(i=0;i<n;i++){
sp[i] = &V[i]; /* punto l'elemento iesimo del vettore */
printf("%2.2f ",*sp[i]);
} printf("\n");
do{
printf("Inserisci il k-esimo minimo da trovare: ");
scanf("%d",&k);
} while ((k<0) || (k>=n));
k_minimo(sp,0,n-1,k);
return 0;
}
/****************************************************************************/
/* PARTITION */
/****************************************************************************/
int partition(void **S,int l,int r)
{
int i,j;
i = l - 1;
j = r + 1;
for(;;){
while( COMPARE(S[r],S[++i]) );
while( COMPARE(S[--j],S[r]) )
if(j==1) break;
if(i>=j) break;
SWAP(&S[i],&S[j]);
}
SWAP(&S[r],&S[i]);
return i;
}
/****************************************************************************/
/* KAPPESIMO MINIMO */
/****************************************************************************/
void k_minimo(void **v,int l,int r, int k)
{
int i;
if (r<=l){
if(r == k)
printf("Il %d-mo minimo e' %2.2f\n",k,(*(double *) v[k]));
return;
}
i = partition(v,l,r);
if(k == i){
printf("Il %d-mo minimo e' %2.2f\n",k,(*(double *) v[k]));
return;
}
if(k<i)
k_minimo(v,l,i-1,k);
else
k_minimo(v,i+1,r,k);
}
Torna ad Laboratorio di Algoritmi e Strutture Dati
