Foro de elhacker.net

int upperTriangleDesc(const int **A, 
		      const int N)
{
// Start coding here
    return 0 ; 
}
 
int main(int argc, char *args[])
{
  int **A;
  int N;
  for( ; scanf("%d",&N)==1; )
    {
      if  ((A=(int**)malloc(N*sizeof(int *)))==NULL)
	{
	  perror("calloc");
	  exit(1);
	}
      for(int n=0;n<N;n++)
	{
	  if  ((A[n]=(int*)malloc(N*sizeof(int)))==NULL)
	    {
	      perror("calloc");
	      exit(1);
	    }
	  for(int m=0;m<N;m++)
	    if (scanf("%d",&A[n][m])!=1)
	      {
		perror("scanf");
		exit(1);
	      }
	}
      printf("upperTriangleDesc: %d\n",upperTriangleDesc((const int **)A,N));
      for(int n=0;n<N;n++)
	free(A[n]);
      free(A);
    }
  return 0;
}

int upperTriangleDesc(const int **A, const int N)
{
    int contador = 0;
    int i, a;
 
    for ( i = 1; i < N; i++)
    {
        for (a = 0; a <= contador; a++)
        {
            if (A[i][a] != 0) return 0; // Es incorrecta
        }
        contador++;
    }
 
    return 1 ; // Es correcta
}

int upperTriangleDesc(const int **A, const int N)
{
    int i, a;
 
    for (i = 1; i < N; i++)
    {
        for (a = 0; a <= (i-1); a++)
        {
            if (A[i][a] != 0) return 0; // Es incorrecta
        }
    }
 
    return 1 ; // Es correcta
}

• Se empieza en la fila 1
• Para cada fila i se recorren las columnas desde 0 hasta i-1.

int upperTriangleDesc(const int **A, const int N){
	int triangular_superior = 1;
	for(size_t i = 1; i < N && triangular_superior; ++i)
		for(size_t j = 0; j < i && triangular_superior; ++j)
			triangular_superior = (A[i][j] == 0);
	return triangular_superior;
} 

•  Date cuenta que contador=i-1. Luego esa variable es redundante, innecesaria! Basta a<i
•  Desde un punto de vista purista (ojo, esto no le quita valor a lo tuyo)... no es progrmacion estructurada... saliendo del bucle interno con return

int upperTriangleDesc(const int **A, const int N)
{
    int contador = 0;
    int i, a;
 
    for ( i = 1; i < N; i++)
    {
        for (a = 0; a <= contador; a++)
        {
            if (A[i][a] != 0) return 0; // Es incorrecta
        }
        contador++;
    }
 
    return 1 ; // Es correcta
}

•  La tecnica es estructurada, pero emplea 3 variables... trinangular_superior es redundante...

int upperTriangleDesc(const int **A, const int N){
	int triangular_superior = 1;
	for(size_t i = 1; i < N && triangular_superior; ++i)
		for(size_t j = 0; j < i && triangular_superior; ++j)
			triangular_superior = (A[i][j] == 0);
	return triangular_superior;
} 

 int upperTriangleDesc(const int **A, const int N, int pivot) {
    	if (pivot == N) return 1;
    	for (int i=0; i<N && pivot < N; i++)
	      if (A[pivot++][i] != 0) return 0;
	return upperTriangleDesc(A,N,N-i+1);
}

upperTriangleDesc((const int **)A,N,1)

int upperTriangleDesc(const int **A, const int N){
    size_t i = 1; j = 0; // Declaramos e inicializamos j para poder usarlo en la condicion del bucle externo
    while(i < N && !A[i][j]){
        // El bucle interno no tiene ninguna complicacion
        while(j < i && !A[i][j]){
            ++j;
        }
        // Ahora al salir tenemos dos situaciones:
        // - (j = i) y en tal caso la matriz todavia es triangular superior -> Incrementamos i y restablecemos j a 0 para recorrer otra fila
        // - (A[i][j] != 0) y en tal caso la matriz ya no es triangular superior -> No podemos modificar i ni j para que el bucle de fuera tambien termine
        if(j == i){
            ++i;
            j = 0;
        }
    }
    // Los bucles acaban cuando:
    // Un elemento no es nulo (A[i][j] != 0) -> !triangular
    // Llegamos al final (i == N) -> SI A[N-1][N-2] == 0 ENTONCES triangular SINO !triangular
    return (i == N && !A[N-1][N-2]);
} 

• Todos los elementos de la fila son nulos -> j = i -> triangular (de momento)
• El último elemento comprobado no era nulo -> j < i

int upperTriangleDesc(const int **A, const int N){
    size_t i = 1, j = 0;
    while(i < N && !j){
        while(j < i && !A[i][j]){
            ++j;
        }
        // Al salir: SI j < i ENTONCES A[i][j] != 0 SINO SI A[i][j-1] == 0 ENTONCES triangular (de momento) SINO !triangular
        j = (j < i) || A[i][j-1];
        ++i;
    }
    // Triangular <-> j = 0
    return !j;
} 

    int upperTriangleDesc(const int **A, const int N)
    {
        int i, a;
 
        for (i = 1; i < N; i++)
        {
            for (a = 0; a <= (i-1); a++)
            {
                if (A[i][a] != 0) return 0; // Es incorrecta
            }
        }
 
        return 1 ; // Es correcta
    }

upperTriangleDesc=A=>{
  for(i=1;i<A.length;++i) 
    for(j=0;j<i;++j)
      if(A[i][j])return 0
  ;return 1
}

int upperTriangleDesc(const int **A, const int N){
    size_t i = 1; j = 0; // Declaramos e inicializamos j para poder usarlo en la condicion del bucle externo
    while(i < N && !A[i][j]){
        // El bucle interno no tiene ninguna complicacion
        while(j < i && !A[i][j]){
            ++j;
        }
        // Ahora al salir tenemos dos situaciones:
        // - (j = i) y en tal caso la matriz todavia es triangular superior -> Incrementamos i y restablecemos j a 0 para recorrer otra fila
        // - (A[i][j] != 0) y en tal caso la matriz ya no es triangular superior -> No podemos modificar i ni j para que el bucle de fuera tambien termine
        if(j == i){
            ++i;
            j = 0;
        }
    }
    // Los bucles acaban cuando:
    // Un elemento no es nulo (A[i][j] != 0) -> !triangular
    // Llegamos al final (i == N) -> SI A[N-1][N-2] == 0 ENTONCES triangular SINO !triangular
    return (i == N && !A[N-1][N-2]);
} 

int upperTriangleDesc(const int **A, const int N){
    size_t i = 1, j = 0;
    while(i < N && !j){
        while(j < i && !A[i][j]){
            ++j;
        }
        // Al salir: SI j < i ENTONCES A[i][j] != 0 SINO SI A[i][j-1] == 0 ENTONCES triangular (de momento) SINO !triangular
        j = (j < i) || A[i][j-1];
        ++i;
    }
    // Triangular <-> j = 0
    return !j;
} 

j=(j<i)||A[i][j-1]
 

j=(j<i)
 

• Unas veces marca el indice de la columna 0<=j<N A[j] (while)
• Otras veces marca un predicado booleano {0,1} para saber si es triangular "pr el momento" j=(j<i)||A[j-1]

int upperTriangleDesc(const int **A, 
		      const int N)
{
  int i,j;
  for (i=1,j=0;i<N && j==i-1; i++)
    for(j=0; (j<i) && !A[i][j];j++); 
  return j==i-1 ;
}
 
// Outer loop
// I1: Q[N/i] and 1<=i<=M, 0<=j<i and ((j<i-1) -> A[i-1][j]!=0)
// Q1: i = min n : 1 <= n <=N and (n<N->(j<n-1 && ->A[n-1][j]!=0))): n nad
//     j = min m : 0 <= m < i and (m<i-1 -> A[i-1][m]!=0))): m
// Quote1(N-i)>=0
// Inner loop
// I2: Q2[N/j] and 0 <= j <= i and i < N 
// Q2: i<N and j = min m : 0 <= m <=i and (m<i -> A[i][m]!=0): m
// Quote2(N-j)>=0
 
 

int upperTriangleDesc(const int **A, 
		      const int N)
{
  int i,j;
  for (i=1,j=0;i<N && !j; i+=!j)
    for(j=i; j && !A[i][j-1];j--); 
  return i==N;
}
 
// Outer loop
// I1: Q[N/i] and 1<=i<=N, 0<=j<=i and ((j>0) -> (i<N and A[i][j-1]!=0))
// Q1: i = min n : 1 <= n <=N and (n<N->(j>0 && ->A[n][j-1]!=0))): n nad
//     j = max m : 0 <= m <= i and (m>0 -> i<N && A[i][m-1]!=0))): m
// Quote1(N-i-j)>=0
// Inner loop
// I2: Q2[N/j] and i<N and 0 <= j <= i
// Q2: i<N and j = max m : 0 <= m <=i and (m>0 -> A[i][m-1]!=0): m
// Quote2(N-j)>=0
 

 return (N == 1 || (i == N && !A[N-1][N-2])); 

 j=(j<i)||A[i][j-1] 

 j=(j<i)