Numero valido: 4130952867
Numero valido: 4130959493 

1406357289
d1d2d3 = 406 --> 406 / 2 = 203
d2d3d4 = 063 --> 063 / 3 = 21
d3d4d5 = 635 --> 635 / 5 = 127
d4d5d6 = 357 --> 357 / 7 = 51
d5d6d7 = 572 --> 572 / 11 = 52
d6d7d8 = 728 --> 728 / 13 = 56
d7d8d9 = 289 --> 289 / 17 = 17
----------
1430952867
d1d2d3 = 430 --> 430 / 2 = 215
d2d3d4 = 309 --> 309 / 3 = 103
d3d4d5 = 095 --> 095 / 5 = 19
d4d5d6 = 952 --> 952 / 7 = 136
d5d6d7 = 528 --> 528 / 11 = 48
d6d7d8 = 286 --> 286 / 13 = 22
d7d8d9 = 867 --> 867 / 17 = 51
----------
1460357289
d1d2d3 = 460 --> 460 / 2 = 230
d2d3d4 = 603 --> 603 / 3 = 201
d3d4d5 = 035 --> 035 / 5 = 7
d4d5d6 = 357 --> 357 / 7 = 51
d5d6d7 = 572 --> 572 / 11 = 52
d6d7d8 = 728 --> 728 / 13 = 56
d7d8d9 = 289 --> 289 / 17 = 17
----------
4106357289
d1d2d3 = 106 --> 106 / 2 = 53
d2d3d4 = 063 --> 063 / 3 = 21
d3d4d5 = 635 --> 635 / 5 = 127
d4d5d6 = 357 --> 357 / 7 = 51
d5d6d7 = 572 --> 572 / 11 = 52
d6d7d8 = 728 --> 728 / 13 = 56
d7d8d9 = 289 --> 289 / 17 = 17
----------
4130952867
d1d2d3 = 130 --> 130 / 2 = 65
d2d3d4 = 309 --> 309 / 3 = 103
d3d4d5 = 095 --> 095 / 5 = 19
d4d5d6 = 952 --> 952 / 7 = 136
d5d6d7 = 528 --> 528 / 11 = 48
d6d7d8 = 286 --> 286 / 13 = 22
d7d8d9 = 867 --> 867 / 17 = 51
----------
4160357289
d1d2d3 = 160 --> 160 / 2 = 80
d2d3d4 = 603 --> 603 / 3 = 201
d3d4d5 = 035 --> 035 / 5 = 7
d4d5d6 = 357 --> 357 / 7 = 51
d5d6d7 = 572 --> 572 / 11 = 52
d6d7d8 = 728 --> 728 / 13 = 56
d7d8d9 = 289 --> 289 / 17 = 17
----------

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
#define MAX 10
const int N = MAX ;   // i.e O(1)
static  int d[MAX];
static const  int primes[MAX-3]={2,3,5,7,11,13,17}; // N primes is very hard to compute.
 
 
 
void print_solution(const int d[])
{
  for(int n=0;n<10;n++) printf("%d",d[n]);
  printf("\n");
  for(int n=1;n<8;n++)
    {
      char s[4];
      sprintf(s,"%d%d%d",d[n],d[n+1],d[n+2]);
      int num=atoi(s);
      printf("d%dd%dd%d = %03d --> %03d / %d = %d\n",n,n+1,n+2,num,num,primes[n-1],num/primes[n-1]);
    }
  printf("----------\n");
  return;
}
 
/* O(1) Specialzer.*/
void primeG(const int k, const int part,const int N)
{
  static int free[MAX]={1,1,1,1,1,1,1,1,1,1};
 
  //  printf("%d\n",k);
  if (k==N)
    {
      print_solution(d);
      return;
    }
  else
    for(int c=0; c<10; c++)
    {
      if (!free[d[k]=c]) continue;
#define DDD (10*part + c)
      if ((k>2) && (DDD%primes[k-3])) continue; 
      free[c]=0;
      primeG(k+1,DDD%100,MAX);
      free[c]=1;
    }
  return;
}
 
 
 
 
 
int main(int argc, char *args)
{
  // Call Specializer.
  primeG(0,0,MAX);
  return 0;
}
 

#include <stdio.h>
#include <stdlib.h>
 
 
int main(int argc, char *args)
{
  int n,acum,many;
  many=acum=0;
  while (scanf("%d",&n)==1)
    {
      acum +=n;
      many++;
    }
  if (ferror(stdin))
    {
      perror("scanf");
      exit(1);
    }
  printf("\n%d %d\n",many,acum);
  return 0;
}
 

 gcc stream.c -o main && ./main
10 20 30 40 50 n

5 150

• 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...

• 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)  

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.

x,y = 3, 1

n = (2^3)*(3^1)=8*3=24

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

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

#define DEC(id)         n/=id 
#define INC(id)         n*=id

•   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

// Expressions
#define NON_ZERO(id)    !(n % id)
#define ZERO(id)        (n%id)

• 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)
  

 
int debug(const char *s, int n, const int i)
{
#ifdef DEBUG  
  int c;
  for( c=0; !(n%i) ; n/=i) c++;
  printf("debug STATE %s : -> %d \n",s,c);
  return c;
#endif  
}
 
 
// N Constant
#define ASSIGN_N(id1,N,id2)  for( ;N;N--) n*=id1*id2 
#define RESTORE_N(N,id) for( ; !(n%id);n/=id) N++ 
 
// Restoring
#define RESTORE(id2,id3)    for( ; !(n%id3);n/=id3)  n*=id2 
 
// Ordinary vars.
#define DEC(id)         n/=id 
#define INC(id)         n*=id
#define SUBS(id1,id2,id3)   for( ; !(n%id2);n/=id2) { n/=id1; n*=id3 ;} 
#define RESET(id)      	for( ; !(n%id);n/=id)
#define ASSIGN(id1,id2,id3)   for( ; !(n%id2);n/=id2) n*=id1*id3 
#define NEG(id)           if (n%id) n*=id; else  for( ; !(n%id);n/=id)
 
// Expressions
#define NON_ZERO(id)    !(n % id)
#define ZERO(id)        (n%id)
 
// Indirect pointers;
#define INC_POINTER(A,id1,id2) for( ; !(n%id1); n/=id1 ) { A++; n*=id2 ; } 
#define INC_POINTER_POINTER(A,id1,id2) for( ; !(n%id1); n/=id1 ) { (*A)++; n*=id2;  }
 
#define DEC_POINTER_POINTER(A,id1,id2) for( ; !(n%id1); n/=id1 ) { (*A)--; n*=id2;  }
#define DEC_POINTER(A,id1,id2)    for( ; !(n%id1); n/=id1 ) { A--; n*=id2 ; } 
 
int lowerTriangleDesc(const int **A, int N)
{
  int n=1;
  // i,j,k : 2,3,5    l : 7
  n=3;  // i,j,k,l=0,1,0,0
  ASSIGN_N(5,N,7);
  RESTORE_N(N,7);
  DEC(5);
  SUBS(5,2,7);
  RESTORE(2,7);
  if (NON_ZERO(5))  // if (N-1-i>0), i.e i<N-1
    {
      INC_POINTER(A,2,7); // A[i]
      RESTORE(2,7) ; 
      INC_POINTER_POINTER(A,3,7); // A[i][j]
      RESTORE(3,7) ; 
      if (**A)
	RESET(5);
      DEC_POINTER_POINTER(A,3,7); // A[i][j]
      RESTORE(3,7) ;
      DEC_POINTER(A,2,7);
      RESTORE(2,7) ; 
    } // k = k && !A[i][j]
  debug("init i",n,2); debug("init j",n,3);
  debug("B: loop i < N-1 && !A[i][j]",n,5);
  for(; NON_ZERO(5); )
    {
      RESET(5);
      ASSIGN_N(5,N,7);
      RESTORE_N(N,7);
      DEC(5);
      SUBS(5,3,7); // N-1-j > 0 , j<N-1
      RESTORE(3,7);
      if (ZERO(5))
	{
	  INC(2); //i++
	  RESET(3);
	  ASSIGN(3,2,5);
	  RESTORE(2,5);
	  INC(3); //j++
	}
      else INC(3);
      debug("step i",n,2); debug("step j",n,3);
      ASSIGN_N(5,N,7);
      RESTORE_N(N,7);
      DEC(5);
      SUBS(5,2,7);
      RESTORE(2,7);
      if (NON_ZERO(5))  // if (N-1-i>0), i.e i<N-1
	{
	  INC_POINTER(A,2,7); // A[i]
	  RESTORE(2,7) ; 
	  INC_POINTER_POINTER(A,3,7); // A[i][j]
	  RESTORE(3,7) ; 
	  if (**A)
	    RESET(5);
	  DEC_POINTER_POINTER(A,3,7); // A[i][j]
	  RESTORE(3,7) ;
	  DEC_POINTER(A,2,7);
	  RESTORE(2,7) ; 
	} // k = k && !A[i][j]
      debug("B: loop i < N-1 && !A[i][j]",n,5);
    }
  ASSIGN_N(5,N,7);
  RESTORE_N(N,7);
  DEC(5);
  SUBS(5,2,7);
  RESTORE(2,7);
  NEG(5);
  debug("epilogue: i==N-1",n,5);
  return NON_ZERO(5);
}
 

$ ./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

gcc -E source.c -o source.hcp

int lowerTriangleDesc(const int **A, int N)
{
  int n=1;
 
  n=3;
  for( ;N;N--) n*=5*7;
  for( ; !(n%7);n/=7) N++;
  n/=5;
  for( ; !(n%2);n/=2) { n/=5; n*=7 ;};
  for( ; !(n%7);n/=7) n*=2;
  if (!(n % 5))
    {
      for( ; !(n%2); n/=2 ) { A++; n*=7 ; };
      for( ; !(n%7);n/=7) n*=2 ;
      for( ; !(n%3); n/=3 ) { (*A)++; n*=7; };
      for( ; !(n%7);n/=7) n*=3 ;
      if (**A)
	for( ; !(n%5);n/=5);
      for( ; !(n%3); n/=3 ) { (*A)--; n*=7; };
      for( ; !(n%7);n/=7) n*=3 ;
      for( ; !(n%2); n/=2 ) { A--; n*=7 ; };
      for( ; !(n%7);n/=7) n*=2 ;
    }
  debug("init i",n,2); debug("init j",n,3);
  debug("B: loop i < N-1 && !A[i][j]",n,5);
  for(; !(n % 5); )
    {
      for( ; !(n%5);n/=5);
      for( ;N;N--) n*=5*7;
      for( ; !(n%7);n/=7) N++;
      n/=5;
      for( ; !(n%3);n/=3) { n/=5; n*=7 ;};
      for( ; !(n%7);n/=7) n*=3;
      if ((n%5))
	{
	  n*=2;
	  for( ; !(n%3);n/=3);
	  for( ; !(n%2);n/=2) n*=3*5;
	  for( ; !(n%5);n/=5) n*=2;
	  n*=3;
	}
      else n*=3;
      debug("step i",n,2); debug("step j",n,3);
      for( ;N;N--) n*=5*7;
      for( ; !(n%7);n/=7) N++;
      n/=5;
      for( ; !(n%2);n/=2) { n/=5; n*=7 ;};
      for( ; !(n%7);n/=7) n*=2;
      if (!(n % 5))
	{
	  for( ; !(n%2); n/=2 ) { A++; n*=7 ; };
	  for( ; !(n%7);n/=7) n*=2 ;
	  for( ; !(n%3); n/=3 ) { (*A)++; n*=7; };
	  for( ; !(n%7);n/=7) n*=3 ;
	  if (**A)
	    for( ; !(n%5);n/=5);
	  for( ; !(n%3); n/=3 ) { (*A)--; n*=7; };
	  for( ; !(n%7);n/=7) n*=3 ;
	  for( ; !(n%2); n/=2 ) { A--; n*=7 ; };
	  for( ; !(n%7);n/=7) n*=2 ;
	}
      debug("B: loop i < N-1 && !A[i][j]",n,5);
    }
  for( ;N;N--) n*=5*7;
  for( ; !(n%7);n/=7) N++;
  n/=5;
  for( ; !(n%2);n/=2) { n/=5; n*=7 ;};
  for( ; !(n%7);n/=7) n*=2;
  if (n%5) n*=5; else for( ; !(n%5);n/=5);
  debug("epilogue: i==N-1",n,5);
  return !(n % 5);
}
 

• 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

int upperTriangleDesc(const int *A, const int N)
{
  int i=N*N-N;
  while (i && !A[i])
    {
      i += N + 1;
      if (i > N*N)
	i = N*N - (N*(1 + (i%N)));
    }
  return !i;
}
 

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

const int **A;
// Set by
if  ((A=(int**)malloc(N*sizeof(int *)))==NULL)
  {
    perror("malloc");
    exit(1);
  }
for(int n=0;n<N;n++)
  {
    if  ((A[n]=(int*)malloc(N*sizeof(int)))==NULL)
      {
	perror("malloc");
	exit(1);
      }
  }
 

const int *A;
 
if  ((A=(int*)malloc(N*N*sizeof(int)))==NULL)
  {
    perror("malloc");
    exit(1);
  }
 

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

int lowerTriangleDescBis(const int **A, 
			 const int N)
{
  int i,j;
  for (i=N-1,j=N; i && (j==N); i-=(j==N))
    for(j=i; j<N && !A[i-1][j];j++);
  return !i;
}

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

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...

dijsktra deberías de poner mas retos como este  

int lowerTriangleDesc(const int **A, 
		      const int N)
{
  // Start code here.
  return 1;
}

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

Estamos ansiosos de ver tu código dijsktra   ¿Para qué retrasarlo más?  

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
 

Cuando tienes proyectos sin terminar pero @dijsktra te pica a darle más vueltas a un algoritmo aparentemente sencillo.  

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

...

Código

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

A ver qué tal esta vez.  

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]