Ecuatie liniara-Backtracking?

[•EDDYZY]

Salut ,
Ma puteti ajuta sa rezolv o problema c++?


Se considera ecuatia liniara a₀x₀ + a₁x₁ + . . . + a_n−1x_n−1 = b, unde atat b cat si
coeficientii a_i, i apartine {0..n − 1}, sunt numere ıntregi. Fiecare dintre variabilele x_i, i apartine
{0..n−1}, poate lua valori doar numere ıntregi ın intervalul [inf, sup], acelasi pentru
toate variabilele (inf < sup sunt de asemenea numere ıntregi).

b) Scrieti ın limbajul C/C++ doua functii min si max care primesc ca argumente
numarul n, tabloul coeficientilor a, valoarea b, marginile inf si sup si un index
k apartine {0, ..n − 1} si returneaza min suma de la k la n-1 din a_ix_i
, respectiv max suma de la k la n-1 din a_ix_i
, unde x_i apartine [inf, sup]. (6p.)
c) Scrieti ın limbajul C/C++ o functie care primeste ca argumente numarul n,
tabloul coeficientilor a, valoarea b, marginile inf si sup si returneaza un tablou
cu n elemente continand o solutie a ecuatiei date sau NULL daca ecuatia nu are
nicio solutie. Folositi functiile min si max definite mai sus pentru a eficientiza
procesul de cautare a solutiilor.


am o idee cum se rezolva:folosind backtraking generez toate sol din interval[inf,sup],si pt fiecare fac o verificare
ce nu inteleg e cum pot folosi functiile min si max.

va rog sa ma ajutati
Multumesc anticipat.

[•klamathix]

Le folosesti ca sa-ti reduci numarul de incercari. Ideea e ca daca ti-ai fixat prin backtracking primele T variabile si ai suma S, atunci ai nevoie sa obtii suma B - S din celelalte N - T variabile. Daca B - S e mai mare decat maximul din cat stii ca poti obtine in ultimele N - T variabile (sau mai mic decat minimul) atunci n-are sens sa continui, e clar ca trebuie sa schimbi ceva din spate.

[•EDDYZY]

Le folosesti ca sa-ti reduci numarul de incercari. Ideea e ca daca ti-ai fixat prin backtracking primele T variabile si ai suma S, atunci ai nevoie sa obtii suma B - S din celelalte N - T variabile. Daca B - S e mai mare decat maximul din cat stii ca poti obtine in ultimele N - T variabile (sau mai mic decat minimul) atunci n-are sens sa continui, e clar ca trebuie sa schimbi ceva din spate.

am inteles. deci aleg primele T variabile care au suma S ,si  verific ca suma B-S sa fie intre minimul si maximul celor N-T variabile
da am inteles conceptul dar mai am o intrebare:
cum incep ?asa pare simplu da cand ma dau la scris...
cu cate variabile incep?
una?

[•klamathix]

Da, cu una . O fixezi apoi mergi recursiv cu celelalte. La fiecare pas verifici daca are rost sa continui pe configuratia asta.

[•EDDYZY]

Da, cu una . O fixezi apoi mergi recursiv cu celelalte. La fiecare pas verifici daca are rost sa continui pe configuratia asta.

deci incep cu x1= inf da de exemplu
x1 poate sa fie egal cu x2,x3 etc?

inf =1 de ex

si sa am sol x1=x2=x3=...=1