Mensajes

[dijsktra]

dijsktra deberías de poner mas retos como este  

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 (c) [Seleccionar] Expandir

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

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 [Seleccionar] Expandir


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


[dijsktra]

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

Allá va... Se aceptan criticas...

Con el buen trabajo que hicisteis al principio, había poco margen... De hecho, la tuya es muy dificil de superar, pero no es estructurada... tiene "saltos"... Y el heroe del cual tomo el pseudonimo, dijsktra, maldecia la programación "con saltos"... Esto podia hacer el software muy complejo de mantener, por lo menos en algoritmia, no en programacion de sistemas.

Lo que no todo el mundo sabe es que, sin cuidado, - sin la técnica de derivación- y sin un buen lenguaje -C no es el mejor para la algoritmia, porque le faltan asignaciones multiples y comandos guardados...- la programacion estructurada puede ser tan dificil de mantener ( o mas) que la no estructurada. Aunque en general, siguiendo las directrices de dijsktra (el original, no yo)  es m'as fácil.


La formalizacion que permite demostrarlo rigorusamente esta descrita en comnetarios, pero eso es para cursos avanzados.. Lo dejo para la posteridad que lo quiera conusltar en Internet...

Propongo dos versiones.. Va la primera...

Código (c) [Seleccionar] Expandir


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


Grosso modo, la idea es la siguiente...
Al principio, al final y entre vueltas del bucle externo, si j<i-1 entonces sabemos que hemos encontradoun elemento A[i-1][j] distingo de 0, en la zona prohibida... Es un invariante... Y acabamos si hemos llegado a i==N en el caso peor... luego en las anteriores a N, no lo encontrarmos... Aun en i==N podria ser, por loq eu evaluamos j==i-1 en el return... Es como una piedra en el calzado esa utlima linea...es lo que le perdio a
YreX-DwX .  Aun asi, se puede apreciar como los indices i,j se modifican naturalmente, con i++,j++

La segunda, mi favorita...

Código (c) [Seleccionar] Expandir


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

En esta version, tenemos la fortuna de parar en la primera linea en la que hayamos encontrado el elemento no valido, que resultara estar en A(i)[j-1] si j>0 (Es un invariante)...
O en N, si no lo encontramos...Pero el cambio no es gratuiro.. el avance de i es condicional, i.e. i+=!j

Saludos...Cuidaos del COVID...!

[Prueba a evaluar la matriz de 1 fila y 1 columna...]

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

Grandeeee....

...

Código (c) [Seleccionar] Expandir


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

Chavalote! Este no te lo puedo bendecir... Tiene un sutil fallo. Te digo cual?
Prueba a evaluar la matriz de 1 fila y 1 columna...
El resultado es indeterminado... porque entonces accedes a una posicion tal como A[0][-1]  . Si acierta, dependera del compilador, o de la conjunci'on de los astros...
Que pasa? que las matrices de 1 fila y 1 columna no son matrices???  Prueba [[1]]!  

Podemos ver que esto se complica mucho y solo para quitar una variable local. Así que tenía que haber otra solución.

Ese es el punto... Que tenemos que hacerlo sencillo. Pero claro, con lo bien que lo hiciste al principio, cacda vez queda menos margen...

...

Código (c) [Seleccionar] Expandir


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.  

 Bravo... Correcta... pero aun redundante... ya que en

Código (c) [Seleccionar] Expandir


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

es equivalente a

Código (c) [Seleccionar] Expandir


j=(j<i)

En ese punto. N>i>0 siempre. ya que 1<=i<=N (desde el principio 1==1, y siempre aumenta... y por meterse en el primer bucle i<N.
(Si has llegado a j==i, es porque todos los anteriores son 0, en particular, A[j-1]. luego es "por el momento triangular", lo que tu registras poniendo j=0.Si no llegas, a j==i es porque A[j] es distinto de 0, y tu la marcas a 1, "diciendo que no es triangular". Por evaluacion en cortocircuito, no se evalua A[j-1]...

Y como tu dices, se ha hecho mas "compleja de leer" ya que...j

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

Pongo ya mi solucion en el mensaje abajo, para no repetir, en respuesta a fary

Hmmm.... Correcta!  

Una objección:

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

Se puede conseguir una solucion estructurada y con solo 2 variables locales?

...
Por lo tanto la solución más sencilla parece un par de bucles que recorran esta parte de la matriz.
.....

Código (c) [Seleccionar] Expandir


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;
}
....
Como echo de menos estas cosas de C/C++ desde que trabajo con Java
...

Desde luego... Con los Objetos de Java (o de C++) no se puede hacer fácilmete algebra...

[a<i]

Hmmmm... Correcta!

Dos objecciones que lo pueden hacer mejor...

•  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

¿Igual algo así?

Código (c) [Seleccionar] Expandir


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
}

[matriz triangular superior decendiente]

Se pide, dada na matriz de tamaño NxN, N arbitrario, determinar si es una matriz triangular superior decendiente. Esto es, los elementos debajo de la diagonal principal descendiente son todos nulos (no necesariaemente el resto).

Por ejemplo, son triangulares superiores descendientes:

Código [Seleccionar] Expandir


1 2 3    1 2 3    
0 4 5    0 4 5
0 0 2    0 0 0


Y no lo son

Código [Seleccionar] Expandir


1 2 3    1 2 3    
0 4 5    2 4 5
0 2 2    0 0 0

Se facilita el codigo de entrada/salida y unos casos de uso. La primera linea marca la dimension de la matriz cuadrada, N. Las siguientes N lineas dan las filas de la matriz.

ES UN RETO. YO YA TENGO LA SOLUCION. EN UNOS DIAS LA PONGO...
(Se valora la solucion mas imple)

Código [Seleccionar] Expandir


5
1 2 3 0 0
0 4 5 0 0
0 0 0 1 1
0 0 0 3 1
0 0 0 0 1
upperTriangleDesc: 1
3
1 2 3
0 4 5
0 2 0
upperTriangleDesc: 0
3
1 2 3
0 4 5
0 0 0
upperTriangleDesc: 1

Código (c) [Seleccionar] Expandir


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

[push_front, pop_front]

Brevemente, amigo.
Las estructuras de datos, en tu caso una lista simplemente enlazda, solo exiten para emular algun tipo asbtracto de datos (pilas, colas, dobles colas ... e incluso listas como tipo abstracto, no como estructura de datos en si).


EDIT: No se hacer en C++. Te proporcion en C


Para tu caso he elegio la emulación parcial de una doble cola. Faltan unas operaciones, como push_front, pop_front , que por espacio omito. practica tu.

TE podra serviar para lo que quieres.


La operacion por la que estas interesado es

Código (c) [Seleccionar] Expandir


typedef struct _node
{
 int info;
 struct _node *next;
} *node;

typedef struct _deque
{
 node first;
 node last;
}deque;


void pop_back(deque *dq)
{
 assert(dq->last != NULL);
 node prev,act;
 for(prev=NULL,act=dq->first;act!=dq->last;act=act->next)
   prev=act;
 dq->last = prev;
 if (prev) prev->next=NULL;
 else dq->first=dq->last=NULL;
 free(act);
}



Y aqui una exhibicion del programa ejecutable

Código (c) [Seleccionar] Expandir



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

typedef struct _node
{
 int info;
 struct _node *next;
} *node;

typedef struct _deque
{
 node first;
 node last;
}deque;


int print(const deque *dq){
 printf("[ ");
 node p;
 for(p=dq->first;p!=NULL ; p=p->next)
   printf("%d ",p->info);
 printf(" ]");
 printf("\n");
 return 0;
}

void create(deque *dq)
{
 dq->first = dq->last = NULL ;
 return;
}

void push_back(deque *dq,int info)
{
 node n;
 if ((n = (node)malloc(sizeof(struct _node)))==NULL)
   {
     perror("malloc");
     exit(-1);
   }
 n->info = info;
 n->next = NULL;
 node prev;
 
 if (dq->last) dq->last->next = n ;
 dq->last= n;
 if (!dq->first) dq->first=dq->last;
 return;
}



int top(const deque *dq)
{
 assert(dq->last != NULL);
 return dq->last->info;
}

void pop_back(deque *dq)
{
 assert(dq->last != NULL);
 node prev,act;
 for(prev=NULL,act=dq->first;act!=dq->last;act=act->next)
   prev=act;
 dq->last = prev;
 if (prev) prev->next=NULL;
 else dq->first=dq->last=NULL;
 free(act);
}


int empty(const deque *dq)
{
 return dq->first == NULL;
}

void destroy(deque *dq)
{
 node p,aux;
 for(p=dq->first ;p;p=aux)
   {
     aux=p->next;
     free(p);
   }
 return ;
}

int main(int argc, char *args[] )
{
 int N=10;
 deque dq;
 create(&dq);
 for(int n=0;n<N;n++)
   push_back(&dq,n);
 for( ; !empty(&dq); pop_back(&dq)) print(&dq);
 print(&dq);
 destroy(&dq);
 return 0;

}



Y una preuba de ejecucion

Código [Seleccionar] Expandir


[ 0 1 2 3 4 5 6 7 8 9  ]
[ 0 1 2 3 4 5 6 7 8  ]
[ 0 1 2 3 4 5 6 7  ]
[ 0 1 2 3 4 5 6  ]
[ 0 1 2 3 4 5  ]
[ 0 1 2 3 4  ]
[ 0 1 2 3  ]
[ 0 1 2  ]
[ 0 1  ]
[ 0  ]
[  ]


Gracias, esa página ya la vi antes de consultar, y no encontré la respuesta. Necesito tomar los datos de la entrada estándar.

Hola.
Tengo experiencia en C pero me gustaría aprender el criptico command.com

Hay algunos tutoriales en la sección de mensajes fijos, pero no encuentro la respuesta.

Se que

Código [Seleccionar] Expandir

set /P VAR=

Lee un escalar. Pero no consigo leer un array por entrada estandar.

algo como

Código [Seleccionar] Expandir

for %%i in (0,1,10) do (
  set /P A[%%i]=
)

Que desde luego, no funciona. si alguien puede decirme...

[YreX-DwX]

Es un problema muy bonito.  

En pseudocódigo tu solución quedaría así:

Código [Seleccionar] Expandir


INICIO
   PEDIR numero
   digitos[LONGITUD_MAXIMA] // array de longitud igual al maximo numero de digitos que puede tener el numero
   numeroDigitos := calcularDigitos(numero, digitos)
...
FIN

La solución por YreX-DwX parece correcta, pero un poco ineficaz, ya qu está en complejidad O(log^2(N)). A grandes rasgos, esto quiere decir que para un número de 10 cifras, hace 10*10 veces la operación más intern, para uno de 1000, hace 1000*1000 veces...


Yo propongo una solucion en O(log(N)), es decir , para un numero de 10 cifras, hace 10*10 veces la operación  . Para uno de 1000, hace 1000*10 veces la operación interna...., Para uno de 4000 cifras, hace 4000*10 veces la operación interna...  Y en espacio es O(10)=O(1), y que solo hay 10 digtos posibles...

Código (cpp) [Seleccionar] Expandir


/*

 Title: Narcisist number (in  base 10)

 P : N == \sum i : 0 <= i <= log(N): a_i*10^i
 Q : N==\sum i : 0 <= i <= log(N): a_i^{log(N)+1}


3     2     1     0
+-----+-----+-----+
|  1  |  5  |   3 |  YES, since 153=1^3+5^3+3^3
+-----+-----+-----+



I ::= 0<=n<=log(N)+1 and Q[log(N)/n-1] and
     M=N/10^n and
     (n<=log(N) ->
     (\forall i : 0 <= i < 10 : pow[i]=i^n and frec[i]=FREC(i,N%10^n)))

!B ::= n==log (N)+1

B ::= n<log (N)+1  ; // i.e. M>0

Init:
-----
 n,pow[0..9],frec[0..9]=0,
 
 |- P -> I [n/0,M/N,pow[0..9]=[1]^10, frec[0..9]=[0]^10]


QUOTE(N,n) = log (N)+1 - n >= 0   (Cuota decreases)

Step:
-----

n = n + 1 ; // i.e. M = M/10 ;

*/

#include <iostream>
#include <cassert>

using namespace std;

int narcisist(const unsigned long long N)
{
 unsigned long long pow[10]={1,1,1,1,1,1,1,1,1,1} ; // [0-9]^0
 unsigned long long frec[10]={0,0,0,0,0,0,0,0,0,0} ;
 unsigned long long sum,M;
 assert(N);
 for (M=N ; M ;M/=10 )  // O(log(N)
   {
     frec[M%10]+=1;
     int d;
     for (sum=d=0 ; d<10 ;d++ )  // O(1)
{
 pow[d]*=d;
 sum+=pow[d]*frec[d];
}
   }
 //  cout <<"trace " << N << " " << sum << endl;
   
 return sum==N;

}

int main (int argc, char *args[])
{
 unsigned long long N;
 for( ; cin >> N ; )
   cout << narcisist(N) << endl;
 return 0;
}


Solo me se 153 y 1634 como numero narcisistas en base 10... SI alguien sabe otros, puede comprobar...

Código [Seleccionar] Expandir

g++ narcisista.cc -o main && ./main
1634
1
153
1
154
0