Question

Se citeste o multime a cu n elemente . Sa se plaseze + sau - astfel incat rezultatul expresiei sa apartina intervalului deschis [p,q].
Cine stie sa o faca poate sa faca doar subprogramul de backtracking deoarece de prelucrare solutie sau valid stiu eu. Multumesc

Answer 1

Din ce inteleg eu acolo tu vei citi n numere de la tastatura, iar apoi pe unele le vei "face" negative punandu-le semnul - in fata iar pe altele le vei lasa pozitive, si ai nevoie de o configuratie se asemenea numere pozitive si negative astfel incat suma lor sa fie dintr-un interval dat (probabil tot de la tastatura) [p,q].

Tu practic ai nevoie de un aranjament de + si -. Asta face problema sa se poata rezolva in doua moduri pentru ca putem face analogia unui sire de + si - cu un nr. binar format din 1 si 0, avand n biti.

Varianta banala este sa folosesti backtracking pentru a genera toate combinatiile de n + sau - iar pentru validare sa verifici suma numerelor (negandu-le pe cele necesare) sa fie intre p si q.

Modul mai interesant este sa te legi de exact acest lucru: ca te poti gandi la solutia ta ca la o configuratie de 1 si 0, nu nr in binar si deci ai putea pur si simplu sa faci un for de la 0 la (2^n)-1 iar in for sa transformi contorul for-ului in binar, apoi considerand 0 ca fiind - si 1 ca fiind + poti verifica daca solutia este buna.

Spor.