Titlul: Triangulatii!
Scris de: CHERA Laurentiu din Septembrie 04, 2008, 16:09:34
Salut!
Vreau sa imi prezentati, daca se poate, o metoda de afisare a triangulatiilor unui patrulater convex!
Numarul lor il pot afla din formula lui Catalan!
Va multumesc!
Titlul: Răspuns: Triangulatii!
Scris de: Filip Cristian Buruiana din Septembrie 04, 2008, 16:45:27
Poti folosi metoda backtracking (http://en.wikipedia.org/wiki/Backtracking).
Poti face asa: consideri un vector st in care sti reprezinta celalalt capat al diagonalei care contine varful i din poligon sau 0, daca din varful i nu pleaca nicio diagonala. Poti impune i < sti. Conditia ca 2 diagonale (i sti) (j stj) sa nu se intersecteze este ca i <= j, stj <= sti sau j <= i, sti <= stj.
Titlul: Răspuns: Triangulatii!
Scris de: CHERA Laurentiu din Septembrie 04, 2008, 16:52:40
Structura(algoritmul) backtracking o(il) stiu, dar as vrea sa vad codul functiei valid . :D
Multumesc pentru informatii!
Titlul: Răspuns: Triangulatii!
Scris de: Filip Cristian Buruiana din Septembrie 04, 2008, 17:28:08
Stai ca nu merge cum spuneam mai sus ca pot fi mai multe diagonale care pleaca din acelasi varf :D. Cel mai simplu este sa consideri toate diagonalele si la fiecare pas verifici daca poti sau nu sa pui diagonala curenta: #include <stdio.h>
typedef struct { int x, y; } diagonala;
int N;
diagonala D[1024]; int nr_diagonale;
int st[1024]; // st[i] = 1 <=> am selectat diagonala i
int between(int x, int r1, int r2)
{ return (r1 <= x && x <= r2); }
int intersect(int i1, int i2)
{
return (D[i1].x != D[i2].x && D[i1].x != D[i2].y && D[i1].y != D[i2].x && D[i1].y != D[i2].y &&
between(D[i1].x, D[i2].x, D[i2].y) + between(D[i1].y, D[i2].x, D[i2].y) == 1);
}
void back(int nivel)
{
int i;
if (nivel == nr_diagonale + 1)
{
int j = 0;
for (i = 1; i <= nr_diagonale; ++i)
j += st[i];
if (j == N-3) // daca am selectat N-3 diagonale afisam
{
for (i = 1; i <= nr_diagonale; ++i)
if (st[i])
printf("(%d %d) ", D[i].x, D[i].y);
printf("\n");
}
return ;
}
st[nivel] = 0; back(nivel+1); // nu selectam diagonala
// verificam daca putem sa o selectam
if (st[1] && nivel == 2)
i = 0;
for (i = 1; i < nivel; ++i)
if (st[i] && intersect(i, nivel))
return ;
st[nivel] = 1; back(nivel+1);
}
int main(void)
{
int i, j;
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; ++i)
for (j = i+1; j <= N; ++j)
{
if (i+1 == j || (i == 1 && j == N)) continue;
++nr_diagonale;
D[nr_diagonale].x = i;
D[nr_diagonale].y = j;
}
i = intersect(2, 3);
back(1);
return 0;
}
Sunt multe optimizari care pot fi facute si poti imbunatati programul de mai sus. Functia valid la care te referi poate fi ceva de genul: int between(int x, int r1, int r2)
{ return (r1 <= x && x <= r2); }
int intersect(int i1, int i2)
{
return (D[i1].x != D[i2].x && D[i1].x != D[i2].y && D[i1].y != D[i2].x && D[i1].y != D[i2].y &&
between(D[i1].x, D[i2].x, D[i2].y) + between(D[i1].y, D[i2].x, D[i2].y) == 1);
}
int valid()
{
int i;
for (i = 1; i < nivel; ++i)
if (st[i] && intersect(i, nivel))
return 0;
return 1;
}
|