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

J

jaci87

Nuovo Utente
29 Nov 2006
4
0
0
Ciao a tutti :D

Dovrei sviluppare un programma che effettua le seguenti operazioni:

Codice: 
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

hellslord

Utente Attivo
28 Nov 2006
99
3
0
Venezia
www.squall.it
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:

Codice: 
 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 :(
 
J

jaci87

Nuovo Utente
29 Nov 2006
4
0
0
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 :D
 
Devi accedere o registrarti per poter rispondere.
Discussioni simili
Autore Titolo Forum Risposte Data
P [PHP] Progettino CRUD di esercitazione. Problema su $_FILE. PHP 9
otto9due Leggere valore da array multidimensionale a chiavi dinamiche PHP 1
M Passaggio variabili array php su un tasto jq PHP 3
M Somma inversa di Array C/C++ 2
MarcoGrazia Iterazione array PHP 5
N Passare array da php a javascript PHP 5
G Ordinare un array multidimensionale PHP 4
H Errore su array associativo PHP 1
K Array senza ripetizioni Presentati al Forum 4
A Gestione array multidimensionale PHP 6
otto9due Più chiavi in array con array_key_exists() PHP 0
M Array associativi php su 2 campi mysql PHP 10
T ALTRO PROBLEMA CON ARRAY PHP PHP 1
T PROBLEMA CON ARRAY PHP 8
L Sessione e array per utenti PHP 0
R Importazione csv su mysql tramite array PHP 2
elpirata Ricavare e stampare indirizzo ip da array associativo PHP 0
P Ciclare tra array di oggetti PHP 1
R Raggruppare valori array PHP 5
S Come conoscere la posizione di numeri in un array escludendo i doppioni PHP 4
D Popolare array PHP 8
R Includere elementi array fra apici PHP 1
P Array da foreach PHP 2
N Variabile di sessione è un array PHP7 PHP 3
R Scorporare array e recuperare record tabella PHP 10
A Contare gli elementi di un array PHP 13
A Importare array in mysql PHP 1
A Array di immagini Sviluppo app per Android 10
D Chiave unica in estrazione dati da array php PHP 0
D Spazio vuoto in un elemento di un array php PHP 2
S Come filtrare valori di un array PHP 4
mazman mysqli_query() mi ritorna un array vuoto anche se presente un record nella tabella PHP 13
A Non è un array e nemmeno un intero, che tipo di dato è? Javascript 1
max1974 PHP, Array Multidimensionale e Grafici PHP 22
S [PHP] Confrontare due array con valori quasi uguali PHP 2
MarcoGrazia [PHP] Unioni di due array con somma di valori PHP 6
R [PHP] Visualizzazione dati Array PHP 2
S [PHP] Eliminare doppioni array e rinumerare le posizioni PHP 2
M Importare - Manipolare Json Array Sviluppo app per Android 2
M [PHP] Problemi su inserimento array nel db PHP 7
M [PHP] Visualizzare un array partendo dal numero 1 e non 0 PHP 5
G [ASP] Ciclare i valori di 2 array Classic ASP 2
S [PHP] Estrarre elementi array su più variabili PHP 5
S [PHP] Estrarre dati tabella in diversi array PHP 2
max1974 [PHP] Raggruppare array PHP 4
A [PHP] Caricamento database in array PHP 11
G sql select con array in php PHP 1
L [Java] Aggiungere elementi ad array JSON Java 0
S [PHP] individuare chiave elemento array PHP 7
A [PHP] Script con array con numeri che iniziano per 00 PHP 2

Discussioni simili

Alto Basso