[esperti]Algo per trovare 3 elementi in un array che sommati tra di loro sono = 100

[xnavigator]

Originariamente inviato da frankitt
Ho capito cosa intendi, ma il senso dell' esercizio è quello, quindi senza fare esponenziali, basta quella matrice, e tenersi qualche informazione in più.

hmm c'è anche un altro problema. l'algo richiesto per quell'esercizio lavora solo su array di interi postivi..
a me l'array ha anche interi negativi

con interi negativi i controlli fatti alla riga 9 (l'if dopo i 2 for) non credo sarebbero corretti...

[frankitt]

Guarda, purtroppo non ho proprio il tempo di mettermelo a fare a mano, cmq quell' algoritmo dovrebbe funzionare anche con i negativi, perchè sempre cmq di somme stiamo parlando. Quindi come ti ripeto l' algoritmo è giusto, solo lo devi riadattare alle tue esigenze, sforzati di trovare queste migliorie, e non di cercare algoritmi più complessi. Questo è il mio consiglio! Mi auguro che altri ti possano aiutare di più. Ciao ciao!

[xnavigator]

Originariamente inviato da frankitt
Guarda, purtroppo non ho proprio il tempo di mettermelo a fare a mano, cmq quell' algoritmo dovrebbe funzionare anche con i negativi, perchè sempre cmq di somme stiamo parlando. Quindi come ti ripeto l' algoritmo è giusto, solo lo devi riadattare alle tue esigenze, sforzati di trovare queste migliorie, e non di cercare algoritmi più complessi. Questo è il mio consiglio! Mi auguro che altri ti possano aiutare di più. Ciao ciao!

guarda non può funzionare con i negativi perchè c'è il controllo nell'if che dice di eseguire l'aggiornamento solo nel caso in cui:

elementoXjesimo <= i

quindi questo significa che verranno scartate tutte le soluzioni che contengono numeri maggiori del nostro obiettivo target... che è giusto nel caso l'array contenesse solo numeri positivi ma non nel nostro caso..

perchè anche se prendiamo un numero esempio 150 che supera il nostro obiettivo 100, potrebbe essere sempre una soluzione se nell'array ci sono altri 2 numeri negativi ( -20 e -30 per esempio ) situazione che invece verrebbe scartata dal tuo algo

[xnavigator]

up

[Andrea1979]

La butto lì, magari dico una cavolata (è qualche millennio che non programmo più seriamente).

Ipotesi:
1) array a ordinato (in senso decrescente);
2) target da raggiungere T;
3)sempre ricerca binaria.


Passo 0: scrematura.
Eliminiamo subito tutti i valori ad indice "i" : a[i] + a[n-1] >= T.
In verità si può fare di meglio, eliminando subito tutti i valori : a[i] + a[n-1] + a[n-2] > T;

Passo successivo:
Scelto un a[i] "pivot", il nuovo target sarà T' = T - a[i]. Quindi ripeterò l'algoritmo con
T', j > i.

[xnavigator]

Originariamente inviato da Andrea1979

In verità si può fare di meglio, eliminando subito tutti i valori : a[i] + a[n-1] + a[n-2] > T;

eliminado intendi che non verrano più considerati nei passi successivi?

(in questo caso purtroppo sarebbe sbagliato)

[Andrea1979]

Non è sbagliato: se il tuo array (ordinato) fosse:

a = {120, 98, 75, 70, 60, 25, 20, 15, 10, 5, 3, 1}
e il tuo target T = 100

è pacifico che per a[0] = 120 sei fuori target.

Ma anche per a[1] = 98 sei fuori target in ogni caso (passo 0 + osservazione) visto che
Per i = 1

a[i] + a[n-1] = 98 + 1 = 99 -> "buono"

ma:

a[i] + a[n-2] + a[n-1] = 98 + 3 + 1 = 102 > 100. No buono.
98 non potrà mai fare parte della tua collezione di 3 elementi.

Quindi al passo 0 già elimini un po' di elementi. Ai passi successivi succedono altre cose.

Per il caso pivot = a[2] = 75.

Il nuovo target è T' = T - 75 = 25.
a[4] e a[5] ovviamente non posso appartenere alla tua collezione, se già hai scelto 75.

Ma anche a[6] = 25 non potrà essere una buona scelta, se nella tua collezione hai già infilato il 75.

Ciò non toglie che alla passata successiva (ovvero cominciando con a[3]= 70) alcuni di quegli elementi siano "buoni". In questo modo dovresti riuscire a scendere a O(nLog(n)) se non ho proprio rimosso tutto.

[xnavigator]

Originariamente inviato da Andrea1979
Non è sbagliato: se il tuo array (ordinato) fosse:

a = {120, 98, 75, 70, 60, 25, 20, 15, 10, 5, 3, 1}

dimentichi il particolare fondalmetale... ci sono anceh i numeri negativi

è pacifico che per a[0] = 120 sei fuori target.

no perchè con numeri negativi ci potrebbbe essere -20 e faresti 120-20=100 (senza dimetnicare vabbè che ho bisgono di 3 numeri)

[Andrea1979]

negativi... ahen... vabbhè allora la furbata non va e non va nemmeno la BS.

[xnavigator]

Originariamente inviato da Andrea1979
negativi... ahen... vabbhè allora la furbata non va e non va nemmeno la BS.

ci sto quasi rinunciando a trovarlo...

comunque sono quasi sicuro che per un problema del genere serve per forza la programmazione dinamica (tipo problema dello zaino) con la costruzione della soluzione partendo dal basso O(Target*N)

tipo quella postata da frankitt, il problema è che anche quella con numeri negativi non va bene... e non saprei come modificarla sincermanete :

http://www.dsi.uniroma1.it/~asd2/ASDII020707Sol.pdf