sábado, 18 de abril de 2009

Mostrar las palabras de Dick

Para calcular los caminos de Dick podemos usar una de las caracterizaciones que viene en wikipedia:

Cn es el número de caminos monótonos que se pueden trazar a través de las líneas de una malla de n × n celdas cuadradas, de forma que nunca se cruce la diagonal. Un camino monótono es aquél que empieza en la esquina inferior izquierda y termina en la esquina superior derecha, y consiste únicamente en tramos que apuntan hacia arriba o hacia la derecha. El recuento de estos caminos es equivalente a contar palabras de Dyck: X significa "moverse a la derecha" e Y significa "moverse hacia arriba".

Para calcular los caminos de Dick podemos usar una de las caracterizaciones que viene en wikipedia, relacionados con los numeros de Cataln Cn:

Cn es el número de caminos monótonos que se pueden trazar a través de las líneas de una malla de n × n celdas cuadradas, de forma que nunca se cruce la diagonal. Un camino monótono es aquél que empieza en la esquina inferior izquierda y termina en la esquina superior derecha, y consiste únicamente en tramos que apuntan hacia arriba o hacia la derecha. El recuento de estos caminos es equivalente a contar palabras de Dyck: X significa "moverse a la derecha" e Y significa "moverse hacia arriba".

Dado el manejo de indices en C, el criterio se adapta a la esquine superior izquierda de la matriz
Usaremos la palabra de Dick para simular un recorrido por la malla
Cada que aparezca un 0, incrementaremos X en 1
Cada que aparezca un 1, incrementaremos Y en 1
El citerio se cumple si al ir recorriendo la malla siempre se cumple que X<=Y



#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int valida_Dick(int *Dick,int n);
void imprimir_Dick(int *Dick,int n);

int main()
{
int i,j,n,k;//indice para calcular las palabras de Dick
int *Dick;//aqui se iran almacenando las palabras de dick temporalmente
//dentro de Dick, un 0 indica X, y un 1 indica Y
//leer el valor n
printf("\nDame el valor de n: ");
scanf("%d",&n);

Dick=(int *)malloc(2*n*(sizeof(int)));//dar espacio la palabra de dick, que es de tamano 2*n

//Aqui vamos a empezar a crear posibles palabras de Dick,
//para ver si es palabra de Dick valos a usar el criterio de la malla de nxn de que no pase de la diagonal
//Si es palabra de Dick, la imprimimos

//Para crear todos los caminos dentro de la malla (sean caminos de Dick o no),
//usaremos otra caracterizacion, que es que cada camino en la malla es la representacion binaria
//de los numeros de 0 a 2^(2*n)-1
for(i=0;i<pow(2,2*n);i++)
{
//llenamos Dick con al representacion binaria de i
k=i;
for(j=0;j<2*n;j++)
{
Dick[j]=k%2;
k=k/2;
}
//vemos si es palabra de dick valida para imprimirla
if (valida_Dick(Dick,n))
imprimir_Dick(Dick,n);
}
free(Dick);
return 0;
}
//---------------------------------------------------------------------------

void imprimir_Dick(int *Dick,int n)
{
int i;
//dentro de Dick, un 0 indica X, y un 1 indica Y
for(i=0;i<2*n;i++)
{
if(Dick[i]==0)
printf("X");
else
printf("Y");
}
printf("\n");
}

int valida_Dick(int *Dick,int n)
{
int i,X=0,Y=0,criterio=1;
//para validar si es palabra de Dick, usaremos el criterio de la malla de nxn, de que no debe pasar de la diagonal
//dado el manejo de indices en C, el criterio se adapta a la esquine superior izquierda de la matriz
//Usaremos la palabra de Dick para simular un recorrido por la malla
//Cada que aparezca un 0, incrementaremos X en 1
//Cada que aparezca un 1, incrementaremos Y en 1
//El citerio se cumple si al ir recorriendo la malla siempre se cumple que X<=Y
for(i=0;i<2*n;i++)
{
if(Dick[i]==0)
X=X+1;
else
Y=Y+1;
if(Y>X)//cumple criterio de la diagonal?
criterio=0;
if((X>n)||(Y>n))//se salio de la matriz?
criterio=0;
}
return criterio;
}

No hay comentarios:

Publicar un comentario