Chair point in a random number matrix

Question

Chair point in a random number matrix

Navigation

#1 by (0 votes)

0

I did this program to find the saddle point in a 3 * 3 matrix, but it does not work and when the message appears that indicates where it is sometimes it is not

#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;
    }
}

c matrices

asked by Steven Medina 08.10.2017 в 19:23

source

1 answer

Dump program output to file Fatal Error Visual Studio Code / git

score 0 · Answer 1

To begin with, your program is assuming that the saddle point will necessarily be found at the lowest value in the row:

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

And it does not necessarily have to be that way since the saddle point represents the union of a local minimum and a local maximum (both being perpendicular to each other).

So, in the following matrix:

2 8 5
4 4 4
X X X

Your algorithm would understand that the saddle point can only be in (0,0) when it is actually in (0,2). Thus, 2 is a minimum both rows and columns while 5 is a minimum in rows and a maximum in columns. In addition it can also happen that in the same row (or column) are several saddle points:

3 8 4
2 2 2
X X X

So, therefore, your algorithm should analyze, for each cell, whether it is a maximum in one of the two directions (rows or columns) and minimum in the other ... but limited to adjacent cells:

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; 
}

And the main adapted for the new function:

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]);
    }
  }
}

If you look at the algorithm, you are assuming that in a sequence such that:

2 2 2 4 X X X

Any of the deuces is part of a local minimum. Without this condition, a 3x3 matrix could only have one saddle point in its central cell, since the rest of the cells would not have values on one of its sides ... thus it will be impossible for the cell in question to be surrounded of minimums and maximums.