C. Conta coppie >0

[lucas87]

L'esercizio è il seguente:

Scrivere una funzione (iterativa) che calcoli il numero di coppie (i,j) tali che
A[i]+B[j]>0 per due vettori A e B.

Sembra una stronzata e infatti lo è!!!
Di seguito è postata la soluzione.
Ma ora c'è da fare una piccola variazione. Ipotizzare che i 2 vettori A e B siano ordinati e sfruttare il fatto che siano ordinati per creare un algoritmo piu efficiente.

Come si puo fare?

Soluzione senza ipotizzare che i vettori siano ordinati:


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



void leggi_array(int *, int );
int cnt_coppie(int *, int *, int, int);



int main(void){
int dim1,dim2;
printf("Immetti la dimensione del primo Array:");
scanf("%d",&dim1);
int v1[dim1];
printf("Immetti la dimensione del secondo Array:");
scanf("%d",&dim2);
int v2[dim2];
printf("caricamento primo vettore\n");
leggi_array(v1,dim1);
printf("caricamento secondo vettore\n");
leggi_array(v2,dim2);
printf("numero di coppie la cui somma e' maggiore di 0 e' = %d\n",cnt_coppie(v1,v2,dim1,dim2));
system("PAUSE");
}

int cnt_coppie(int *t1,int *t2, int dim1, int dim2){
int i,j,cnt;
cnt=0;
for (i=0;i<dim1;++i){
for (j=0;j<dim2;++j){
if ((t1[i]+t2[j])>0) ++cnt;
}
}
return cnt;
}


void leggi_array(int *t, int d){
int i;
for(i=0;i<d;i++){
printf("Immetti t[%d]= ",i);
scanf("%d",&t[i]);
}
}

[Ziosilvio]

Modifica leggermente l'algoritmo di ricerca binaria in modo che trovi, in un vettore, non l'indice dell'elemento con un valore fissato ma quello del più piccolo elemento che non scende al di sotto di quel valore.
A questo punto, per ogni A[k] applica la ricerca modificata a B sul valore -A[k]: trova j, e aggiungi len(B)-j al totale delle coppie.

EDIT: questo ipotizza che sia ordinato solo B... si può fare di meglio...

... ah, sì: chiamare l'algoritmo solo sulla porzione di B tra l'ultimo indice trovato, e la fine.
ARIEDIT: questo andrebbe bene se A fosse letto a partire dall'elemento più grande.
Se invece parti dal più piccolo, fai la tua ricerca una volta sola quando hai A[1]; poi, quando conti A[2], noti che tutti gli elementi di B che hai trovato al primo passaggio, vanno ancora bene, e devi al più aggiungere qualcuno di quelli di prima... e mi sa che così arrivi a tempo O(N + K) anziché O(N log K), dove N è la lunghezza di A e K quella di B...

[lucas87]

Provato e funzionante. Grazie della risposta Ziosilvio.

Qualcuno sa come sfruttare il fatto che entrambi i vettori siano ordinati?

Grazie in anticipo.

[yorkeiser]

Un'idea, una volta che hai ordinato gli array, é:

per ogni a[i], cerca l'indice j per cui a[i]+b[j]>0
coppie += Dimensione_array_b - j

Su un array ordinato puoi ottimizzare anche la ricerca, ad esempio eseguendo una ricerca selettiva, ovvero non scorrendo l'array b elemento per elemento alla ricerca del primo elemento che soddisfa la condizione voluta.
Un esempio di ricerca selettiva:


jInf=0
jSup=Dimensione_array_b;

while (jSup!=jInf)
{
j = jSup-jInf/2;
If (b[j] soddisfa la condizione) jSup=j
else jInf = j
}


la j finale che ottieni dovrebbe essere il primo indice j che verifica la condizione da te voluta

[Ziosilvio]

Qualcuno sa come sfruttare il fatto che entrambi i vettori siano ordinati?
Ho editato il mio post precedente. Vedi un po' se funziona...

[lucas87]

Mhh..per ziosilvio, lo fatto come dici tu pero in esecuzione non da problemi, a volte va, ma penso per puro caso. Se ti capita di fare il codice, fammi sapere se ti va e magari postalo se hai tempo.

ciao

[lucas87]

Utilizzando l'idea di yorkeiser lo fatto funzionare, non pero usando la ricerca effettuata in quell'altro modo, in quanto mi creava problemi alcune volte.

Posto la probabile soluzione finale:



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

#define LIMIT 1024


void leggi_array(int *, int );
int cnt_coppie(int *, int *, int, int);



int main(void){
int dim1,dim2;
printf("Immetti la dimensione del primo Array:");
scanf("%d",&dim1);
int v1[dim1];
printf("Immetti la dimensione del secondo Array:");
scanf("%d",&dim2);
int v2[dim2];
printf("caricamento primo vettore\n");
leggi_array(v1,dim1);
printf("caricamento secondo vettore\n");
leggi_array(v2,dim2);
printf("numero di coppie la cui somma e' maggiore di 0 e' = %d\n",cnt_coppie(v1,v2,dim1,dim2));
system("PAUSE");
}

int cnt_coppie(int *t1,int *t2, int dim1, int dim2){
int i,j,cnt;
cnt=0;
j=0;
for (i=0;i<dim1;++i){
for (j=0;j<dim2;++j){
if ((t1[i]+t2[j])>0){
cnt=cnt+(dim2-j);
break;
}
}
}
return cnt;
}


void leggi_array(int *t, int d){
int i;
for(i=0;i<d;i++){
printf("Immetti t[%d]= ",i);
scanf("%d",&t[i]);
}
}