Imprimă pagina - Afisare permutari folosind un vector dat

Titlul: Afisare permutari folosind un vector dat
Scris de: Radu Chichi din Ianuarie 17, 2010, 18:49:48

De ceva vreme ma tot chinui sa gasesc metoda de rezolvare a acestui tip de problema prin folosirea algoritmului de backtrack,
insa solutia imi tot scapa...probabil din cauza lipsei unei fundatii solide a backtracking-ului.
V-as ruga sa modificati urmatorul algoritm,ce afiseaza deasemenea toate permutarile posibile, unde metoda de input difera insa
{1,2,3......n} :

Cod:

#include<iostream.h>
#include<fstream.h>
int n,st[100];
void init (int k)
{
	st[k]=0;
}
int succesor(int k)
{
	if(st[k]<n)
{
st[k]=st[k]+1;
return 1;
	}
	else return 0;
}
int valid(int k)
{
	for(int i=1;i<k;i++)
		if(st[k]==st[i]) return 0;
	return 1;
}
int solutie (int k)
{
	return k==n;
}
void print()
{
	for(int i=1;i<=n;i++)
	cout<<st[i]<<" ";
	cout<<endl;
}
void backtrack(int k)
{
	init(k);
	while(succesor(k))
		if(valid(k))
			if(solutie(k)) print();
		else backtrack(k+1);
}
main()
{
	cout<<"n= "; 
	cin>>n;
	backtrack(1);
}

Din nou repet, metoda de input in cazul programului pe care vreau sa il obtin, se va baza pe un n citit, si deasemenea un n numar de elemente citite:
Ex:

Cod:

 n=3
 3 4 8

Titlul: Răspuns: Afisare permutari folosind un vector dat
Scris de: George Popoiu din Ianuarie 17, 2010, 19:00:27

Incearca sa implementezi iterativ, poate o sa intelegi mai bine. Toate metodele sunt corecte, inafara de back.

La back ai putea sa faci ceva de genu:

Cod:

void back()
{
int AS;
int k=1;
init(k);
while(k>0)
   {
   do{}while( (as=succesor(k)) && !valid(k));
   if(AS)
      {
      if(solutie(k))print();
      else k++;
      }
   else k--;
   }
}

Daca nu intelegi da-mi un PM, sau incearca sa intelegi ce face backu si la ce se refera metoda. Cauta printr-un manual sau pe net.

Titlul: Răspuns: Afisare permutari folosind un vector dat
Scris de: Radu Chichi din Ianuarie 17, 2010, 19:30:37

OK, am gasit solutia... in cadrul functiei de tiparire trebuia folosit inca un vector ( v[ st [ i ] ] ).

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Radu Chichi din Ianuarie 17, 2010, 18:49:48