Mensajes

Hola buenas, os comento. Estoy desarrollando un algoritmo muy básico de ordenación que me han pedido para clase, no uno existente, sino uno que se nos ocurra. Se que en este campo ya hay mucho escrito pero me parece que la mejor forma de aprender es intentarlo uno mismo, sin buscar ideas por internet, por lo menos a priori. Asi que sin conocer ningún algoritmo de ordenación, y sin tener en cuenta la eficiencia de mi solución esto es lo que he hecho. El algoritmo funciona "a medias". Se ve a simple vista:

Código (c) [Seleccionar] Expandir


#define BIGGEST 32767

void sort(int *non_sorted, int *sorted, int size)
{
//Flags
int *beggining = non_sorted;
int *end = (non_sorted + size);

//Pointers
int *current = beggining;

//Vars
int n_sorted = 0;
int last_minor_found = BIGGEST;
int last_sorted = 0;


while(n_sorted < size)
{
//Find minor bigger than last sorted
while(current != end)
{
if(*current < last_minor_found && *current > last_sorted)
{
last_minor_found = *current;
}
current++;
}

//Save in sorted array
*sorted = last_minor_found;
sorted++;
n_sorted++;

//Reinicialize
last_sorted = last_minor_found;
current = beggining;
last_minor_found = BIGGEST;
}
}


Output 1:

Código [Seleccionar] Expandir


Enter size of array: 10  
Non sorted array:
67  69  29  80  14  61  88  99  4  58  
Sorted array:
4  14  29  61  67  69  80  88  99  32767




El problema viene cuando se repite algun numero.

Aqui se ve mas evidente, ordena hasta el cien, y luego pone el maximo. En vez de poner consecutivamente los repetidos.

Código [Seleccionar] Expandir


Enter size of array: 200
Non sorted array:
2  21  85  19  70  91  82  93  29  100  76  34  85  81  61  9  31  28  75  76  37  53  42  40  12  74  16  66  88  68  49  41  40  85  60  61  75  93  53  3  92  80  89  29  60  49  89  90  28  64  17  64  16  59  55  27  84  22  44  71  41  44  64  80  81  75  41  55  67  45  10  10  25  50  38  84  50  79  26  77  42  42  92  9  52  46  88  36  68  31  58  8  27  73  40  7  47  80  13  65  76  74  75  100  75  64  36  24  42  13  52  35  6  43  44  58  89  31  45  56  61  54  15  39  27  54  97  25  85  62  90  61  35  16  12  10  79  99  33  73  11  37  7  69  79  50  78  67  80  22  74  93  27  41  31  5  94  80  30  31  41  71  43  75  86  54  36  64  5  21  36  67  57  43  35  35  44  12  54  24  85  79  16  12  19  98  68  65  77  49  95  17  19  89  44  4  42  79  20  98 
Sorted array:
2  3  4  5  6  7  8  9  10  11  12  13  15  16  17  19  20  21  22  24  25  26  27  28  29  30  31  33  34  35  36  37  39  40  41  42  43  44  45  47  49  50  52  53  54  56  57  58  60  61  62  64  65  66  67  68  69  70  71  73  74  75  76  77  78  79  80  81  82  85  86  88  89  90  91  92  93  94  95  98  99  100  100  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767  32767

Gracias de antemano!

Hola, no se exactamente que problemas puedes tener en el código. Pero por lo que recuerdo, uno de los algoritmos mas usados para encontrar la ruta es el algoritmo A Star.

http://en.wikipedia.org/wiki/A*_search_algorithm

Si mal no recuerdo, habia hecho la implementación siguiendo esta guia:
http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/a-pathfinding-for-beginners-r2003
(disponible español en http://www.policyalmanac.org/games/articulo1.htm)

y este tambien:
http://www.raywenderlich.com/4946/introduction-to-a-pathfinding

necesitas dos listas enlazadas.  Por lo menos leyendo esas guias puedas darte una idea de como sacar la ruta mas eficiente.

Saludos.

Me he estado mirando el algoritmo que me dices y he sacado alguna idea que puedo aplicar aqui, pero no exactamente lo que me piden en el problema, de hecho es más simple. El programa no tiene que buscar la ruta mas eficiente, basta con una de las rutas, y aunque esta sea un mero "caminito" más que un laberinto.(Como el del ejemplo) Este codigo deberia servir para lo que me piden, pero por algun lado peta.
Gracias por la ayuda!

te digo, tu código es más largo de lo que la mayoría intentarán leer también

procura usar las etiquetas GeSHi para publicad código (ya que si no es más difícil de leer)

por ultimo te recomiendo usar el debugger y correr las instrucciones paso a paso para poder ver cual es el error en tu logica más facilmente

Gracias, no sabia como resaltar el texto! Voy a intentar con el debugger, a ver si consigo algo.

Hola buenas a todos. Soy alumno de primero de carrera de ingeniería de software y me dirijo a esta comunidad (otra vez) para pedir ayuda a la voz de la experiencia con un problema en el que estoy atascado.
El ejercicio consiste en hacer un programa en C que sea capaz de resolver un laberinto simple, un camino, que se le ha de pasar al programa por la entrada de texto. El laberinto tiene que ser de 32x32 caracteres binarios, siendo los 0s los espacios vacíos.
Y ha de guardarse en un array bidimend¡sional para trabajar con él.
Tal que así:

Código [Seleccionar] Expandir


11111011111111111111111111111111
11111011111111111111111111111111
11111011111111111111111111111111
11111011111111111111111111111111
11111011111111111111111111111111
11111000000000000000000111111111
11111111111111111111110111111111
11111111111111111111110111111111
11111111111111111111110111111111
11111111111111111111110111111111
11111111111111111111110111111111
11111111111111111111110111111111
11111100000000000000000111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111101111111111111111111111111
11111100000000000000000000000011
11111111111111111111111111111011
11111111111111111111111111111011
11111111111111111111111111111011
11100000000000000000000000000011
11101111111111111111111111111111
11101111111111111111111111111111
11101111111111111111111111111111
11101111111111111111111111111111
11101111111111111111111111111111
11100000000000000000000000011111
11111111111111111111111111011111


Y la salida del programa ha de darte los movimientos que ha seguido el programa para completar el laberinto. También he hecho que imprima las coordenadas de la posición actual en cada movimiento.

El problema viene cuando al pasarle el laberinto, el programa avanza solo unas pocas posiciones o entra en un bucle. Dando salidas como estas:

Posicion inicial 0x0(ni un avance)

Código [Seleccionar] Expandir

Array guardado
Mi posicion inicial: 0 x 0

Posicion inicial 3x5 (avanza varias y luego se para)

Código [Seleccionar] Expandir

Array guardado
Mi posicion inicial: 3 x 5
Down Mi posicion: 4 x 5
Down Mi posicion: 5 x 5
Right Mi posicion: 5 x 6
Right Mi posicion: 5 x 7


Posicion 5x22 (Idem)

Código [Seleccionar] Expandir

Array guardado
Mi posicion inicial: 5 x 22
Down Mi posicion: 6 x 22
Down Mi posicion: 7 x 22


Posicion 5x9 (Entra en bucle)

Código [Seleccionar] Expandir

Array guardado
Mi posicion inicial: 5 x 9
Right Mi posicion: 5 x 10
Right Mi posicion: 5 x 11
Left Mi posicion: 5 x 10
Right Mi posicion: 5 x 11
Left Mi posicion: 5 x 10
Right Mi posicion: 5 x 11
Left Mi posicion: 5 x 10
Right Mi posicion: 5 x 11
Left Mi posicion: 5 x 10
Right Mi posicion: 5 x 11


Evidentemente algo en la lógica o en el algoritmo esta mal, pero no consigo encontrar el fallo.

Este es mi código:

Código (c) [Seleccionar] Expandir

#include<stdio.h>


main()
{
int position_fila;
int position_columna;
int ultima_pos_fila, ultima_pos_col;
int sig_fila, sig_columna, ant_fila, ant_columna;
int laberinto[32][32];
int v,t,c,i,x,j, nc;
nc = 0;

position_fila = 0;
position_columna = 0;
sig_fila = position_fila + 1;
sig_columna = position_columna + 1;
ant_fila = position_fila - 1;
ant_columna = position_columna - 1;
ultima_pos_fila = ultima_pos_col = 0;

v = 1;
nc = 0;

for(i=0;i<32;i++)
{
for(j=0;j<32;j++)
{
laberinto[i][j] = 0;
}
}



//Guardar entrada en array bidimensional "laberinto"

for(i=0;i<32;i++)
{
for(j=0;j<32;j++)
{
c = getchar();
switch(c)
{
case '1':
{
laberinto[i][j] = 1;
break;
}
case '0':
{
laberinto[i][j] = 0;
break;
}
case '\n':
{
j = j - 2;
break;
}
default:
break;

}
}
}

//Imprimir laberinto

printf("Array guardado\n");

for(i=0;i<32;i++)
{
for(j=0;j<32;j++)
{
printf("%d", laberinto[i][j]);
++nc;
if(!(nc%32))
printf("\n");
}
}





//Averiguar posicion inicial

for(t = 0; t < 32; t++)
{
v = laberinto[0][t];
if(v == 0)
{
position_columna = t;
break;
}
}


printf("Mi posicion inicial: %d x %d\n", position_fila, position_columna);


//Resolucion

for(x = 0; x < 50;x++)
{

// 2 Condiciones:
//[1] Si puedo moverme hacia abajo  (Si el elemento bajo mi posicion es 0).
//[2] Que no haya estado antes en esa posicion (si mi ultima posicion no es igual a la siguiente).

if((!(laberinto[sig_fila][position_columna])) && (sig_fila != ultima_pos_fila))
{
ultima_pos_fila = position_fila; //Guardas ultima posicion
++position_fila; //Mueves hacia abajo
printf(" Down ");
printf("Mi posicion: %d x %d\n", position_fila, position_columna);
}

// 2 Condiciones:
//[1] Si puedo moverme hacia la derecha (Si el elemento a la derecha mi posicion es 0).
//[2] Que no haya estado antes en esa posicion (si mi ultima posicion no es igual a la siguiente).

else if((!(laberinto[position_fila][sig_columna])) && (sig_columna != ultima_pos_col))
{
ultima_pos_col = position_columna; //Guardas ultima posicion
position_columna++; //Mueves hacia la derecha
printf(" Right ");
printf("Mi posicion: %d x %d\n", position_fila, position_columna);
}

// 2 Condiciones:
//[1] Si puedo moverme hacia arriba  (Si el elemento sobre mi posicion es 0).
//[2] Que no haya estado antes en esa posicion (si mi ultima posicion no es igual a la siguiente).

else if((!(laberinto[ant_fila][position_columna])) && (ant_fila != ultima_pos_fila))
{
ultima_pos_fila = position_fila; //Guardas ultima posicion
position_fila--; //Mueves hacia arriba
printf(" Up ");
printf("Mi posicion: %d x %d\n", position_fila, position_columna);
}

// 2 Condiciones:
//[1] Si puedo moverme hacia la izquierda (Si el elemento a la izquierda mi posicion es 0).
//[2] Que no haya estado antes en esa posicion (si mi ultima posicion no es igual a la siguiente).

else if((!(laberinto[position_fila][ant_columna])) && (ant_columna != ultima_pos_col))
{
ultima_pos_col = position_columna; //Guardas ultima posicion
position_columna--; //Mueves hacia izquierda
printf(" Left ");
printf("Mi posicion: %d x %d\n", position_fila, position_columna);
}

}

}


Muchas gracias de antemano por cualquier ayuda y un saludo a la comunidad elhacker!

Gracias por la explicación! Ha sido vital para resolver el problema!
Asi ha quedado finalmente:

Código [Seleccionar] Expandir


#include <stdio.h>



main()
{
int c,i;
int index[20];
int n_char = 0;
int h,t;


/* Inicialización del array */

for( i = 0; i < 20; ++i)
{
index[i]=0;
}

/* Contador de longitud */

while ((c = getchar()) != EOF)
{ if ( c != ' ' && c != '\n' && c != '\t' )
{
++n_char;
}
else if ( n_char > 0 )
{
index[n_char]++;
n_char = 0;
}

}

/* Impresión del histograma */

for(t = 1; t < 20; ++t)
{
printf("%4d Caracteres: ", t);
for(h = 0; h < index[t]; ++h)
{
printf("=");
}
printf("\n");
}

}


Hola a todos!

soy estudiante de ingeniería y estoy tratando de resolver un ejercicio. Un programa que muestre un histograma de las longitudes de las palabras de un texto
de entrada (usando la entrada estándar). Mi codigo es este:

#include <stdio.h>
#define IN 1
#define OUT 0


main()
{
   int c,i;
   int state;
   int index[10];
   int n_char = 0;
   int n_words = 0;
   state = OUT;
   
   
   
   for( i = 0; i < 10; ++i)
   {
      index = 0;
   }
   
   
   
   while( c = getchar() != EOF )
   {   if (state == IN)
      {
         n_char = n_char + 1;
         printf("%d\n", n_char);
      }
      if( c = ' ' || c == '\n' || c == '\t' )
      {
         state = OUT;
         index[n_char] = index[n_char] + 1;
      }
      else if ( state == OUT )
      {
         state = IN;
         ++n_words;
      }
      
   }
   printf("%d\n", index[0]);
   printf("%d\n", index[1]);
   printf("%d\n", index[2]);
   printf("%d\n", index[3]);
   printf("%d\n", index[4]);
   printf("%d\n", index[5]);
   printf("%d\n", index[6]);
   printf("%d\n", index[7]);
   printf("%d\n", index[8]);
   printf("%d\n", index[9]);
   
}

Al ejecutarlo, en lugar de guardar el número de palabras de X número de caracteres en cada posición del array, introduce el numero total de caracteres del texto siempre en la misma posicion del array. Que estoy haciendo mal?
Gracias de antemano!