Imprimă pagina - Siruri de caractere-Backtracking

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??

Problema nu se rezolva cu permutari ci cu produs cartezian. Tu ai 3 multimi: S-multimea subiectelor, P-multimea predicatelor si C-multimea complementelor. Tu trebuie sa generezi toate triplele de forma (a,b,c) cu a apartine S, b apartine P si c apartine C.
Acum, cum faci back-ul? Ceva de genu:

Cod:

back(nivel)
{	
	if(nivel==4) //am pus si subiect si predicat si complement
		afisare();
	else
		{
			for ( int i = 1; i <= M[ nivel ][ 0 ]; i++ ) //M[nivel][0] = cardinalul multimii M[nivel], multime in care stochezi cele 3 multimi S,P,C; ai un masiv 3-dimensional unde stochezi sirurile
			{
				st[ nivel ] = M[ nivel ][ i ];
				back(nivel+1);
			}
		}
}

Daca nu iti iese sau ai nevoie de ajutor la ceva...sa-mi spui. Bafta!

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Tofan Eduard din Iulie 19, 2013, 14:00:14