elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.


 


Tema destacado: Accede Canal Oficial Telegram de elhacker.net


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, YreX-DwX)
| | |-+  [ALGEBRA DE MATRICES] Matriz triangular INFERIOR DESCENDIENTE en C.
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [ALGEBRA DE MATRICES] Matriz triangular INFERIOR DESCENDIENTE en C.  (Leído 858 veces)
dijsktra

Desconectado Desconectado

Mensajes: 98


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
[ALGEBRA DE MATRICES] Matriz triangular INFERIOR DESCENDIENTE en C.
« en: 4 Mayo 2020, 22:24 »

dijsktra deberías de poner mas retos como este  :P

Va por el fary !

 Nuestros hermanos de América puede que no sepan quien es el Fary... Es... el "más cantante de España",,,   https://www.youtube.com/watch?v=XLZO3DGRrfY
(Parodia de lo mal que hablan los "gallegos"!!)

A vueltas con las matrices... Se trata ahora de comprobar si una matriz es triangular inferior descendiente...


Yo lo he hecho de arriba a bajo. Es similar, pero es como si a un zurdo le mandaran escribir con la derecha, o a un diestro con la izquierda...

Vale el mismo código base de

https://foro.elhacker.net/programacion_cc/algebra_de_matrices_matriz_triangular_superior_desdendiente_en_c-t504451.0.html;msg2220794#msg2220794

Código
  1. int lowerTriangleDesc(const int **A,
  2.      const int N)
  3. {
  4.  // Start code here.
  5.  return 1;
  6. }

De nuevo, el que más simple/bonito lo hace, (no el que termine antes, como en los concursos) gana!

Ojo , YreX-DwX, no se te olivde que tienen que valer para matrices N>=1 columnas....

Ejemplos de entrada de casos son...
EN DOS DIAS PONGO LA SOLUCION
Código:
3
1 0 0
0 1 0
0 0 1
lowerTriangleDesc: 1
3
1 2 3
0 4 5
0 0 6
lowerTriangleDesc: 0
3
1 2 3
2 4 5
0 0 6
lowerTriangleDesc: 0
5
1 0 0 0 0
1 2 0 0 0
1 2 3 0 0
1 2 3 4 0
1 2 3 4 5
lowerTriangleDesc: 1
5
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
lowerTriangleDesc: 1
1
1
lowerTriangleDesc: 1
1
0
lowerTriangleDesc: 1



En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
YreX-DwX
Moderador
***
Desconectado Desconectado

Mensajes: 702



Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular INFERIOR DESCENDIENTE en C.
« Respuesta #1 en: 5 Mayo 2020, 18:01 »

Hmm... Veo demasiada similitud con el otro tema. Esto me da que pensar si será tan simple o hay alguna otra forma escondida. Le he dado muchas vueltas a ver si encontraba una alternativa como ir reduciendo la matriz por recursividad, pero no es posible (o eso me ha parecido, tengo un poco olvidado el trabajo directo con memoria...) al no ser una matriz como tal contigua en memoria.

Así que aprovecharé para sacarme la espinita que se me quedó con el otro tema...
Ojo , YreX-DwX, no se te olivde que tienen que valer para matrices N>=1 columnas....
Y tranquilo, ya no me olvidaré de las matrices de orden 1 :xD :xD

Código
  1. int lowerTriangleDesc(const int **A, const int N){
  2.    int i, j = N;
  3.    for(i = 0; i < N-1 && j == N; ++i)
  4.        for(j = i+1; j < N && !A[i][j]; ++j);
  5.    return j == N;
  6. }

PD: Sigo pensando que hay alguna solución oculta sorprendente. No dormiré tranquilo hasta ver la solución. :xD


En línea

Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
dijsktra

Desconectado Desconectado

Mensajes: 98


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular INFERIOR DESCENDIENTE en C.
« Respuesta #2 en: 6 Mayo 2020, 00:03 »

Hmm... Veo demasiada similitud con el otro tema.

Tienes razon. YreX-DwX... No me ha quedado bien.... :-( :-( Era muy similar al otro.... Y la solucion que pones es implecable...

Código
  1. int lowerTriangleDesc(const int **A, const int N){
  2.    int i, j = N;
  3.    for(i = 0; i < N-1 && j == N; ++i)
  4.        for(j = i+1; j < N && !A[i][j]; ++j);
  5.    return j == N;
  6. }

yo habia propuesto

Código
  1. int lowerTriangleDescBis(const int **A,
  2. const int N)
  3. {
  4.  int i,j;
  5.  for (i=N-1,j=N; i && (j==N); i-=(j==N))
  6.    for(j=i; j<N && !A[i-1][j];j++);
  7.  return !i;
  8. }

PD: Sigo pensando que hay alguna solución oculta sorprendente. No dormiré tranquilo hasta ver la solución. :xD

  VAMOS A HACERLO DIFICIL, PERO DIFICILISMO !

Todo el mundo ve que hay dos bucles y dos variables

ESTE ES EL RETO:


PROGRAMAR LA SOLUCION USANDO SOLO UN BUCLE Y UNA SOLA VARIABLE DE CONTROL, A PARTE DE LAS QUE SE DAN POR PARAMETRO

(Por supuesto, el programa sera mas dificil de legible, pero sera igualmente correcto....)


No me pidais la solucion en un dia que no se si tendre tiempo... Se que se puede, y tengo que hacerla...
y tu, YreX-DwX, m'as vale que duermas un poco...que te puedes volver tarumba... :rolleyes: :rolleyes:


En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
YreX-DwX
Moderador
***
Desconectado Desconectado

Mensajes: 702



Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular INFERIOR DESCENDIENTE en C.
« Respuesta #3 en: 6 Mayo 2020, 05:43 »

  VAMOS A HACERLO DIFICIL, PERO DIFICILISMO !

Todo el mundo ve que hay dos bucles y dos variables

ESTE ES EL RETO:

PROGRAMAR LA SOLUCION USANDO SOLO UN BUCLE Y UNA SOLA VARIABLE DE CONTROL, A PARTE DE LAS QUE SE DAN POR PARAMETRO

(Por supuesto, el programa sera mas dificil de legible, pero sera igualmente correcto....)

Esto sí que promete.  ;-) ;-)
Después de darle unas cuantas vueltas creo que está cerca pero no consigo sacarlo así que dejo mi razonamiento por si alguien se anima a seguir mientras yo duermo... (Espero no soñar con esto :rolleyes:)

La idea es tratarlo algo así como un array unidimensional, es decir, un único índice que se incrementa desde 1 hasta n siendo n el número de casillas a recorrer. Resulta que n = (N*(N-1)/2). Iremos incrementando el contador en 1 a no ser que una casilla no sea nula en cuyo caso podemos concluir que esa matriz no es triangular inferior.
Código:
i := 1
MIENTRAS i <= (N*(N-1)/2) and i != 0 ENTONCES
    i = (A[f(i)][g(i)] == 0) * (i+1)
FIN MIENTRAS
RETURN i
Como se puede apreciar falta definir las funciones f() y g() que determinen la fila y columna del siguiente elemento en función de i.

Parece sencillo usando los operadores de división entera y módulo pero no es tan simple. Probando con matrices de orden N >= 2 (ya que de orden 1 sería triangular sin entrar por el bucle) he encontrado lo siguiente:
Código:
N = 2 -> M = (N*(N-1)/2) = 1
i    -> 1
f(i) -> 0
g(i) -> 1

N = 3 -> M = 3
i    -> 1 - 2 - 3
f(i) -> 0 - 0 - 1
g(i) -> 1 - 2 - 2

N = 4 -> M = 6
i    -> 1 - 2 - 3 - 4 - 5 - 6
f(i) -> 0 - 0 - 0 - 1 - 1 - 2
g(i) -> 1 - 2 - 3 - 2 - 3 - 3

N = 5 -> M = 10
i    -> 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10
f(i) -> 0 - 0 - 0 - 0 - 1 - 1 - 1 - 2 - 2 - 3
g(i) -> 1 - 2 - 3 - 4 - 2 - 3 - 4 - 3 - 4 - 4

N = 6 -> M = 15
i    -> 01 - 02 - 03 - 04 - 05 - 06 - 07 - 08 - 09 - 10 - 11 - 12 - 13 - 14 - 15
f(i) -> 00 - 00 - 00 - 00 - 00 - 01 - 01 - 01 - 01 - 02 - 02 - 02 - 03 - 03 - 04
g(i) -> 01 - 02 - 03 - 04 - 05 - 02 - 03 - 04 - 05 - 03 - 04 - 05 - 04 - 05 - 05
Y así sucesivamente. Yo creo que se ve perfectamente el patrón. El problema como ya he dicho es sacar la que sería la fórmula cerrada de f() y g().
Si alguien se quiere animar a intentar seguir o a exponer su razonamiento... :rolleyes: :rolleyes:
En línea

Código
  1. cout << "Todos tenemos un defecto, un error en nuestro código" << endl;
fary
Colaborador
***
Desconectado Desconectado

Mensajes: 957



Ver Perfil WWW
Re: [ALGEBRA DE MATRICES] Matriz triangular INFERIOR DESCENDIENTE en C.
« Respuesta #4 en: 6 Mayo 2020, 14:51 »

Hola, no había visto esto... ¿No es mejor crear otro tema para no mezclar todo?  ;-) ;-)

saludos!
En línea

Un byte a la izquierda.
NEBIRE


Desconectado Desconectado

Mensajes: 2.229


Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular INFERIOR DESCENDIENTE en C.
« Respuesta #5 en: 6 Mayo 2020, 18:22 »

No es más complicado hacerlo en un solo bucle, tan solo es cuestión de precisar más cálculos (tampoco muchos más), que la simpleza de dos bucles ofrece...

(nota: Estoy tomando como ejemplo el triangulo de la otra ocasión ya que es trivial modificarlo a cualquiera de las esquinas.
Igualmente la nomenclatura de: (derecha izquierda, superior, inferior) no tiene más punto que ponerse de acuerdo. Personalmente entiendo que acomoda más denominarla conforme a la esquina que ocupa al vértice del triángulo que conecta solo con ceros, y que para el ejemplo a continuación es: inferior-iizquierda).

Para entender el mecanismo subyacente hay que estudiar un poquito la matriz.
...y  atribuir algunos estados que nos permitan dar flujo al cálculo

 Matriz: 0-35 ceros saltos  index ini
 5 6 0 8 2 3 - 0  - 6          00 - estado de escape
 0 4 3 9 0 0 - 1  - 5          06
 0 0 1 5 3 4 - 2  - 4          12
 0 0 0 5 2 0 - 3  - 3          18
 0 0 0 0 7 0 - 4  - 2          24
 0 0 0 0 0 6 - 5  - 1          30 - estado inicial
 x x x x x x                   xx - estados de cambio
                         ancho + 1: estado de avance


Explicando la tabla...
- Lo obvio es que los ceros aumentan en uno con cada fila... en la columna fila se ha puesto una columna que lleva dicha cuenta. Una funcion podría simplemente contar cuando son 0 y devolcerá TRUE cuando sea el sumatorio de dicha serie. Aunque claramente es más ineficiente que devolver false tan pronto un valor no cumple la restricción.
- La columna saltos, indica cuantos hay que omitir tras recorrer los 0. Algo tangible es que 'ceros + saltos = ancho, pués por algo son los elementos en una fila.
- He añadido una última columna que señala los índices (de un array unidimensional) que suponen el primer elemento de cada fila.

En el algoritmo a continuación se empieza por el vértice que da nombre al triángulo (ver nota arriba), y recorre en diagonal (en el ejemplo) hacia abajo y a la derecha... Así he añadido algunos estados para terminar de entender...
El estado inicial es pués 30 : index = (size- ancho)
En cada ciclo aumentará: index += (ancho +1)
Cuando se alcanza un valor de index en los 'estados de cambio', justamente el enésimo valor que ocupa en esa fila (fuera de la matriz), es lo mismo que señalar la fila siguiente a la que saltar (pués es simétrico, considerando justamente como vértice del triángulo la esquina antedicha en la nota superior).
El bucle termina cuando alcanza el estado de escape, que para este triángulo será el índice 0.

...y ahora el pseudocódigo (que cualquiera puede traducir a cualquier lenguaje, ya que el problema no es un problema restrictivo a ningún lenguaje específico, es decir no es un problema de ningún lenguaje si no de algoritmia)...
Código:
Buleano = Funcion EsMTID(array byte Valores(), entero Ancho, entero Size)
    entero index
   
    index = (Size - Ancho)
    Hacer
        Si (Valores(index) <> 0) Devolver False  // *
        index = (index + Ancho + 1)
       
        Si (index > Size)      // conocemos la fila a la que saltar por el sobrante: (Index Modulo Ancho)
            index = (Size - (Ancho * (1 + (index Modulo Ancho))))
        fin si
    Repetir Mientras  (index > 0)
   
    Devolver True
Fin Funcion
* Sí, también reconoce correctamente el caso de una matriz de 1x1
En línea

dijsktra

Desconectado Desconectado

Mensajes: 98


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular INFERIOR DESCENDIENTE en C.
« Respuesta #6 en: 13 Mayo 2020, 11:45 »

...y ahora el pseudocódigo (que cualquiera puede traducir a cualquier lenguaje, ya que el problema no es un problema restrictivo a ningún lenguaje específico, es decir no es un problema de ningún lenguaje si no de algoritmia)...

Tengo que dejar claro que su idea es la que más me ha gustado.
Comentarios...
  • Mete  una variable mas, size, que no es m'as que ancho*ancho, luego se puede enmendar
  • No es programacion estructurada (return 0) pero eso es facilmente enmendable.Ojo!, no digo que no sea válida en C, digo que no es C-estructurada
  • La construccion "repeat until", no es la adecuada. De hecho para N=1, el algoritmo falla. Pero es facilmente enmendable

Con las ligeras enmiendas... El pseudocodigo de NEBIRE pasado a C, resulta
Código
  1. int upperTriangleDesc(const int *A, const int N)
  2. {
  3.  int i=N*N-N;
  4.  while (i && !A[i])
  5.    {
  6.      i += N + 1;
  7.      if (i > N*N)
  8. i = N*N - (N*(1 + (i%N)));
  9.    }
  10.  return !i;
  11. }
  12.  
Y algunos resultados (correctos, por supuesto)
Código:
1
1
upperTriangleDesc: 1
2
1 1
0 1
upperTriangleDesc: 1
3
1 2 3
0 1 2
0 0 1
upperTriangleDesc: 1
3
1 2 3
0 1 2
1 0 1
upperTriangleDesc: 0
Es encomiable el esfuerzo por hallar la ley que aplica al indice "i". Realmente es una función compleja...

Sin embargo... Hay un detalle no menor que puede echarse al traste....

SE HA CAMBIADO EL TIPO DE LA MATRIZ DE BIDIMENSIONAL A UNIDIMENSIONAL

Código
  1. const int **A;
  2. // Set by
  3. if  ((A=(int**)malloc(N*sizeof(int *)))==NULL)
  4.  {
  5.    perror("malloc");
  6.    exit(1);
  7.  }
  8. for(int n=0;n<N;n++)
  9.  {
  10.    if  ((A[n]=(int*)malloc(N*sizeof(int)))==NULL)
  11.      {
  12. perror("malloc");
  13. exit(1);
  14.      }
  15.  }
  16.  
por
Código
  1. const int *A;
  2.  
  3. if  ((A=(int*)malloc(N*N*sizeof(int)))==NULL)
  4.  {
  5.    perror("malloc");
  6.    exit(1);
  7.  }
  8.  

EDIT
Esto supone que se han cambiado las condiciones del problema original por otro que era equivalente, que lo emula ,pero con condiciones distintas (los datos de entrada se presuponen codificados de otro modo). As'i, con N=6, el resultado no es correcto cuando se le pasa un valor const int **A, malloc(N), ya que A[30] , esta fuera de memoria. (si lo esta const int *A, malloc(N*N)...)

Todavia no tengo la mia... tengo algnuas cosas todavía sin madurar.
« Última modificación: 20 Mayo 2020, 08:57 por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
dijsktra

Desconectado Desconectado

Mensajes: 98


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: [ALGEBRA DE MATRICES] Matriz triangular INFERIOR DESCENDIENTE en C.
« Respuesta #7 en: 19 Mayo 2020, 21:18 »

Bueno, ya va siendo hora que vaya dando una respuesta a este tema... ME VA A QUEDAR UN MENSAJE LARGO, pero a lo mejor a la posteridad le sirve de ayuda.
Recordemos que las condiciones para resolverlo eran
  • sin cambiar la codificacion de los parametros, esto es, entra const int **A, no const int *A
  • una sola variable de control, n, (aparte de los parametros, A, N)
  • Un solo bucle. No he podido, me he cansado!! (Se puede, no obstante)

Código:
i := 1
MIENTRAS i <= (N*(N-1)/2) and i != 0 ENTONCES
    i = (A[f(i)][g(i)] == 0) * (i+1)
FIN MIENTRAS
RETURN i
Como se puede apreciar falta definir las funciones f() y g() que determinen la fila y columna del siguiente elemento en función de i.Si alguien se quiere animar a intentar seguir o a exponer su razonamiento... :rolleyes: :rolleyes:

Ni mucho menos es tan simple. En https://en.wikipedia.org/wiki/Pairing_function y en http://szudzik.com/ElegantPairing.pdf se describen algunos esquemas de recorrido de una matriz, proyectando dos dimensiones en uno y viceversa. No viene la tuya, pero para otras mas sencillas quedan expresiones muy complejas que trascienden el uso basico de % y /.... Un horror, vamos porque nosotros queremos no pasar de % y /.

Yo sabia que se podía, porque un resultado clásico de computabilidad dice:

Citar
 todo lo que se puede computar con programa estilo "while" y N variables se puede hacer con 1 variable.

La contrapartida será, por supuesto,

  • la legibilidad, No tiene interes pr'actico, pero si t'eorico, pues se puede hacer lo mismo con una variable que con N, (tesis de turing-Church)
  • la eficiencia.Los programas consumen más tiempo de ejecución, aunque sin dejar de ser tratable polinomialmente (Tesis de Cook)  
Esta  es la estretegia:

Código:
En una variable se pueden codificar el estado de N variables, sin más que adoptar en esa variable el producto de los primeros N numeros primos elevados al valor de cada variable respectiva.

Eso quiere decir que para codificar

Código:
x,y = 3, 1

Damos el valor a n de.
Código:
n = (2^3)*(3^1)=8*3=24

Que por el teorema de la Aritmetica, denota univocamente unico numero o valor para n. La forma para recuperar x, (y) será el  exponente de la mayor potencia de 2, (3) que todavia haga divisible a n entre ella.

Código:
x = max { k | \exists z n=2^k*z } = 3, ya que 2^4=32 no divide a 24
y = max { k | \exists z n=3^k*z } = 1 ya que 3^2=9 no divide a 24

Pero recordemos que no podemos usar m'as que una variable, luego es ilegal llamar a funciones f(n) g(n), porque estas har'ian uso de pilas y variables, y eso es trampa... Da la casualidad de que esas funciones SI SE PUEDEN COMPUTAR SOLO CON % Y /.

Este es el codigo que quier implementar de partida.

Código
  1. int lowerTriangleDesc(const int **A, const int N)
  2. {
  3.  int i, j ;
  4.  for(i = 0, j=i+1; i < N-1 && !A[i][j]; )
  5.    if (j==N-1) { i++; j = i + 1 ;}
  6.    else j++;
  7.  return i==N-1;
  8. }

Fijemonos en como se realizan las instrucciones post decremento post incremento

Código
  1. #define DEC(id)         n/=id
  2. #define INC(id)         n*=id

Esto es asi, ya que sumar 1 a la n'esima variable equivalea multiplicar el numero por el n-esimo factor primo.

M'as dificil...
Como poder evaluar i < N - 1, cuando en nuestra unica variable solo esta almacenado n=2^i*3^j ?

La estrategia sera cargar en una variable auxiliar-virtual k,n=2^i*3^j*5^k el valor de N-1-i y ver si es mayor que cero
  •   el exponente k(5) tiene que ser  igual a N, lo  que solo se puede llevar a cabo al multiplicar tantas veces por 5 como unidades tenga N
  • Como esto solo se puede saber decrementando N una unidad hasta que queda 0...al punto que multiplicamos por 5, multiplicamos por 7 (otra variable virtual l) para no perder la referencia de N en posteriores computos (que rollo!)
  • A continuacion, restauramos N, haciendo la operacion inversa, dividiendo por 7, hasta que no se pueda mas. esto es n%7==0,  ycada vez se suma 1  a N
  • Despues restamos a k (5), 1, dividiendo por 5.
  • Despues restamos i(2) a k(5), con cuidado de guardar copia en l(7) de lo que vale i  (Otra vez Un rollo!!!)
  • Restauramos en i(2), previamente guardado en el exponente de l(7)
  • Finalmente, vemos el resultado k(5) a ver si es mayor que cero. Esto ocurre si el numero n%5==0, en otro caso, k(5) es igual a 0. Convencete con n=(2^1)*(3^3)*5(^1). Ves que el resto entre 5(k) es 0, lo que no pasa con n=(2^1)*(3^3)*5(^0), cuyo resto entre 5(k) no es 0

Código
  1. // Expressions
  2. #define NON_ZERO(id)    !(n % id)
  3. #define ZERO(id)        (n%id)

Con un poco de paciencia, se puede entender el razonamiento.

  • Como es tan tedioso y proclve a errores me he creado una especie de "compilador" con las directivas de preprocesador C.
  •  El monstruo ha quedado notablemente m'as complejo que el programa anterior, pero era lo esperado... ya que, como se puede ver, solo se usa UNA variable, n)

Código
  1.  
  2. int debug(const char *s, int n, const int i)
  3. {
  4. #ifdef DEBUG  
  5.  int c;
  6.  for( c=0; !(n%i) ; n/=i) c++;
  7.  printf("debug STATE %s : -> %d \n",s,c);
  8.  return c;
  9. #endif  
  10. }
  11.  
  12.  
  13. // N Constant
  14. #define ASSIGN_N(id1,N,id2)  for( ;N;N--) n*=id1*id2
  15. #define RESTORE_N(N,id) for( ; !(n%id);n/=id) N++
  16.  
  17. // Restoring
  18. #define RESTORE(id2,id3)    for( ; !(n%id3);n/=id3)  n*=id2
  19.  
  20. // Ordinary vars.
  21. #define DEC(id)         n/=id
  22. #define INC(id)         n*=id
  23. #define SUBS(id1,id2,id3)   for( ; !(n%id2);n/=id2) { n/=id1; n*=id3 ;}
  24. #define RESET(id)       for( ; !(n%id);n/=id)
  25. #define ASSIGN(id1,id2,id3)   for( ; !(n%id2);n/=id2) n*=id1*id3
  26. #define NEG(id)           if (n%id) n*=id; else  for( ; !(n%id);n/=id)
  27.  
  28. // Expressions
  29. #define NON_ZERO(id)    !(n % id)
  30. #define ZERO(id)        (n%id)
  31.  
  32. // Indirect pointers;
  33. #define INC_POINTER(A,id1,id2) for( ; !(n%id1); n/=id1 ) { A++; n*=id2 ; }
  34. #define INC_POINTER_POINTER(A,id1,id2) for( ; !(n%id1); n/=id1 ) { (*A)++; n*=id2;  }
  35.  
  36. #define DEC_POINTER_POINTER(A,id1,id2) for( ; !(n%id1); n/=id1 ) { (*A)--; n*=id2;  }
  37. #define DEC_POINTER(A,id1,id2)    for( ; !(n%id1); n/=id1 ) { A--; n*=id2 ; }
  38.  
  39. int lowerTriangleDesc(const int **A, int N)
  40. {
  41.  int n=1;
  42.  // i,j,k : 2,3,5    l : 7
  43.  n=3;  // i,j,k,l=0,1,0,0
  44.  ASSIGN_N(5,N,7);
  45.  RESTORE_N(N,7);
  46.  DEC(5);
  47.  SUBS(5,2,7);
  48.  RESTORE(2,7);
  49.  if (NON_ZERO(5))  // if (N-1-i>0), i.e i<N-1
  50.    {
  51.      INC_POINTER(A,2,7); // A[i]
  52.      RESTORE(2,7) ;
  53.      INC_POINTER_POINTER(A,3,7); // A[i][j]
  54.      RESTORE(3,7) ;
  55.      if (**A)
  56. RESET(5);
  57.      DEC_POINTER_POINTER(A,3,7); // A[i][j]
  58.      RESTORE(3,7) ;
  59.      DEC_POINTER(A,2,7);
  60.      RESTORE(2,7) ;
  61.    } // k = k && !A[i][j]
  62.  debug("init i",n,2); debug("init j",n,3);
  63.  debug("B: loop i < N-1 && !A[i][j]",n,5);
  64.  for(; NON_ZERO(5); )
  65.    {
  66.      RESET(5);
  67.      ASSIGN_N(5,N,7);
  68.      RESTORE_N(N,7);
  69.      DEC(5);
  70.      SUBS(5,3,7); // N-1-j > 0 , j<N-1
  71.      RESTORE(3,7);
  72.      if (ZERO(5))
  73. {
  74.  INC(2); //i++
  75.  RESET(3);
  76.  ASSIGN(3,2,5);
  77.  RESTORE(2,5);
  78.  INC(3); //j++
  79. }
  80.      else INC(3);
  81.      debug("step i",n,2); debug("step j",n,3);
  82.      ASSIGN_N(5,N,7);
  83.      RESTORE_N(N,7);
  84.      DEC(5);
  85.      SUBS(5,2,7);
  86.      RESTORE(2,7);
  87.      if (NON_ZERO(5))  // if (N-1-i>0), i.e i<N-1
  88. {
  89.  INC_POINTER(A,2,7); // A[i]
  90.  RESTORE(2,7) ;
  91.  INC_POINTER_POINTER(A,3,7); // A[i][j]
  92.  RESTORE(3,7) ;
  93.  if (**A)
  94.    RESET(5);
  95.  DEC_POINTER_POINTER(A,3,7); // A[i][j]
  96.  RESTORE(3,7) ;
  97.  DEC_POINTER(A,2,7);
  98.  RESTORE(2,7) ;
  99. } // k = k && !A[i][j]
  100.      debug("B: loop i < N-1 && !A[i][j]",n,5);
  101.    }
  102.  ASSIGN_N(5,N,7);
  103.  RESTORE_N(N,7);
  104.  DEC(5);
  105.  SUBS(5,2,7);
  106.  RESTORE(2,7);
  107.  NEG(5);
  108.  debug("epilogue: i==N-1",n,5);
  109.  return NON_ZERO(5);
  110. }
  111.  

Los mensajes debug, por supuesto, son opcionales y no forman parte del codigo. Es para poder seguir mejor la codificacion de las variables en una sola.

Ah!, las pruebas de que va bien!

El codigo de IO esta en
https://foro.elhacker.net/programacion_cc/algebra_de_matrices_matriz_triangular_superior_desdendiente_en_c-t504451.0.html;msg2220794#msg2220794

Código:
$ ./main
1
1
debug STATE init i : -> 0
debug STATE init j : -> 1
debug STATE B: loop i < N-1 && !A[i][j] : -> 0
debug STATE epilogue: i==N-1 : -> 1
lowerTriangleDesc: 1
2
1 0
1 1
debug STATE init i : -> 0
debug STATE init j : -> 1
debug STATE B: loop i < N-1 && !A[i][j] : -> 1
debug STATE step i : -> 1
debug STATE step j : -> 2
debug STATE B: loop i < N-1 && !A[i][j] : -> 0
debug STATE epilogue: i==N-1 : -> 1
lowerTriangleDesc: 1
2
1 1
1 1
debug STATE init i : -> 0
debug STATE init j : -> 1
debug STATE B: loop i < N-1 && !A[i][j] : -> 0
debug STATE epilogue: i==N-1 : -> 0
lowerTriangleDesc: 0
3
1 0 0
1 1 0
1 1 1
debug STATE init i : -> 0
debug STATE init j : -> 1
debug STATE B: loop i < N-1 && !A[i][j] : -> 2
debug STATE step i : -> 0
debug STATE step j : -> 2
debug STATE B: loop i < N-1 && !A[i][j] : -> 3
debug STATE step i : -> 1
debug STATE step j : -> 2
debug STATE B: loop i < N-1 && !A[i][j] : -> 1
debug STATE step i : -> 2
debug STATE step j : -> 3
debug STATE B: loop i < N-1 && !A[i][j] : -> 0
debug STATE epilogue: i==N-1 : -> 1
lowerTriangleDesc: 1
3
1 0 0
1 1 1
1 1 1

debug STATE init i : -> 0
debug STATE init j : -> 1
debug STATE B: loop i < N-1 && !A[i][j] : -> 2
debug STATE step i : -> 0
debug STATE step j : -> 2
debug STATE B: loop i < N-1 && !A[i][j] : -> 3
debug STATE step i : -> 1
debug STATE step j : -> 2
debug STATE B: loop i < N-1 && !A[i][j] : -> 0
debug STATE epilogue: i==N-1 : -> 0
lowerTriangleDesc: 0

P.D
Si aun no te convence que es una variable...  aplica la siguiente linea en el compilador
para observar que solo existe la varaible "n" en la rutina...
Código:
gcc -E source.c -o source.hcp

el resultado es.

Código
  1. int lowerTriangleDesc(const int **A, int N)
  2. {
  3.  int n=1;
  4.  
  5.  n=3;
  6.  for( ;N;N--) n*=5*7;
  7.  for( ; !(n%7);n/=7) N++;
  8.  n/=5;
  9.  for( ; !(n%2);n/=2) { n/=5; n*=7 ;};
  10.  for( ; !(n%7);n/=7) n*=2;
  11.  if (!(n % 5))
  12.    {
  13.      for( ; !(n%2); n/=2 ) { A++; n*=7 ; };
  14.      for( ; !(n%7);n/=7) n*=2 ;
  15.      for( ; !(n%3); n/=3 ) { (*A)++; n*=7; };
  16.      for( ; !(n%7);n/=7) n*=3 ;
  17.      if (**A)
  18. for( ; !(n%5);n/=5);
  19.      for( ; !(n%3); n/=3 ) { (*A)--; n*=7; };
  20.      for( ; !(n%7);n/=7) n*=3 ;
  21.      for( ; !(n%2); n/=2 ) { A--; n*=7 ; };
  22.      for( ; !(n%7);n/=7) n*=2 ;
  23.    }
  24.  debug("init i",n,2); debug("init j",n,3);
  25.  debug("B: loop i < N-1 && !A[i][j]",n,5);
  26.  for(; !(n % 5); )
  27.    {
  28.      for( ; !(n%5);n/=5);
  29.      for( ;N;N--) n*=5*7;
  30.      for( ; !(n%7);n/=7) N++;
  31.      n/=5;
  32.      for( ; !(n%3);n/=3) { n/=5; n*=7 ;};
  33.      for( ; !(n%7);n/=7) n*=3;
  34.      if ((n%5))
  35. {
  36.  n*=2;
  37.  for( ; !(n%3);n/=3);
  38.  for( ; !(n%2);n/=2) n*=3*5;
  39.  for( ; !(n%5);n/=5) n*=2;
  40.  n*=3;
  41. }
  42.      else n*=3;
  43.      debug("step i",n,2); debug("step j",n,3);
  44.      for( ;N;N--) n*=5*7;
  45.      for( ; !(n%7);n/=7) N++;
  46.      n/=5;
  47.      for( ; !(n%2);n/=2) { n/=5; n*=7 ;};
  48.      for( ; !(n%7);n/=7) n*=2;
  49.      if (!(n % 5))
  50. {
  51.  for( ; !(n%2); n/=2 ) { A++; n*=7 ; };
  52.  for( ; !(n%7);n/=7) n*=2 ;
  53.  for( ; !(n%3); n/=3 ) { (*A)++; n*=7; };
  54.  for( ; !(n%7);n/=7) n*=3 ;
  55.  if (**A)
  56.    for( ; !(n%5);n/=5);
  57.  for( ; !(n%3); n/=3 ) { (*A)--; n*=7; };
  58.  for( ; !(n%7);n/=7) n*=3 ;
  59.  for( ; !(n%2); n/=2 ) { A--; n*=7 ; };
  60.  for( ; !(n%7);n/=7) n*=2 ;
  61. }
  62.      debug("B: loop i < N-1 && !A[i][j]",n,5);
  63.    }
  64.  for( ;N;N--) n*=5*7;
  65.  for( ; !(n%7);n/=7) N++;
  66.  n/=5;
  67.  for( ; !(n%2);n/=2) { n/=5; n*=7 ;};
  68.  for( ; !(n%7);n/=7) n*=2;
  69.  if (n%5) n*=5; else for( ; !(n%5);n/=5);
  70.  debug("epilogue: i==N-1",n,5);
  71.  return !(n % 5);
  72. }
  73.  

SE PUEDE HACER CON UN SOLO BUCLE

DE NUEVO, EL COSTE A PAGAR SERA UN CONTROL MAS COMPLEJO,

AQUI LO DEJO.
« Última modificación: 19 Mayo 2020, 23:21 por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Matriz Triangular Superior
Programación C/C++
m@o_614 9 18,757 Último mensaje 30 Junio 2013, 19:28
por m@o_614
[Consulta] Matriz triangular inferior y superior en C++
Programación C/C++
romybe 1 5,758 Último mensaje 20 Julio 2015, 21:21
por romybe
Matriz triangulada inferior
Programación C/C++
Snarky 3 1,006 Último mensaje 10 Octubre 2017, 20:06
por ivancea96
matriz triangular superior
Programación C/C++
openclasroom 1 1,239 Último mensaje 24 Octubre 2017, 16:07
por engel lex
[ALGEBRA DE MATRICES] Matriz triangular superior desdendiente en C. « 1 2 »
Programación C/C++
dijsktra 13 766 Último mensaje 3 Mayo 2020, 20:21
por fary
Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines