esercitazione array [c++]..help!!

[jaci87]

Ciao a tutti

Dovrei sviluppare un programma che effettua le seguenti operazioni:

l) Stampa su cout la scritta "Dammi il valore della somma dei due 
   elementi da cercare. x = ". 

m) Legge da cin il numero x. 

n) Cerca due indici distinti i e j tali che A[i] + A[j] == x. 
   Si suggerisce di usare una while con invariante 

   /* Ord(A[0..n-1]), A[p]+A[q] != x per ogni p compreso tra 0 e i-1 e 
      q qualsiasi e per ogni q compreso tra j+1 ed n-1 e p qualsiasi */ 

o) Se i == j stampa su cout la scritta "Non esiste nessuna coppia di 
   indici distinti tali che A[i]+A[j] == x" 

p) Se i < j stampa su di una stessa riga di cout la scritta 
   "A[i]+A[j] = x" dove i, j sono i valori degli indici calcolati e 
   x e' il valore della somma cercata.

Per i punti l,m,o,p non ci sono problemi...il punto n invece mi sta facendo dannare :incazz2: ...in particolare realizzare il ciclo che abbia quell'invariante.
Mi va benissimo anche se mi suggerite come lo fareste voi, senza per forza utilizzare quell'invariante.

 

[hellslord]

Ciao, l'invariante che hai fornito non mi è molto chiara se devo essere sincero... cmq... Il sistema più semplice (ma anche il meno efficiente) per risolvere il problema è questo:

 for (int i = 0; i < n; i++)
 { 
   int flag = 0;
   for(int j = i; j < n; i++)
   {
     if (a[i] + a[j] == x)
     {
       flag = 1;
       break;
     }
   }
   if (flag) break;
 }

In questa maniera per ogni elemento dell'array controlli che sommandolo ai rimanenti dia la somma cercata (gli elementi prima di i non è necessario controllarli, dato che nei cicli precedenti sono già stati sommati con quelli attuali, e per la prorietà commutativa della somma non è necessario riprovarli).
Controlli inoltre anche la situazione a + a = x ... in tal caso i cicli terminano lo stesso e poi avrai il controllo...

Il fatto è che la complessità dell'algoritmo è THETA(n^2) (a causa dei due cicli for annidati che scandiscono tutti gli elementi dell'array per ogni elemento, nel caso peggiore di i=j=0)... Sicuramente si può trovare un algoritmo più efficiente, e forse seguendo la invariante fornita si arriverebbe ad avere prestazioni migliori, ma ripeto: quell'invariante non mi è molto chiara...

Purtroppo ora non ho molto tempo per pensarci a dovere

 

[jaci87]

grazie hellslord, più o meno è come lo avevo pensato io

P.s.: quello che ci ha suggerito l'invariante è stato il prof di introduzione alla programmazione, non so se mi spiego

 

[hellslord]

Sempre felice di dare una mano