Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: subsiruri suma  (Citit de 7964 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
VladBtz
Strain
*

Karma: -3
Deconectat Deconectat

Mesaje: 29



Vezi Profilul
« : Ianuarie 24, 2015, 18:55:47 »

se citeste un sir de n numere.sa se scrie numerele care adunate ,dau o suma egal cu nr k.

exemplu
n=10
9 2 7 4 5 10 3 8 1 6   si k =13

10 +3
9+4
7+5 +1
etc...

ma gandeam sa sortez crescator vectorul si apoi cu i=0,i<n-1 si j=i+1;j<n  sa fac o suma care cat timpe mai mica decat k sa adune in ea....nu prea iese
« Ultima modificare: Ianuarie 24, 2015, 20:28:45 de către bieltz vlad » Memorat
Djok
Client obisnuit
**

Karma: 10
Deconectat Deconectat

Mesaje: 71



Vezi Profilul
« Răspunde #1 : Ianuarie 25, 2015, 21:23:33 »

Depinde de N, daca N<=20 se poate de facut cu generare de submultimi.
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #2 : Ianuarie 26, 2015, 04:01:38 »

http://en.wikipedia.org/wiki/Subset_sum_problem.

Problema e NP-Complete pe cazul general, se presupune că nu există soluție în timp polinomial relativ la input. Deci fie ai N mic și faci ceva exponențial în N -după cum ți-a sugerat Valeriu mai sus- fie ai valorile mici și o rezolvi cu programare dinamică.

Hint pentru programare dinamică: Gândește-te cum poți actualiza sumele obținute dintr-o anumită mulțime atunci când o extinzi cu un nou element.

Dacă ai soluții care merg atât pentru N mare cât și pentru valori mari, probabil ceva nu e în regulă.

Memorat
VladBtz
Strain
*

Karma: -3
Deconectat Deconectat

Mesaje: 29



Vezi Profilul
« Răspunde #3 : Ianuarie 27, 2015, 20:46:34 »

si daca numarul drebuie format doar din doua numere?
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #4 : Ianuarie 27, 2015, 22:31:42 »

Tu ce idei ai?
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines