problema nella richiesta di un esercizio

[dennis87]

L'esercizio in questione richiede, dato un vettore di interi, il numero di inversioni presenti
nell’array, cioè il numero di coppie di indici i e j tali che i < j e v[i] > v[j].
Ma che vuol dire? non riesco a capire il senso della richiesta.
Io ho scritto questo codice che viene compilato ed eseguito senza problemi, ma non so valutare se il risultato ottenuto è giusto oppure no, mi potreste aiutare?
Grazie mille.

int l=10;
int[] v=new int[l];
int n=v.length;
boolean distinti=true;
int inversioni=0;

for(int i=0; i<n; i++){
	v[i]=1+(int)(Math.random()*20);
	System.out.print(v[i]+" ");
}

int i=0;
while(i<n && distinti){
	int j=i+1;
	while(j<n && distinti){
		if(v[i]==v[j]){
			distinti=false;
		}
		j++;
	}
	i++;
}
System.out.println("\n"+distinti);

for(int k=0; k<n; k++){
	for(int w=k+1; w<n; w++){
		if(v[k]>v[w]){
			inversioni++;
		}
	}
}
System.out.println("\nIl numero di inversioni presenti e': "+inversioni);

[Andrea1979]

Allora, come per ogni esercizio, la cosa da fare e prendere carta e penna e fare una prova "a manina" per cercare di capire che cosa chieda l'esercizio:

Quindi mi scrivo un array di int_

[7;  -4;  5;  22; 0;  11; 19;  8]

ed interpreto il testo: trovare il numero di coppie di indici (i,j) | (i < j AND v[i] > v[j])

che non fa mai male e mi pare di capire che, se per esempio
i = 3
j = 5

e
v[i] = v[3] = 15
v[j] = v[5] = 8
questa è un'inversione, se invece v[j] = v[5] = 22 allora non viene rispettata il secondo termine dell'AND e quindi non ho un'inversione. Proviamo con l'array di esempio, come potrei fare? Doppio ciclo for, il primo indice i, il secondo indice j che parte da i+1. Un contantore inizializzato a zero. Il test v[i] > v[j]. Hai fatto tutto (l'ultima parte del codice che hai postato). Quindi direi che sei giunto (o chi per te) alla conclusione. La prima parte del codice non l'ho nemmeno guardata in quanto non mi sembrava inerente.

[dennis87]

Sono giunto, io, alla conclusione solo perche il testo dava gia le condizioni. Appunto i < j e v[i] > v[j], e quindi ho deciso di usare due cicli for per scorrere il vettore e l'if per fare il controllo.
Ma perdonami, ancora non sono riuscito a capire cosa si intende per inversioni, anche se l'avevo gia fatto, e l ho rifatto con carta e penna...

PS: la prima parte del codice riguarda un altra richiesta dell'esercizio, ovvero quella di vedere se gli elementi all'interno del vettore sono tutti distinti o no.

[Andrea1979]

Boh, è un po' che non faccio algoritmi (tipo 10 anni), e non so so quel numero che hai trovato sia anche l'upper bound del numero di swap tra elementi che dovresti fare con un qualche algoritmo di ordinamento affinchè il vettore sia ordinato in ordine crescente.

[Patrick Jane]

Originariamente inviato da dennis87
Ma perdonami, ancora non sono riuscito a capire cosa si intende per inversioni, anche se l'avevo gia fatto, e l ho rifatto con carta e penna...

i è minore di j. Un inversione si verifica quando l'elemento in posizione i è maggiore dell'elemento in posizione j (visto che naturalmente l'elemento i essendo più piccolo viene prima dell'elemento in posizione j).

Questo è ciò che conosco come inversione, ed è ciò che viene richiesto, se non erro.