Salut,
alta problema de backtracking



Scriet¸i un program C/C++ care cite¸ste din fi¸sierul standard de intrare (tastatura)
¸siruri de caractere de forma cuvˆant#tip, unde cuvˆant este un ¸sir oarecare de litere
iar tip poate fi una din literele S,P sau C, semnificat¸ia fiind subiect, predicat sau
complement. Aplicat¸ia va afi¸sa pe ecran toate propozit¸iile avˆand structura subiect
predicat complement ce pot fi formate cu ajutorul cuvintelor citite. Datele de intrare
se consider˘a a fi corecte.
Exemplu: dac˘a la intrare s-au introdus ¸sirurile: Ion#S Vasile#S alearga#P
repede#C scrie#P, atunci pe ecran se va afi¸sa: Ion scrie repede, Ion alearga
repede, Vasile scrie repede, Vasile alearga repede


deci se rezolva cu backtracking gen permutari S₁P₁C₁,S₁P₂C₁, etc

Dar cum reusesc sa memorez sirurile si sa le introduc in backtracking??

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

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?

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.