• Sábado 21 de Diciembre de 2024, 15:29

Mostrar Mensajes

Esta sección te permite ver todos los posts escritos por este usuario. Ten en cuenta que sólo puedes ver los posts escritos en zonas a las que tienes acceso en este momento.


Mensajes - rafaeljosem

Páginas: [1]
1
Diseño de Algoritmos / Ayuda Con Algoritmo
« en: Jueves 24 de Agosto de 2006, 22:48 »
Hola, tengo el siguiente ejercicio:

Aplicar el esquema de los algoritmos divide y venceras para que dadas las coordenadas (x, y) de dos puntos en el plano, que representen los extremos en un segmento, se dibuje el segmento.

Esto es lo que tengo, en codigo C:

Código: Text
  1.  
  2.  
  3. void ptomedio(double xmedio, double ymedio, double x1, double x2, double y1, double y2)
  4. {
  5.   int index;
  6.  
  7.   if (((xmedio > x1) && (ymedio > y1))||((xmedio > x2) && (ymedio > y2)))
  8.   {
  9.     x2 = xmedio;
  10.     y2 = ymedio;  
  11.  
  12.     contador++; //cuenta el nro de veces que se llama una funcion
  13.  
  14.     ptomedio ((x1+x2)/2.0, (y1+y2)/2.0, x1, x2, y1, y2); //haz lo mismo para la primera mitad
  15.  
  16.       x1 = xmedio;
  17.       y1 = ymedio;
  18.    
  19.     ptomedio ((x2 + xmedio)/2, (y2+ymedio)/2, x1, x2, y1, y2); //lo mismo para la 2da mitad
  20.    
  21.     for (index = contador; index > 0; index--)
  22.       printf(" ");
  23.  
  24.     printf(".");
  25.      
  26.     printf("\n");
  27.     contador--;
  28.  
  29.    
  30.   }
  31.  
  32.    
  33.  
  34. }
  35.  
  36.  

El algoritmo me funciona solo cuando el segmento tiene pendiente positiva. Necesito ayuda para hacerlo que funcione para pendiente negativa tambien.

Hice la llamada a la funcion de la sigte forma:

Código: Text
  1.  
  2.  
  3. ptomedio((2.0+1.0)/2.0,(5.0+4.0)/2.0, 1.0, 2.0, 3.0, 4.0);
  4.  
  5.  
  6.  

Gracias

2
C/C++ / Re: Ayuda Salto De Caballo (recursion Infinita)
« en: Domingo 20 de Agosto de 2006, 20:39 »
Ya pude resolver el problema. El codigo que habia puesto no tenia ningun error, el problema estaba en que al hacer N = 8, el programa buscaba la solucion dentro de un numero muy grande de combinaciones, por lo que demoraba demasiado tiempo. Me di cuenta al copiar otro codigo que encontre en internet, y me hacia lo mismo, asi que hice N = 5 y funciono  :D

3
C/C++ / Re: Ayuda Salto De Caballo (recursion Infinita)
« en: Domingo 20 de Agosto de 2006, 17:53 »
Hola, el codigo que escribi lo saque de un libro, en donde se esta tratando el tema de Backtracking, el problema es que la explicacion del libro no es muy buena (y al parecer el codigo que ellos presentan para este problema tiene errores), si podrias reconmendarme algun link en donde pueda encontrar informacion sobre backtracking, te lo agradecería.

Gracias

4
C/C++ / Ayuda Salto De Caballo (recursion Infinita)
« en: Domingo 20 de Agosto de 2006, 04:16 »
Hola

Necesito ayuda con el siguiente codigo, el problema es que la funcion saltocaballo() se llama a si misma infinitamente, no se que hacer.

Este programa tiene como objetivo buscar la secuencia de saltos ha de dar un caballo de ajedrez, partiendo de una casilla cualquiera, para pasar por cada una de las casillas del tablero

Código: Text
  1.  
  2.  
  3. #define N 8
  4. #define n (N+1)
  5.  
  6. void saltocaballo(int i, int x, int y, int *exito);
  7. void escribetablero();
  8.  
  9. int tablero[n][n];
  10. int d[8][2] = {{2,1}, {1,2}, {-1,2}, {-2,1},{-2,-1}, {-1,-2},
  11. {1,-2}, {2,-1}}; // los 8 posibles movimientos del caballo se obtienen sumando
  12.                         //estos valores con la posicion actual (x,y)
  13.  
  14.  
  15. int main(void)
  16. {
  17.  
  18.   int x, y;
  19.   int solucion, i, j;
  20.  
  21.   do{
  22.     printf("\nCoordenadas iniciales del caballo ");
  23.     scanf ("%d %d", &x, &y);
  24.  
  25.    
  26.     } while ((x<1) || (x > N) ||
  27.        (y < 1) || (y > N));
  28.  
  29.        //valores iniciales del tablero
  30.   for (i = 1; i <=N; i++)
  31.     for (j = 1; j<=N; j++)
  32.       tablero[i][j] = 0;
  33.  
  34.   tablero[x][y] = 1;
  35.  
  36.         //llamada con coordenadas iniciales y primer salto
  37.   solucion = 0;
  38.   saltocaballo (2,x,y,&solucion);
  39.  
  40.   if (solucion)
  41.   {
  42.     puts("\n\tEl Problema tiene solucion:\n");
  43.     escribetablero();
  44.   }
  45.   else
  46.     puts("No se ha encontrado solución al problema\n");
  47.    
  48.   putchar('\n');
  49.   system("PAUSE");
  50.   return 0;
  51. }
  52.  
  53. void saltocaballo(int i, int x, int y, int *exito)
  54. {
  55.   int nx, ny;
  56.   int k;
  57.   *exito = 0;
  58.   k = 0;  //inicializa el conjunto de posible movimientos
  59.  
  60.   do {
  61.     k++;
  62.    
  63.     nx = (x + d[(k-1)][0]);
  64.     ny = (y + d[(k-1)][1]);
  65.  
  66.               //determina si nuevas coordenadas son aceptables
  67.     if ((nx >= 1) &&(nx <= N) &&
  68.       (ny >= 1) && (ny <= N) &&
  69.       (tablero[nx][ny] == 0))
  70.     {
  71.       tablero[nx][ny] = i;  //anota movimiento
  72.       if (i < (N*N))
  73.       {
  74.        
  75.         saltocaballo((i+1), nx, ny, exito);
  76.         if (!(*exito)) //no se alcanzo solucion
  77.         {
  78.          
  79.           tablero[nx][ny] = 0; //se borra anotación
  80.         }
  81.       }
  82.       else
  83.         *exito = 1; //caballo ha cunierto el tablero
  84.     }
  85.   }while ((k < 8) && !(*exito));
  86.  
  87.  
  88. }
  89.  
  90.  
  91.  
  92.  

Páginas: [1]