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

 

 


Tema destacado: Los 10 CVE más críticos (peligrosos) de 2020


  Mostrar Mensajes
Páginas: 1 2 3 4 5 6 7 8 [9] 10 11
81  Programación / Programación C/C++ / Re: "carcateres adyacentes por parejas" en: 12 Junio 2018, 10:46 am
A ver, gusanillo, este problema ya lo preguntaste aquí ( y creo que resuelto)

https://foro.elhacker.net/programacion_cc/buenos_diastengo_muchas_dudas_con_un_ejercicio_de_caracteres-t480917.0.html;msg2155561#msg2155561

Si ponemos "caracteres adyacentes por parejas" o algo similar en el tema, podremos localizarlo mejor
82  Programación / Programación C/C++ / Re: Invertir cadena de carácteres sobre si misma con punteros en: 1 Mayo 2018, 18:14 pm
hola!

Yo preferiría hacerlo sin invertir las cadenas, porque es más fácil, pero si hay que hacerlo invirtiendo....


1 version. Sin incluir espacios, sólo palabras


Código
  1. #include <string> // string
  2. #include <iostream>  // cin, cout
  3. #include <cstdlib> //  malloc
  4.  
  5. using namespace std;
  6.  
  7. int palindrome(const char* W)
  8. {
  9.  char *jj;
  10.  const char *i, *j;
  11.  for(i=W  ; *i  ;i++) ;  // compute len=(i-W)
  12.  if (!(j=jj=(char *)calloc(sizeof(char),(i-W)+1)))
  13.    {
  14.      perror("calloc");
  15.      exit(-1);
  16.    }
  17.  for(  ; i > W  ;i--,jj++) *jj=*(i-1); // reverse copy
  18.  for(   ; *i && (*i == *j);i++,j++ ); //compare
  19.  return !*i ; //  true if end reached.
  20. }
  21.  
  22. int main(int argc, char **args)
  23. {
  24.  string phrase;
  25.  for (; getline(cin,phrase); )
  26.    cout << palindrome(phrase.c_str()) << endl;
  27.  return 0;
  28. }


Aquí algunos ejemplos de ejecución. 1 expresa que es palíndromo, 0 que no lo es.

Código:
1234
0
1111
1
1221
1
12344321
1
2
1
331133
1
33113
0
    (intro, palabra vacía, que es palindromo)
1

2 versión. Frases que pueden incluir varias palabras separadas por espacios, blancos, tabuladores...
(Nota: Los separadores están "normalizados" por la funcion isspace(int c))


Código
  1. #include <string> // string
  2. #include <iostream>  // cin, cout
  3. #include <cstdlib> //  malloc
  4.  
  5. #include <cctype> // isspace
  6. #define sp(c) isspace((c)) // shortcut    
  7.  
  8. using namespace std;
  9.  
  10. int palindrome(const char* W)
  11. {
  12.  const char *i, *j;
  13.  char *jj;
  14.  
  15.  for(i=W  ; *i  ;i++) ;
  16.  if (!(j=jj=(char *)calloc(sizeof(char),(i-W)+1))) // len=(i-W)
  17.    {
  18.      perror("calloc");
  19.      exit(-1);
  20.    }
  21.  for(  ; i > W  ;i--,jj++) *jj=*(i-1); // reverse copy
  22.  const char *b; // key!
  23.  for ( ; *i && (sp(*i)||sp(*j) || (*i==*j)); i+=(*i==*j)||sp(*i), j+=(*b==*j)||sp(*j)) b=i;
  24.  return !*i ; //  true if end reached.
  25. }
  26.  
  27.  
  28. int main(int argc, char **args)
  29. {
  30.  string phrase;
  31.  for (; getline(cin,phrase); )
  32.    cout << palindrome(phrase.c_str()) << endl;
  33.  return 0;
  34. }

Algunso casos de prueba

Código:
dabale arroz a la zorra el              abad
1
dabale arroz a la zorra el abad
1
dabale arroz al zorro el  abad
0
               (30 espacios en blanco e intro)
1

Lo que pasa es que no me da tiempo a explicarlo. Si, se que mi escritura del for puede desconcertar a algunos, pero se trata de un doble avance...de los punteros... Dos comentarios más :
  • con python no haria falta la variable "b" porque puede simular la asignacion simultanea.
  • se puede prescindir una de las variables, "j" o "jj" (la que quede debe se (char *)), a cambio de un bucle similar al primero para rescatar de nuevo la longitud de la cadena, antes de el último for de comparación 

Que te sirva! Y perdón por los acentos que faltan!
83  Programación / Programación C/C++ / Re: error id returned 1 exit status [_getchr()] en: 30 Abril 2018, 13:46 pm
Esto es por conio.h que es una librería de Borland y estás usando otro compilador que no la tiene.

Empiezo por la solución. Prueba a poner, como solución local:

Código
  1. ...
  2. #include<conio.h>
  3. #define getchr  _getchr
  4.  
  5. using namespace std;
  6.  
  7. int main(){
  8. ....
  9.  

a ver qué pasa...(no he podido probar porque tengo Linux...)

Como dice MAFUS, pertenecían a Borland, pero Microsoft las mantiene en su SDK, para garantizar compatibilidad con el legacy software

https://docs.microsoft.com/en-us/cpp/c-runtime-library/console-and-port-i-o

Pero, bien claro lo advierte...

This API cannot be used in applications that execute in the Windows Runtime. For more information, see CRT functions not supported in Universal Windows Platform apps.


Es  una pena que para un programa que no pretende hacer una aplicación, sino un sencillo algoritmo con entrada-salida por consola se pierda compatibilidad con el restro de plataformas linux, mac, freebsd...

Las recomendaciones al respecto, son...
  • No uses ni "_getchr()", ni system("PAUSE"). Esta última, aunque te funcione, lo que hace es abrir todo un proceso costoso que NADA tiene que ver con tu algoritmo.... Tendría sentido en programación Batch* de windows.
    Ejecuta el programa desde una consola abierta expresamente para eso, no lanzándolos desde el IDE... busca dónde se guarda el ".exe" y des la consola lo ejecutas. Así todos los símbolos se quedan para que los puedas ver
  • Si aún quieres lanzarlos desde el IDE, (Visual C++, Dev-Cpp....) prueba a poner un sencillo "cin >> ch" , con "ch" de tipo "char"... que espera latente a leer un caracter (más el enter). As'i al menos, lo podran ejecutar otras plataformas no windows. Pero ojo, estas marcando un "protocolo"  de entrada totalmente inútil... Mejor ejecuta desde consola!

*... Hace poco en estos foros pude ver a uno de los mejores programadores de Batch "del mundo"... creo que era de Méjico.... Increible lo que podia hacer con el command.com. (Sabe algo alguien de él?)
84  Programación / Programación C/C++ / Re: Ayuda con sintaxis For en: 27 Abril 2018, 22:58 pm
Okok muchas gracias a ambos, y si quisiera que se inicializara desde el valor de la variable "n" dada por el usuario,y termine hasta que sea igual a 3?

Un poco más raro... pero igual de bonito.

La expresión

Código
  1. c=(N%3==0)*N

se evalúa de la siguiente manera: Si N es divisible entre 3, entonces (N%3==0) es 1, y entonces c, vale  1*N . En otro caso, pues 0.

Código
  1. #include <stdio.h>
  2. #include <assert.h>
  3.  
  4.  
  5. /*
  6.   P : M >= 3
  7.   Q : c = sum i : 3 <= i <= M and (i%3==0) : i
  8.      
  9.   I : Q[M/n] and 3 <= n <= M
  10.   B : n > 3
  11.      
  12.   Quota (n) = n - 3 >= 0
  13.   Step : n = n - 1
  14.   Restore : c = c + (n-1)*\chi((n-1)%3==0)
  15.      
  16. */
  17.  
  18. #define DEBUG
  19.  
  20. unsigned int mult3(const unsigned int N)
  21. {
  22.  assert(N>=3);
  23.  unsigned int n,c;
  24.  for(n=N,c=(N%3==0)*N;n>3;n--)
  25.    {
  26. #ifdef DEBUG
  27.      if (n%3==0) printf("%d ",n);
  28. #endif
  29.      if (((n-1)%3==0)) c+=(n-1);
  30.    }
  31. #ifdef DEBUG
  32.      printf("%d ",3);
  33. #endif
  34.  return c;
  35. }
  36.  
  37.  
  38.  
  39. int main()
  40. {
  41.  unsigned int M;
  42.  int e;
  43.  for ( ; (e=scanf("%u",&M))==1;)
  44.    printf(" --> %u\n",mult3(M));
  45.  if (e!=EOF)
  46.    {
  47.      printf("Not a integer");
  48.      return -1;
  49.    }
  50.  return 0;
  51. }

La salida del programa da
Código:
3
3  --> 3
4
3  --> 3
5
3  --> 3
6
6 3  --> 9
7
6 3  --> 9
8
6 3  --> 9
9
9 6 3  --> 18
10
9 6 3  --> 18
85  Programación / Programación C/C++ / Re: Ayuda con sintaxis For en: 27 Abril 2018, 14:57 pm
Hola!

... que haya contenidos en un número dado por el usuario.
Si digito un 9 la suma de sus múltiplos debería dar 3+6+9=18

Yo diría mejor

 contenidos en un rango empezando desde 3 hasta un número (mayor o igual que 3) dado por el usuario.


La sintaxis de la instrucción de control "for", a no dudarlo, una de las señales más características del lenguaje C, sobretodo porque es tan versátil que su expresividad es equivalente a la de la instrucción "while"...
Esto no era así en otros lenguajes de su época, como el mítico Pascal, en el que se usaba como azucar sintáctico de una construcción while particular (donde había una variable  contadora "n", que se comparaba contra una expresión "n=e(...)" y se incrementaba o disminuía  en un valor constante 1,2...)

Tiene 4 partes
Código
  1. for (init; B ; step) body
que vienen a coincidir con lo que en algoritmia clásica se conoce como

  • init : donde se dan valores a las variables al principio
  • B : guarda que determina cuándo termina su ejecución. (Después del init y del step en segundas vueltas)
  • step : incremento de variable, para que el bucle progrese hacia su terminación (después del body)
  • body: aproxima el cómputo parcial a la solución definitivadespues de evaluar la guarda y antes de step

En el cuerpo del bucle pueden aparecer instrucciones como break; o continue, y aunque muy útiles en programación se sistemas y en el mundo real, en algoritmia clásica son el "patito feo" que rompe la llamada "programación estructurada" o "composicional"... Pero esto es otro tema aparte..... C no fue hecho para estudiar algoritmia, sino para la programación de sistemas operativos, y es ahí donde encuentran todo su valor...


Ahi va una solución a tu problema.
Los comentarios tienen más importancia en cursos avanzados de algoritmia. Por el momento fífate en la rutina mult3. Después intenta programarla en sentido descendente (con nn--...)


Código
  1. #include <stdio.h>
  2. #include <assert.h>
  3.  
  4.  
  5. /*
  6.   P : M >= 3
  7.   Q : c = sum i : 3 <= i <= M and (i%3==0) : i
  8.  
  9.   I : Q[M/n] and 3 <= n <= M
  10.   B : n < M
  11.  
  12.   Quota (n) = M - n >= 0
  13.   Step : n = n + 1
  14.   Restore : c = c + (n+1)*\chi((n+1)%3==0)
  15.  
  16. */
  17.  
  18. #define DEBUG
  19.  
  20. unsigned int mult3(const unsigned int N)
  21. {
  22.  assert(N>=3);
  23.  unsigned int n,c;
  24. #ifdef DEBUG
  25.      printf("%d ",3);
  26. #endif
  27.  for(n=c=3;n<N;n++)
  28.    {
  29.      if (((n+1)%3==0)) c+=(n+1);
  30. #ifdef DEBUG
  31.      if ((n+1)%3==0) printf("%d ",n+1);
  32. #endif
  33.    }
  34.  return c;
  35. }
  36.  
  37.  
  38.  
  39. int main()
  40. {
  41.  unsigned int M;
  42.  int e;
  43.  for ( ; (e=scanf("%u",&M))==1;)
  44.    printf(" --> %u\n",mult3(M));
  45.  if (e!=EOF)
  46.    {
  47.      printf("Not a integer");
  48.      return -1;
  49.    }
  50.  return 0;
  51. }
  52.  
  53.  
  54.  


La salida que da el programa es:

Código:
3
3  --> 3
4
3  --> 3
5
3  --> 3
6
3 6  --> 9
7
3 6  --> 9
8
3 6  --> 9
9
3 6 9  --> 18
10
3 6 9  --> 18




86  Programación / Programación C/C++ / Re: [Función fscanf] en: 23 Abril 2018, 01:14 am
Código
  1.  


Mis preguntas son:
¿Por qué el carácter '\n' no lo imprime cuando lo lee?
El número 20 se lo salta al terminar de leer la primera línea, ¿Por qué?
fscanf lee '\n' ?  '\n' es un char, cierto?

Espero sus respuestas :D


Como dices, "\n" es un carácter, pero la directiva de matching "%c", según el manual, salta todos los caracteres "white-space", (entendiendo estos como el spacio, el tablador, el fin de línea... todos los que responden a isspace(int c) ).
Si te fijas en la salida , salta del 19 al 21...

Otra aspecto tiene que ver con printf. Propimaente hablando, el caracter '\n' no es carácter imprimible, segun (isprint(c)) ,  sino de control iscntrl(c). En el caso de "\n" dicen que "debe" hacer un scrolling de 1 y empezar en la primera columna, no que imprima propiamente un caracter...



Una solución pasa por dejar usar las rutinas "high-level IO", los streams, a las de "low-level IO", los "file descriptors".

El incoveniente es que perdemos la funcionalidad de la rutina
Código
  1. long ftell(FILE *stream)

pero que podemos simular con

Código
  1. pos=lseek(fd,0,SEEK_CUR)

Por supuesto, para dar una salida formateada, debo volver a las rutinas "high-level" IO, como printf... Pero es un problema aparte de el de lectura read



Hay otro error, que ya muestro corregido, relatio a la función feof()... Esta función sólo tiene valores coherentes después de haber invocado la correspondiente fscanf, es decir, no puede anticipar si la cabeza lectora ha llegafo a fin de fichero..



Ahí va mi propuesta.

Código
  1. #include <stdlib.h> // exit()...
  2. #include <assert.h> // assert
  3. #include <unistd.h> // open,read,close (Low-level IO),
  4. #include <sys/types.h>
  5. #include <sys/stat.h>
  6. #include <fcntl.h> // open,O_RDONLY...
  7. #include <stdio.h> //p printf
  8.  
  9.  
  10. #include <ctype.h> // isprint
  11.  
  12. int main()
  13. {
  14.  char c;
  15.  int n;
  16.  int fd;
  17.  const char *pattern="%d\t%c\t%d\n";
  18.  char row[80];
  19.  if (!(fd=open("texto.txt",O_RDONLY)))
  20.    {
  21.      perror("open");
  22.      exit(EXIT_FAILURE);
  23.    }
  24.  printf("ASCII\tPrint\tPos\n");
  25.  while((n=read(fd,&c,sizeof(char)))> 0)
  26.    {
  27.      assert(isascii(c));
  28.      if ((n=sprintf(row,pattern,c,isprint(c)?c:' ',lseek(fd,0,SEEK_CUR)))<0)
  29. {
  30.  perror("sprintf");
  31.  exit(EXIT_FAILURE);
  32. }
  33.      printf(row);
  34.    }
  35.  if (n==-1)
  36.    {
  37.      perror("read");
  38.      exit(EXIT_FAILURE);
  39.    }
  40.  close(fd);
  41.  exit(EXIT_SUCCESS);
  42. }
  43.  

Pasándole el fichero de texto propuesto
Código:
supholasadkjholasad
adholadsa

El programa arroja la salida siguiente: Cuando es imprimible, imprime su símbolo, cuando es de control, en su lugar, un espacio. (Los números que salen al principio los pone el codgo GeSHi del web, porque si no, perdía el formato de salida... un lío vamos)

Código
  1.  
  2. ASCII Print Pos
  3. 115 s 1
  4. 117 u 2
  5. 112 p 3
  6. 104 h 4
  7. 111 o 5
  8. 108 l 6
  9. 97 a 7
  10. 115 s 8
  11. 97 a 9
  12. 100 d 10
  13. 107 k 11
  14. 106 j 12
  15. 104 h 13
  16. 111 o 14
  17. 108 l 15
  18. 97 a 16
  19. 115 s 17
  20. 97 a 18
  21. 100 d 19
  22. 10 20
  23. 97 a 21
  24. 100 d 22
  25. 104 h 23
  26. 111 o 24
  27. 108 l 25
  28. 97 a 26
  29. 100 d 27
  30. 115 s 28
  31. 97 a 29
  32. 10 30
87  Programación / Programación C/C++ / Re: Funcion recursiva en: 8 Abril 2018, 11:50 am
La programación recursiva... un tema apasionante.

Su origen es anterior a la programación iterativa y, en algunos contextos, se suele referir a ella como una modalidad de programación declarativa. ¿por qué? Porque...

¡ es más sencilla !

Consiste en declarar, no en programar, la expresión que deseas ( Esta sutil distinción se aprecia con la experiencia...).



An = 2An-1 + 3
A0 = 1


 Fíjate que es prácticamente lo mismo que en la expresión matemática.... No hay "variables" (salvo el parámetro), no hay asignaciones, no hay bucles... Casi parece matemáticas y no computación...

Código:
  fun A(in int n) dev int
  {
     case n==0 : dev 1
     case n> 0 : dev 2*A(n-1) + 3
  }

La transcripción a lenguaje como C puede quedar:



Código
  1. #include <stdio.h>
  2.  
  3. unsigned int A(const unsigned int n)
  4. {
  5.  if (n==0) return 1;
  6.  if (n>0) return (2*A(n-1) + 3);
  7. }
  8.  
  9. #define MAXIMUM 20
  10.  
  11. int main(int argc, char *args[])
  12. {
  13.  unsigned int n;
  14.  for( n=0; n<MAXIMUM ; n++)
  15.    printf("A\(%2u\) : %8u\n",n,A(n));
  16. }

La salida da lo siguiente:
Código:
A( 0) :        1
A( 1) :        5
A( 2) :       13
A( 3) :       29
A( 4) :       61
A( 5) :      125
A( 6) :      253
A( 7) :      509
A( 8) :     1021
A( 9) :     2045
A(10) :     4093
A(11) :     8189
A(12) :    16381
A(13) :    32765
A(14) :    65533
A(15) :   131069
A(16) :   262141
A(17) :   524285
A(18) :  1048573
A(19) :  2097149


Si quieres una versión más "C-flavour"/NINJA puedes hacer:

Código
  1. unsigned int A(const unsigned int n)
  2. {
  3.  return n?(2*A(n-1)+3):1 ;
  4. }

Cuidadito que el paso de mates a C no es gratis... Más allá de A=29, la función desborda los valores de unsigned int....







88  Programación / Programación C/C++ / Re: Estructura de datos en C en: 5 Abril 2018, 17:12 pm
 Uff! El tema es muy denso para explicar en un sólo mensaje. Pero
 vamos a intentarlo. Intenta, en un primer momento, olvidar que sabes
 C/C++ o cualquier otro lenguaje.

  Sabes, desde los 10 años, que los enteros ( o los naturales,
 racionales) son un tipo de números dotados de ciertas operaciones (la
 suma, el producto...).  Allá por el último cuarto del siglo XIX, los
 matemáticos europeos (Dedekind, Hilbert, Noether, Peano, Cantor y
 otros... ) intentaban caracterizar las propiedades de esos "entes" y
 sus operaciones. Te sonaran las propiedades commutativa, asociativa,
 y algún valor especial como el elemento neutro,

Código:
 sets
 int
 operations
 + : (int, int) -> int
 constants
 0 : int
 axioms
 a + b = b + a  [comm]
 (a + b) + c = a + (b + c)  [assoc]
 a + 0 = a  [e.neutro]
 ....

 y los términos anillo, semigrupo, grupo conmutativo...

 En computación, esos enteros y sus operaciones tienen una
 representación trivial y limitada en el computador (int, con MAX_INT,
 etc...)  que se proyecta en palabras de 8 o 16 bits y operaciones
 básicas en la ALU...

 Sin embargo, en algoritmia se necesitan además otros "tipos de
 datos", como los que mencionas, (pila, cola, listas...) que también
 se caracterizan por unas propiedades. Éstas también se pueden
 expresar algebraicamente (aunque ya casi nadie lo practica, :-( )
 
 En el caso de las pilas de enteros (stack), la estructura lineal más
 sencilla, tenemos 3/4 operaciones.

 Las operaciones, grosso modo, se dividen en tres grupos.
 - constructoras
 - modificadoras
 - consultoras.

Código:
 sets
 stack, int, bool
 constants
 empty : stack
 operations
 push : (stack,int) -> stack
 pop  : stack - -> stack
 head : stack - -> int
 isempty : stack -> bool
 var
 i : int
 p : stack
 axioms
 pop(push(p,i))=p
 head(push(p,i))=i
 isempty(empty)=true
 ...

 El primer axioma dice que al quitar (pop) un elmento de una pila (p)
 a la que por lo menos se le ha añadido (push) un entero (i), nos
 queda esa pila sin el elemento. Esto también lo sabes "por sentido
 común", pero la novedad, repito, es la forma matemática, cuyo origen
 debemos a los europeos del finales del s. XIX.
 

 Y aquí entra el lenguaje C. Como no están implementadas a nivel
 hardware, el lenguaje nos permite "simularlas" (ojo a la palabra, es
 clave) con construcciones que tienen su base en elementos conocidos,
 como arrays, punteros...


 Los que programan la STL de C++ las ponen a tu disposición una serie
 de estructuras (<stack>, <queue>, <list>) para que las uses en tus
 algoritmos. Son de muy alta calidad y su implementación escapa a la
 de cualquier principiante.

 Pero podemos experimentar haciéndo las nuestras "de juguete".

 - Para empezar, lo haremos con memoria estática, (arrays...)  

 - En otro correo, si quieres, las podemos hacer con memoria dinámica
 (punteros)

 Observa que, al igual que con los int, al usar una array fijo de
 elementos, la expresividad de nuestra implementación esta limitada a
 un número maximo de elementos apilados.  

 Al margen de esto, una operación no es aplicable siempre, como la
 división por 0. Es el caso de la operación pop, o head. No son aplicables
sobre pilas vacías

 En esos casos, su comportamiento está indefinido, por eso se emplea
 la libreria <assert.h>.


Código
  1. #ifndef _STACK_TOY_
  2. #define _STACK_TOY_
  3. #define MAXIMUM 200
  4.  
  5. #include <assert.h>
  6.  
  7. typedef struct
  8. {
  9.  // I : 0 <= many <= MAXIMUM
  10.  unsigned int many;
  11.  unsigned int M[MAXIMUM];
  12. } STACK, *PSTACK;
  13.  
  14. void empty( PSTACK pstack)
  15. {
  16.  pstack->many = 0 ;
  17. }
  18.  
  19. void push(PSTACK pstack, const int i)
  20. {
  21.  assert((pstack->many)<MAXIMUM);
  22.  pstack->M[pstack->many++]=i;
  23.  return;
  24. }
  25.  
  26. void pop(PSTACK pstack)
  27. {
  28.  assert((pstack->many)>0);
  29.  pstack->many--;
  30.  return;
  31. }
  32.  
  33.  
  34. int head(const PSTACK pstack)
  35. {
  36.  assert((pstack->many)>0);
  37.  return pstack->M[pstack->many -1];
  38. }
  39.  
  40. int isempty(const PSTACK pstack)
  41. {
  42.  return  (pstack->many == 0 );
  43. }
  44.  
  45.  
  46. #endif

89  Programación / Programación C/C++ / Re: Funcion palíndromo. en: 5 Abril 2018, 09:29 am
Perdón, tengo una objeción contra mis "objecciones".
En nuestra querida lengua, objeción es con una c. Y objección es un arcaísmo.
Mi latín me ha fallado (otras lenguas lo conservan, como el inglés, object, objection). Quien sabe... A lo mejor dentro de 500 años, los internautas vean que objeción y objeto, son arcaísmos, y mandan poner ojeto y ojeción, como ahora con sujeto y sujeción.



Sin embargo, si tengo dos objecciones 'entre humanos' con este algoritmo:

Ya lo he cambiado allí.
90  Programación / Programación C/C++ / Re: Funcion palíndromo. en: 4 Abril 2018, 17:48 pm
Un palíndromo es una palabra que se 'lee' igual al derecho que al revés...

Luego, si yace en un array, básicamente se trata de comparar el primer 'carácter válido', con el último 'carácter válido', el segundo 'caracter válido', con el penultimo 'caracter válido' hasta llegar aunirse (que será o no el centor 'geométrico'.

Nota que la cuestión para no cometer errores, radica en: es 'carácter válido', lo mismo que en la descripción he marcado 'leer' entre comillas simples, para hacer notarlo...
De acuerdo. Una puntualización "pedantic" (perdón). Son los 'caracteres no válidos' los que delimitan las palabras dentro de una 'frase'

Esto sería un sencillo algoritmo que recorre el array tomando caracteres válidos de ambos extremos y comparándolos:

Código:
buleano = funcion Espalindromo(array bytes B() )
    entero j,k, n

    j= b.length -1 // tamaño del array
    Hacer mientras (k<j)
        hacer mientras b(k) sea espacio   // buscar siguiente 'carácter válido'
            k +=1
        repetir
    
        hacer mientras b(j) sea espacio   // buscar anterior 'carácter válido'
            j -=1
        repetir

        Si b(k) es distinto de b(j) devolver false
 
        k +=1
        j -=1
    repetir

    devolver true
fin funcion

Nota que además de espacio, podría haber tabuladores, y otros signos de puntuación, como comas ',' '; ':', etc... si se da el caso, mejor crear una función que busque el siguiente carácter válido, rechanzando todos los no aceptables... para rechazar solo uno o dos, basta hacerlo 'in situ'.

Hay una errata (no un error) , por dejar la variable k sin inicializar, (k=0). Pero 'entre humanos', no entre compiladores, eso es una errata.

Sin embargo, si tengo dos objeciones 'entre humanos' con este algoritmo:

  • la primera, importante, de corrección,. supongamos la entrada de una frase de 420 espacios ... Entonces el primer bucle anidado progresa indefinidamente más allá de los límites permitidos...Lo que invalida el cómputo
  • La segunda, no tan importante, de complejidad temporal (en constante). Supongamos una frase de 420 caracteres, el primero y el ultimo distintos de espacio e iguales entre si, y el resto, entre medias espacios. Por ejemplo A....418 espacios...A.  Entonces, el algoritmo recorre cada casilla es recorrida 2 veces (420), cuando se puede hacer en una vez.  Repito, es una diferencia de constante, O(2n), vs O(n) en el caso peor. No es tan grave.


Aqui propongo, en primera instancia, el pseudocodigo que propongo
Código:
  Pseudocode:
  -----------

 P:
  n,m=0,N
  while (n<m) and V[n]==' ')
    n=n+1
  while (n<m) and V[m-1]==' ')
    m = m - 1
 I:
  while (m -n > 1 ) and (V[n]==V[m-1] )
     n=n+1
     while (n<m) and V[n]==' ')
       n=n+1
     m = m - 1
     while (n<m) and V[m-1]==' ')
       m = m - 1
  done
  Q:
  return (m-n)<=1

Notemos que en el caso peor, cada casilla se recorre exactamente una vez. Que no nos lie el anidamiento de bucles.... (Se puede hacer sin anidamientos también, pero NEBIRE empezó asi la buena idea...) ::) Quizás una forma "repeat until" sería de lectura más fácil,  pero lo dejo así, por ser la forma canónica de la derivación dijkstra...

Código:
 init,
 while b do
   restore
   step
 done

Aquí va la implementación en C/C++, que aporto, puesto que estamos en la sección de C/C++.


Código
  1. #include <cstring> // strlen
  2. #include <string>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7. int palindrome(const char* W)
  8. {
  9.  int i,j;
  10.  for(i=0,j=strlen(W); (i<j) && (W[i]==' ');i++);
  11.  for( ; (i<j) && (W[j-1]==' ');j--);
  12.  for( ; (j - i) > 1 && (W[i]==W[j-1]); )
  13.    {
  14.      for(i++; (i<j) && (W[i]==' ');i++);
  15.      for(j--; (i< j) && (W[j-1]==' ');j--);
  16.    }
  17.  return ((j-i) <= 1 );
  18. }
  19.  
  20.  
  21.  
  22. int main(int argc, char **args)
  23. {
  24.  string phrase;
  25.  for (; getline(cin,phrase); )
  26.    cout << palindrome(phrase.c_str()) << endl;
  27.  return 0;
  28. }

Estos son unos casos de prueba, donde 1 marca "true", y 0 "false". En el último caso, la linea solo contiene espacios, y como se ´lee igual' al derecho que al revés, da 1.

Código:
dabale arroz a la zorra el              abad
1
dabale arroz a                   la zorra el abad
1
dabale arroz al zorro el abad
0
                                                                                    
1


Y la guinda, (solo para aficionados al calculo Hoare y derivación Disjkstra). La justificación formal de su corrección.


Código:
  Palindrome on a given phrase, length(N) >= 0

  As a problem decission, we model it as an optimization problem

  P : W[N], N>= 0
  Q : 1 >= max i,j : 0 <=i <=j <= N and
                 (j>i) ->
                 ( V[i]!=' ' and V[j-1]!=' ' and
                   #k:0<=k<=i:V[k]!=' ' == #k:j<=k<=N:V[k-1]!=' ' and
                   V[i]!=V[j-1] )  
                   : j-i

i.e., the greatest segment not fullfilling palindrome conditions,
      1 or 0 if all of them fullfill.
      (see picture below)

                             (true)
                             15-16
                          ..........
              7----------------------------------24
          5----------------------------------------25
        4---------------------------------------------27
      3-------------------------------------------------28
    2-----------------------------------------------------29
  1---------------------------------------------------------30
0-------------------------------------------------------------31

0                                                               N=32
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|d|a|b|a|l|e| |a|r|r|o|z| |a| |l|a| |z|o|r|r|a| |e|l| |a|b|a|d| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+


  (Long step strategy)

  B : (m-n) > 1 and V[n]==V[m-1]
  I :  0 <= n <= m <= N and
       (m-n> 1) -> (V[n]!=' ' and V[m-1]!=' ') and
       \forall i,j : 0 <= i < n and m<j<=N and
                     V[i]!=' ' and V[j-1]!=' ' and
    #k:0<=k<=i:V[k]!=' ' == #k:j<=k<=N:V[k-1]!=' '
                   :
                   V[i]==V[j-1] )
  
  C(m,n) = m -n >= 0
  Step: (At least decreases on 2, since B: m-n > 1 )
      n, m = n + (a-n), m-(m-b)
      where
         a = max i : n < i < m and AllessBl(V,n+1,i):i
         b = min i : a <= i < m and AllessBl(V,i,m-1):i


      
  O(n), despite the nested loops

 Pseudocode
  -----------

 P:
  n,m=0,N
  while (n<m-1) and V[n]==' ')
    n=n+1
  while (n<m) and V[m-1]==' ')
    m = m - 1
 I:
  while (m -n > 1 ) and (V[n]==V[m-1] )
     n=n+1
     while (n<m-1) and V[n]==' ')
       n=n+1
     m = m - 1
     while (n<m) and V[m-1]==' ')
       m = m - 1
  done
  Q:
  return (m-n)<=1


  
Páginas: 1 2 3 4 5 6 7 8 [9] 10 11
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines