Program gasire numere ce insumate dau o anumita valoare

#1
greenlife

Posted 15 March 2023 - 13:10

Active Member

Grup: Members
Posts: 1,966
Înscris: 29.07.2017

Salut. Daca puteti sa-mi dati un punct de plecare pentru un program ce sa faca ceea ce scrie in titlu.
De exemplu am suma de 24
Cum fac ca sa detectez de exemplu din 2 pagini de numere care dintre ele, insumate dau 24.
1, 2, 7, 4, 6, 8, 20, 1, 3, 19,..................................................
19+2+3=24. Un numar poate fi adunat o singura data.
Multumesc.

Back to top

#2
sorin147

Posted 15 March 2023 - 14:12

Senior Member

Grup: Senior Members
Posts: 6,349
Înscris: 11.08.2003

La 2 pagini ar trebui sa fie multe numere si,implicit, probabil si suma de cautat este mare => pica ideea de a le ordona crescator si sa incepi calculul de la numarul egal sau mai mic decat cel cautat.
Trebuie toate combinatiile sau macar una?
Logica (de balta) zice sa le aduni pe rand pana iti da ce trebuie: intai vezi daca numarul exista in lista, apoi aduni cate 2 numere, apoi cate 3 si tot asa => nu pare prea eficient dar (sper) ca face treaba
Aranjate iar si, Oarba dupa ele... cumva

Apropo, poti pune paginile aici si sa vedem ce (ne) iese?

Back to top

#3
sags

Posted 15 March 2023 - 15:42

Senior Member

Grup: Senior Members
Posts: 9,936
Înscris: 24.04.2013

Backtracking. Alta idee nu imi vine in minte acuma.

La pima impresie pentru a reduce timpul de rulare:

Sorteaza numerele crescator. In acest fel opresti adaugarea de numere cand suma celor existente depaseste suma asteptata si te intorci.
Calculeaza de la inceput suma tuturor numerelor. Daca e strict mai mica decat cea dorita clar nu exista solutie. Daca e egala iar e clar, ai o singura solutie care contine toate numerele, dar probabilitate sa fie asa e mica.
Compara suma dorita cu jumatatea sumei tuturor numerelor. Daca e mai mare, rezolva problema cu suma tuturor minus suma dorita in locul celei dorite. In acest fel scurtezi backtrackingul fiindca, oprindu-te cand suma numerelor de pana atunci e ai mare decat cea tinta, te vei opri mai devreme. Solutia pentru problema initiala este formata din celelalte numere decat cele din solutia gasita a problemei modificate.

Back to top

#4
greenlife

Posted 15 March 2023 - 16:06

Active Member

Grup: Members
Posts: 1,966
Înscris: 29.07.2017

Multam de sprijin. Ma apuc sa buchisesc. Într-adevăr sumele sunt mai mari iar întrările(numerele) sunt multe. Nu pot pune paginile cu ele fiindca au multe date personale.

Back to top

Anunturi

Bun venit pe Forumul Softpedia!

Program gasire numere ce insumate dau o anumita valoare

#1 greenlife Posted 15 March 2023 - 13:10

#2 sorin147 Posted 15 March 2023 - 14:12

#3 sags Posted 15 March 2023 - 15:42

#4 greenlife Posted 15 March 2023 - 16:06

Anunturi

▶ 0 user(s) are reading this topic

Sign In

#1
greenlife

Posted 15 March 2023 - 13:10

#2
sorin147

Posted 15 March 2023 - 14:12

#3
sags

Posted 15 March 2023 - 15:42

#4
greenlife

Posted 15 March 2023 - 16:06