0

Hice este programa para encontrar el punto de silla en una matriz de 3*3, pero no funciona y cuando aparece el mensaje que indica donde está a veces no es

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

int LlenarMostrar (int Matriz[3][3]);
int Punto (int Matriz[3][3]);


int main () {

    int Matriz [3][3];

    printf("Punto de silla.\n\n");
    LlenarMostrar (Matriz);
    Punto (Matriz);

}

int LlenarMostrar (int Matriz[3][3]){

    int I, J;

    srand (time(NULL));

    for (I=0; I<3; I++){
        for (J=0; J<3; J++){
            Matriz[I][J]=rand()%10;
            printf("%i\t", Matriz[I][J]);   
        } printf("\n");
    }       
}

int Punto (int Matriz[3][3]){

    int I, J, K, P=10, P2=0, F=0, C=0; 

    for (I=0; I<3; I++){
        for (J=0; J<3; J++){
            if (P<Matriz[I][J]){
                P=Matriz[I][J];
                F=I;
                C=J;
            }
        }
        P2=P;
        for (K=0; K<3; K++){
            if (P>Matriz[K][F]){
                P=Matriz[K][F];
                }
            }
        if (P==P2){
        printf("\nEl punto de silla es %i en la fila %i y columna %i", P, F, C);
        }
        P=0;
        P2=0;
        F=0;
        C=0;
    }
}   

1 respuesta 1

1

Para empezar tu programa está asumiendo que el punto de silla se va a encontrar, necesariamente, en el valor más bajo de la fila:

for (J=0; J<3; J++){
    if (P<Matriz[I][J]){
        P=Matriz[I][J];
        F=I;
        C=J;
    }
}

Y no tiene por qué ser necesariamente así ya que el punto de silla representa la unión de un mínimo local y un máximo local (siendo ambos perpendiculares entre sí).

Así, en la siguiente matriz:

2 8 5
4 4 4
X X X

Tu algoritmo entendería que el punto de silla únicamente puede estar en (0,0) cuando realmente se encuentra en (0,2). Así, el 2 es un mínimo tanto el filas como en columnas mientras que el 5 es un mínimo en filas y un máximo en columnas. Además también puede suceder que en una misma fila (o columna) se encuentren varios puntos de silla:

3 8 4
2 2 2
X X X

Así, por tanto, tu algoritmo debería analizar, para cada celda, si es un máximo en una de las dos direcciones (filas o columnas) y mínimo en la otra... pero limitándose a las celdas adyacentes:

int Punto (int matriz[][3],int fila, int col)
{
  int chequeoFilaDer = 0;
  int chequeoFilaIzq = 0;
  int chequeoColArr  = 0;
  int chequeoColAbj  = 0;

  for( int f=fila+1 ; f < 3 && chequeoFilaDer == 0; ++f )
  {
    if( matriz[f][col] != matriz[fila][col] )
      chequeoFilaDer = matriz[fila][col] > matriz[f][col]? 1 : -1;
  }

  for( int f=fila-1; f >= 0 && chequeoFilaIzq == 0; --f )
  {
    if( matriz[f][col] != matriz[fila][col] )
      chequeoFilaIzq = matriz[fila][col] > matriz[f][col]? 1 : -1;
  }

  // maximo a un lado y minimo al otro o sin maximos ni minimos
  // sin maximos ni minimos -> toda la fila tiene le mismo valor
  if( chequeoFilaDer + chequeoFilaIzq == 0 )
    return 0;

  for( int c=col+1; c<3 && chequeoColAbj == 0; ++c )
  {
    if( matriz[fila][c] != matriz[fila][col] )
      chequeoColAbj = matriz[fila][col] > matriz[fila][c]? 1 : -1;
  }

  for( int c=col-1; c>=0 && chequeoColArr == 0; --c)
  {
    if( matriz[fila][c] != matriz[fila][col] )
      chequeoColArr = matriz[fila][col] > matriz[fila][c]? 1 : -1;
  }

  if( chequeoColArr + chequeoColAbj == 0 )
    return 0;

  int chequeoFila = chequeoFilaDer + chequeoFilaIzq;
  int chequeoCol  = chequeoColArr  + chequeoColAbj;

  // maximo + minimo =  1 - 1 =  0
  // maximo + maximo =  1 + 1 =  2
  // minimo + minimo = -1 - 1 = -2
  return chequeoFila + chequeoCol == 0; 
}

Y el main adaptado para la nueva función:

int main () {

  int Matriz [3][3];

  printf("Punto de silla.\n\n");
  LlenarMostrar (Matriz);

  for( int fila=0; fila<3; fila++ )
  {
    for( int col=0; col<3; col++ )
    {
      if( Punto(Matriz,fila,col) )
        printf("Punto de silla en (%d,%d) con valor %d\n",fila,col,Matriz[fila][col]);
    }
  }
}

Si te fijas en el algoritmo está asumiendo que ante una secuencia tal que:

2 2 2 4 X X X

Cualquiera de los doses forma parte de un mínimo local. Sin esta condición una matriz de 3x3 únicamente podría tener un punto de silla en su celda central, ya que el resto de celdas no tendría valores en uno de sus lados... con lo que va a ser imposible que la celda en cuestión esté rodeada de mínimos y máximos.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.