Ho svolto l’esercizio e il programma funziona, vi è un piccolo problema che nn riesco a risolvere nella stampa dei valori dei vettori la cui somma è x.
Il programma ignora il quarto elemento (in ordine di stampa) e stampa zero, mentre stampa il valore di v[j ] al posto di x. cioè risulta:
v[i]+v[j] = valore v[i] + 0 = valore v[j]
al posto di
v[i]+v[j] = valore v[i] + valore v[j] = x
La frazione di codice a cui faccio riferimento è alla riga 38. (penultimo if)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1000
int main()
{
long long int v[N]={0};
int i=0; //variabile decisionale per il riempimento
int n=0; //dimensione vettore
int x=0; // valore da cercare
int yes=0; //flag per sapere se è stato trovata almeno una coppia
/************************************************************************
* RIEMPIMENTO VETTORE *
************************************************************************/
printf("Inserisci dimensione del vettoren");
scanf("%d",&n);
printf("digita:t1 per inserimento da inputt2 per inserimento automatico casualen");
scanf("%d",&i);
srand(time(NULL));
if (i==1) for (int j=0; j<n; j++) scanf("%d",&v[j]); //inserimento manuale
else for (int j=0; j<n; j++) v[j]=rand(); //inserimento automatico
for( int j=0; j<n; j++) printf("v[%d] = %dn",j+1,v[j]); //stampa vettore
/************************************************************************
* RICERCA *
************************************************************************/
printf("ninserisci un valore compreso tra 0 e %dn",RAND_MAX);
scanf("%d",&x);
for(int j=0; j<n; j++)
for(int k=j+1; k<n; k++)
if(v[j]+v[k]==x) {printf("nv[%d]+ v[%d] = %d + %d = %d n",j+1,k+1,v[j],v[k],x); yes=1;}
if(yes==0) printf("n non ci sono valori nel vettore la cui somma sia uguale e %dn",x);
return 0;
}
Ho compilato il programma, non vedo errori. Su array casuali funziona senza problemi. Quando illustra il suo problema, dovrebbe fornire un istanza (il contenuto del vettore ed il numero cercato). Domanda un po più tosta: qual’è la sua complessità? Lo stesso problema può essere risolto con complessità minore?
Trascurando gli assegnamenti, le operazioni di confronto con somma sono n(n+1)/2 quindi la complessità è o(n^2).
Ho provato a ottimizzare l’algoritmo in questo modo e spero che il ragionamento sia corretto:
1) ordino il vettore con merge sort) ->o(nlogn)
2) cerco le posizione dell’elemento x nel vettore (chiamiamo j la posizione) con la ricerca dicotomia-> o(logn)
3) cerco le posizione dell’elemento x/2(se esiste altrim in numero strettam minore)(posizione k) -> o(log(n/2))
3) effettuo i confronti sommando gli elementi con posizione da 1a k e gli elementi da k+1 a j -> caso peggiore: n^2/4, caso migliore: o(1)
In definitiva questo algoritmo avrebbe o(n^2) cioè pari al precedente, quindi non dovrebbe essere possibile ottimizzare ulteriormente l’algoritmo.
Dal momento che si deve comunque sempre trovare una combinazione di due elementi, non si potrà fare a meno di avere complessità n^2 ,al massimo si può diminuire il numero di iterazioni del caso pessimo di un fattore costante come è descritto nel secondo algoritmo (che ripensandoci può essere migliorato rispetto ai primi 3 passi in funzione del dato in input ).