[C++]n camile

[LordCronos]

Mai am la codul asta care deja sunt intr-o ceata totala:

Code: Select all

#include<iostream>
using namespace std;
int st[100],depth,m[50][50],top,n,zile;
int tipar(int st[],int top)
{
    zile++;
    //m[i][d[i]]=st[top+1];
    //for(int i=1;i<=top;i++)
    cout<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<st[i]<<" ";
        m[st[i]][i]=st[top+1];
    }
    top=1;
    return 0;
}
int succesor(int st[],int top)
{
    if(st[top]<n)
    {
        st[top]++;
        return 1;
    }
    else return 0;
}
int valid(int st[],int top)
{
    if(top>1)
    {
        for(int i=1;i<top;i++)
        {
            if(st[i]==st[top])
            return 0;
        }
        for(int i=1;i<=depth+1;i++)
        {
            if(st[top]==m[st[top-1]][i])
            return 0;
        }
    }
    return 1;
}
int init(int st[],int top)
{
    st[top]=0;
}
int solutie(int st[],int top)
{
    if(top==n)
    return 1;
    return 0;
}
int back(int st[],int top)
{
	top=1;
	init(st,top);
	while(top>0)
	{
		while(succesor(st,top))
		{
			if(valid(st,top))
			if(solutie(st,top))
			tipar(st,top);
			else
			{
				top++;
				init(st,top);
			}
		}
		top--;
	}
}
int main()
{
    cout<<"n= ";
    cin>>n;
    back(st,top);
    cout<<endl<<"Zile= "<<zile;
    return 0;
}

O caravana formata din n camile calatoreste prin desert in sir indian. Pentru a sparge monotonia zilelor lungi de drum, beduinul sef se hotaraste sa schimbe asezarea camilelor astfel incat fiecare camila sa nu mai vada in fata ei aceeasi camila de pana atunci. Sa se genereze toate posibilitatile de asezare a camilelor.

La mine nu stiu cum se face dar inca e permutari :)) ...

[IsTI37]

Ma dispera cand in C++ cineva nu foloseste { } la toate for/if-urile.
Faci o functie care afiseaza o matrice cu nxn elemente in locul functiei tipar si st il folosesti in urmatorul fel : st[1] este coloana reginei pe primul rand, deci umplii toate coloanele inafara de valoarea lui st[1] cu 0 si cu 1 pe pozitia lui st[1] pe randul 1...

Mura in gura:

Code: Select all

int tipar(int st[],int top)
{
    for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) {
    if(st[i]=j) cout<<"1" else cout<<"0";
   }
    cout<<endl;
   }
   cout<<endl;   
}

[LordCronos]

Ma dispera cand in C++ cineva nu foloseste { } la toate for/if-urile.
Faci o functie care afiseaza o matrice cu nxn elemente in locul functiei tipar si st il folosesti in urmatorul fel : st[1] este coloana reginei pe primul rand, deci umplii toate coloanele inafara de valoarea lui st[1] cu 0 si cu 1 pe pozitia lui st[1] pe randul 1...

Mura in gura:

Code: Select all

int tipar(int st[],int top)
{
    for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) {
    if(st[i]=j) cout<<"1" else cout<<"0";
   }
    cout<<endl;
   }
   cout<<endl;   
}

Mi-am dat seama intre timp. :)) Multumesc oricum. :D

Mai am la codul asta care deja sunt intr-o ceata totala:

Code: Select all

#include<iostream>
using namespace std;
int st[100],depth,m[50][50],top,n,zile;
int tipar(int st[],int top)
{
    zile++;
    //m[i][d[i]]=st[top+1];
    //for(int i=1;i<=top;i++)
    cout<<endl;
    for(int i=1;i<=n;i++)
    {
        cout<<st[i]<<" ";
        m[st[i]][i]=st[top+1];
    }
    top=1;
    return 0;
}
int succesor(int st[],int top)
{
    if(st[top]<n)
    {
        st[top]++;
        return 1;
    }
    else return 0;
}
int valid(int st[],int top)
{
    if(top>1)
    {
        for(int i=1;i<top;i++)
        {
            if(st[i]==st[top])
            return 0;
        }
        for(int i=1;i<=depth+1;i++)
        {
            if(st[top]==m[st[top-1]][i])
            return 0;
        }
    }
    return 1;
}
int init(int st[],int top)
{
    st[top]=0;
}
int solutie(int st[],int top)
{
    if(top==n)
    return 1;
    return 0;
}
int back(int st[],int top)
{
	top=1;
	init(st,top);
	while(top>0)
	{
		while(succesor(st,top))
		{
			if(valid(st,top))
			if(solutie(st,top))
			tipar(st,top);
			else
			{
				top++;
				init(st,top);
			}
		}
		top--;
	}
}
int main()
{
    cout<<"n= ";
    cin>>n;
    back(st,top);
    cout<<endl<<"Zile= "<<zile;
    return 0;
}

O caravana formata din n camile calatoreste prin desert in sir indian. Pentru a sparge monotonia zilelor lungi de drum, beduinul sef se hotaraste sa schimbe asezarea camilelor astfel incat fiecare camila sa nu mai vada in fata ei aceeasi camila de pana atunci. Sa se genereze toate posibilitatile de asezare a camilelor.

La mine nu stiu cum se face dar inca e permutari :)) ...

[reTry]

daca vrei ti-o fac eu cu backtracking, codul ala al tau mi se pare ciudat, desi si ala e tot backtracking !

[IsTI37]

E acelasi cod cu primul, doar ca lasi afisarea cu cout<<st si scoti din valid linia care iti verifica in diagonala reginele.
E foarte aiurea algoritmul tau de backtracking, foloesti mult prea multe functii fara nici un rost.
Foloseste maxim 3.
afisare, conditie si back...

Code: Select all

        for(int i=1;i<=depth+1;i++)
        {
            if(st[top]==m[st[top-1]][i])
            return 0;
        }

nu are rost

[reTry]

Code: Select all

#include<iostream>
using namespace std;
int x[11],n;
int valid(int k)
{
	int i;
	for(i=1;i<k;i++)
		if(x[i]==x[k])
			return 0;
	if(k>1 && x[k]-x[k-1]==1)
		return 0;
	return 1;
}
void afisare(int k)
{
	int i;
	for(i=1;i<=k;i++)
		cout<<x[i]<<" ";
	cout<<endl;
}
void back(int k)
{
	int i;
	for(i=1;i<=n;i++)
	{
		x[k]=i;
		if(valid(k)==1)
			if(k==n)
				afisare(k);
			else back(k+1);
	}
}
int main()
{
	cout<<"Dati numarul de camile: ";cin>>n;
	cout<<"\n";
	cout<<"Modul de aranjare a camilelor sunt: ";
	cout<<"\n";
	back(1);
	return 0;
}

Lucrezi cu pozitiile camilelor, daca nu ai inteles prv .

[LordCronos]

Code: Select all

#include<iostream>
using namespace std;
int x[11],n;
int valid(int k)
{
	int i;
	for(i=1;i<k;i++)
		if(x[i]==x[k])
			return 0;
	if(k>1 && x[k]-x[k-1]==1)
		return 0;
	return 1;
}
void afisare(int k)
{
	int i;
	for(i=1;i<=k;i++)
		cout<<x[i]<<" ";
	cout<<endl;
}
void back(int k)
{
	int i;
	for(i=1;i<=n;i++)
	{
		x[k]=i;
		if(valid(k)==1)
			if(k==n)
				afisare(k);
			else back(k+1);
	}
}
int main()
{
	cout<<"Dati numarul de camile: ";cin>>n;
	cout<<"\n";
	cout<<"Modul de aranjare a camilelor sunt: ";
	cout<<"\n";
	back(1);
	return 0;
}

Lucrezi cu pozitiile camilelor, daca nu ai inteles prv .

Asta e permutari.. si am vazut si ceva de genu' pe internet... nu e corect ...
Pentru n = 3 ar trebui sa-mi dea 1 2 3 si 1 3 2 atat. + ca-mi trebuie irecursiv.

[reTry]

cum sa-ti dea 1 2 3 si 1 3 2 ? Problema spune clar ca trebuie toate combinatiile a.i. o camila sa nu mai aiba in fata pe aceeasi care a avut-o initial !

so : n = 3 ( 1 2 3 )
vei avea solutie : 1 3 2, 2 1 3, 3 2 1.

Ce e gresit, ma rog, in rezolvarea mea?

1 3 2 e intradevar o solutie dar 1 2 3 e combinatia initiala !

ps: gandeste-o matematic mai intai
ps2: cum Dumnezeu faci tu backtracking nerecursiv? asta e ideea la backtracking

[LordCronos]

cum sa-ti dea 1 2 3 si 1 3 2 ? Problema spune clar ca trebuie toate combinatiile a.i. o camila sa nu mai aiba in fata pe aceeasi care a avut-o initial !

so : n = 3 ( 1 2 3 )
vei avea solutie : 1 3 2, 2 1 3, 3 2 1.

Ce e gresit, ma rog, in rezolvarea mea?

1 3 2 e intradevar o solutie dar 1 2 3 e combinatia initiala !

ps: gandeste-o matematic mai intai
ps2: cum Dumnezeu faci tu backtracking nerecursiv? asta e ideea la backtracking

Inteleg ca vrei sa ma ajuti, dar nu trebuie sa suferi. Asta mi se cere la scoala, asta fac.

1 3 2, 2 1 3, 3 2 1.

Deci, in concluzie n=3
1 2 3 1 3 2 combinatiile posibile. Mai gandeste-te cand iei de pe net.

[IsTI37]

Nerecursiv ar insemna sa folosesti pur si simplu formula pentru combinatii.

[LordCronos]

Nerecursiv ar insemna sa folosesti pur si simplu formula pentru combinatii.

A.. Pai nu la asta ma refeream.. pur si simplu sa folosesc acest "back".

Code: Select all

int back(int st[],int top)
{
   top=1;
   init(st,top);
   while(top>0)
   {
      while(succesor(st,top))
      {
         if(valid(st,top))
         if(solutie(st,top))
         tipar(st,top);
         else
         {
            top++;
            init(st,top);
         }
      }
      top--;
   }
}

Informatica la mine la scoala e 0. Nici nu stiu ce face un "for" macar.