[Algoritmi] ricerca di coppie in vettori

[tonno16]

salve a tutti. Questo è il mio primo thread. Ho qui con me alcuni esercizi risolti, ma di cui non so se effettivamente le mie soluzioni solo valide. Provo a scriverli su questo forum scoperto oggi.

TESTO DELL' ESERCIZIO:
sia V un vettore di n elementi pari ( quindi 4 elementi 6 elementi 12 elementi....). Creare un algoritmo che ritorni true se ci sono coppie che sommate diano lo stesso valore, e false se ciò non accade.

esempio: vettore= 2 3 4 5 6 7.......la somma è sempre 9. 2+7 4+5.... i numeri considerati non possono essere riusati

PSEUDO CODICE:

trovato=1;

MERGESORT(V)
TROVA(V, i , n)
    if n = 2  then  return TRUE
    while( trovato!=0)
              if   ( A[i]+[n] )!= A[i+1]+A[n-1]   then  return FALSE
              else return TRUE
    
   TROVA(A,i+1, n-1)

tempo impiegato credo sia T(n)=T(n/2)+c + mergesort quindi penso logn + nlogn = teta(nlogn)

dite che va bene come algoritmo ricorsivo?

[hamming_burst]

Ciao Benvenuto,

"tonno16":
TESTO DELL' ESERCIZIO:
sia V un vettore di n elementi pari ( quindi 4 elementi 6 elementi 12 elementi....). Creare un algoritmo che ritorni true se ci sono coppie che sommate diano lo stesso valore, e false se ciò non accade.

esempio: vettore= 2 3 4 5 6 7.......la somma è sempre 9. 2+7 4+5.... i numeri considerati non possono essere riusati

quindi ritorna true se esistono almeno due coppie (1). Oppure si deve decidere se esiste un partizionamento di coppie di due elementi con somma uguale (2)?

es. 2 3 4 5 6 7
2+7=4+5=6+3
ok in entrambe le versioni.

es. 2 3 4 5 7 8
2+7=4+5
ok per (1)
non per (2)

[tonno16]

partizionamento di coppie, le quali danno tutte lo stesso valore.

quindi se hai 1 2 3 4 5 6 7 100....ecco non va bene perchè non tutte le coppie danno la stessa somma.
inoltre ipotizzo io che vada ordinato. Non sono sicuro di questo

[hamming_burst]

per risolverlo hai provato diciamo ingegneristicamente, oppure c'è dietro una dimostrazione?

con l'ordinamento e con questo:

A[i]+[n] )!= A[i+1]+A[n-1]  

se fai la giusta ricorrenza ed iterazione su tale confronto, la proprietà sarebbe corretta e risolvi il problema, ma ti chiedo: perchè proprio un ordinamento e quel confronto, sapresti dimostrarlo?

Tutto il resto non ha senso in termini di programmazione, od almeno è scritto male.

    while( trovato!=0)
              if   ( A[i]+[n] )!= A[i+1]+A[n-1]   then  return FALSE
              else return TRUE
    
   TROVA(A,i+1, n-1)

iteri sul primo ed ultimo elemento se sono diversi ritorni TRUE o FALSE ed il codice termina. Il problema non è risolto.

dichiari trovato, utilità di ciò? non lo modifichi ed è un'invariante fasulla, perchè avresti un ciclo infinito.
Non hai controlli sulla grandezza del vettore, se togliessimo i return, dopo $n/2$ iterazioni confronteresti di nuovo gli stessi elementi al contrario. Dopo $n$ iterazioni avresti un seg-fault.
pseudocodice ok, ma che sia almeno ben definito.

tempo impiegato credo sia T(n)=T(n/2)+c + mergesort quindi penso logn + nlogn = teta(nlogn)

La ricorrenza è, a manica larga, $T(n-1) + c$ perchè avanzi di uno step a ricorrenza, omettendo i controlli avresti una complessità di $O(n)$ che è sovrastata dall'ordinamento $O(nlogn)$.

dite che va bene come algoritmo ricorsivo?

basterebbe anche solo il ciclo, se scritto bene.

ti consiglio di ripensare al tutto, sia alla proprietà del problema (banale) sia all'algoritmo.
A mio vedere si può rimanere a complessità $O(n)$ utilizzando le proprietà richieste, senza ordinare quindi eliminando tale operazione. Ma per il momento sistemiamo la tua proposta.