Foros del Web » Programación para mayores de 30 ;) » C/C++ »

Petando la pila. Problemas y retos usando recursividad.

Estas en el tema de Petando la pila. Problemas y retos usando recursividad. en el foro de C/C++ en Foros del Web. Cita: Iniciado por leosansan Por cierto, habrás observado que sigo al pie de la letra tus recomendaciones en cuanto a que el nombre e las ...

  #61 (permalink)  
Antiguo 02/12/2014, 03:37
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por leosansan Ver Mensaje
Por cierto, habrás observado que sigo al pie de la letra tus recomendaciones en cuanto a que el nombre e las variables sea representativo. Salen unos códigos más largos pero reconozco que me están gustando su uso.

Un fuerte abrazo amigo eferion. NO me canso de repetir la suerte que tenemos de que estés por aquí por tus excelsos conocimientos de C++, por no hablar del C.
Creo que todos acabamos aprendiendo cosas nuevas visitando estos foros.

Desde luego puedo decir que me siento halagado por ser útil, eso quiere decir que todo el esfuerzo que invertí para acabar la carrera no ha sido en vano jejejeje.

Un fuerte abrazo
  #62 (permalink)  
Antiguo 02/12/2014, 03:46
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 18 años
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

No es si se un operador ternario se pueda entender o no. El problema es que los operadores ternarios anidados son infumables de leer, sepas o no. Yo en su momento tuve que traducirlo a if-else para ver que equivalía a la solución de eferion
__________________
github.com/xgbuils | npm/xgbuils
  #63 (permalink)  
Antiguo 02/12/2014, 04:36
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 12 años
Puntos: 28
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por leosansan Ver Mensaje
Tan solo he usado el operador condicional, creo que los usuarios deberían usarlo más para evitar tanto ef-else y sus llaves correspondientes. Pero observa que no he usado operadores a nivel de bit y/o desplazamientos, cosa que también podría haber usado como en su momento hizo kutcher. Pero eso me parece que se sale de los conocimientos generales. Pero un condicional......
Sí, pero es un operador ternario anidado, se ve muy raro y proclibe a errores.

Lo puedes dejar en un punto intermedio:
Código C++:
Ver original
  1. int unsigned comb ( unsigned n , unsigned k )
  2. {
  3.     if (k > n/2) return comb ( n , k );
  4.     else
  5.       return ( k >= 1 ) ?  ( n  * comb (  n - 1 , k - 1 ) / k ) : 1 ;
  6. }

Aunque tanto parentesis me sigue liando:

Código C++:
Ver original
  1. int unsigned comb ( unsigned n , unsigned k )
  2. {
  3.     if (k > n/2) return comb ( n , k );
  4.     if (k >= 1)  return n  * comb (  n - 1 , k - 1 ) / k;
  5.     return 1;
  6. }

Me gusta más así, se puede ver caso por caso en cada linea.
  #64 (permalink)  
Antiguo 02/12/2014, 04:57
Avatar de vangodp  
Fecha de Ingreso: octubre-2013
Mensajes: 934
Antigüedad: 10 años, 9 meses
Puntos: 38
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Tampoco es para tanto XDD:
( k > n / 2 ) ? ( comb ( n , k ) ) : ( k >= 1 ) ? ( n * comb ( n - 1 , k - 1 ) / k ) : 1
traducion...
k es mayor que n/2?
caso si! devuelve ( comb ( n , k ) )
caso no! es k mayor o igual a 1?
caso si!devuelve ( n * comb ( n - 1 , k - 1 ) / k )
caso no! devuelve 1
  #65 (permalink)  
Antiguo 02/12/2014, 05:26
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 1 mes
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por vangodp Ver Mensaje
Tampoco es para tanto XDD:
( k > n / 2 ) ? ( comb ( n , k ) ) : ( k >= 1 ) ? ( n * comb ( n - 1 , k - 1 ) / k ) : 1
traducion...
k es mayor que n/2?
caso si! devuelve ( comb ( n , k ) )
caso no! es k mayor o igual a 1?
caso si!devuelve ( n * comb ( n - 1 , k - 1 ) / k )
caso no! devuelve 1


¡¡¡Este es mi fenómeno¡¡¡.


Como pueden ver en la sencilla explicación de vangodp no tienen mayor ciencia los operadores ternarios o condicionales.

¡¡¡Saluditos!!!

  #66 (permalink)  
Antiguo 02/12/2014, 05:30
Avatar de vangodp  
Fecha de Ingreso: octubre-2013
Mensajes: 934
Antigüedad: 10 años, 9 meses
Puntos: 38
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Me gustan los operadores ternarios =). Sin embargo a las funciones recursivas me estan dando sudores. jajaja

  #67 (permalink)  
Antiguo 02/12/2014, 09:02
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 12 años
Puntos: 28
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por vangodp Ver Mensaje
Tampoco es para tanto XDD:
( k > n / 2 ) ? ( comb ( n , k ) ) : ( k >= 1 ) ? ( n * comb ( n - 1 , k - 1 ) / k ) : 1
traducion...
k es mayor que n/2?
caso si! devuelve ( comb ( n , k ) )
caso no! es k mayor o igual a 1?
caso si!devuelve ( n * comb ( n - 1 , k - 1 ) / k )
caso no! devuelve 1
Oh venga, me vas a decir que mi código no es más sencillo que el de leo xD

Cuanto mas sencillo, mas difícil es equivocarse.
  #68 (permalink)  
Antiguo 02/12/2014, 17:08
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 8 meses
Puntos: 13
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Buenas, al fin vuelvo a pasar por aquí

Solución al primer ejercicio:

Código C++:
Ver original
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. char* no_Rep(char *dst, int i, int len)
  6. {
  7.     int flag = 0;
  8.     if (i < len)
  9.     {
  10.         dst[i] == dst[i - 1] ? (flag = 1) : (flag = 0);
  11.         if (flag)
  12.         {
  13.             memmove(dst + i - 1, dst + i, len - i * sizeof(char));
  14.             i -= 1, len -= 1;
  15.         }
  16.         no_Rep(dst, i + 1, len);
  17.     }
  18.     else
  19.         dst[i] = '\0';
  20.     return dst;
  21. }
  22.  
  23. char* noRep(char* destino, const char* origen)
  24. {
  25.     strcpy(destino, origen);
  26.     return no_Rep(destino, 1, strlen(destino));
  27. }
  28.  
  29. int main(void)
  30. {
  31.     char cad[] = "abccccfabaddeff";
  32.     char* destino = calloc(strlen(cad) + 1, sizeof(char));
  33.  
  34.     printf("%s\n", noRep(destino, cad));
  35.  
  36.     free(destino);
  37.     return 0;
  38. }

Solución al segundo ejercicio:

Código C++:
Ver original
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. #define MAX(a,b) ((a)>(b)?(a):(b))
  5. #define MIN(a,b) ((a)<(b)?(a):(b))
  6.  
  7. int dec[5];
  8.  
  9. int cant(int x, int t)
  10. {
  11.     if (x)
  12.        t +=  1 << (x % 10) * 6, cant(x / 10, t);
  13.     else
  14.         return t;
  15. }
  16.  
  17. int comprobar(int min, int max, int x, int b, int t)
  18. {
  19.     if(min <= max)
  20.     {
  21.         b = x / min;
  22.         if (min * b == x && ((min % 10) || (b%10))
  23.             && t == cant(min, 0) + cant(b, 0) )
  24.         {
  25.             printf("%d = %d x %d ", x, min, b);
  26.             return 1;
  27.         }
  28.         comprobar(min + 1, max, x, b, t);
  29.     }
  30.     else return 0;
  31. }
  32.  
  33. int es_vampiro(int x)
  34. {
  35.     int min, max, b = 0, nd = log10(x) + 1, t = cant(x, 0);
  36.     if (nd % 2) return 0;
  37.  
  38.     min = MAX(dec[nd/2-1], (x+dec[nd/2]-2)/(dec[nd/2]-1));
  39.     max = MIN(x/min, sqrt(x));
  40.  
  41.     return comprobar(min, max, x, b, t);
  42. }
  43.  
  44. int main(void)
  45. {
  46.     dec[0] = 1;
  47.  
  48.     for (int i = 1; i < 5; i++) dec[i] = dec[i - 1] * 10;
  49.     printf("\n%d\n", es_vampiro(13078260));
  50.  
  51.     return(0);
  52. }

Saludos

Última edición por kutcher; 02/12/2014 a las 18:51
  #69 (permalink)  
Antiguo 03/12/2014, 01:23
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 1 mes
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por vangodp Ver Mensaje
Me gustan los operadores ternarios =). Sin embargo a las funciones recursivas me estan dando sudores. jajaja
Y a mi me encantan. Me recuerdan a cuando daba clases y enseñaba un método diferente al usado normalmente por los alumnos pero de gran potencia que reducía los cálculos en en orden de diez. Al principio se resistían a dejar lo conocido pero al cabo de unas semana, y después de probarlo varias veces ya no había vuelta atrás: se quedaban con el nuevo método. Y es que lo nuevo y mejor cuesta al principio, pero una vez que le coges el tranquillo ya no lo sueltas. Estoy seguro que si algunos de los que han opinado en contra del operador condicional, incluido el encadenado, lo ponen en práctica cuatro o cinco veces ya no podrán prescindir de él.

Y respecto a las funciones recursivas amigo vangodp te aconsejo que empieces por algunas"suaves", poco a poco le oras cogiendo el truquillo. Aunque yo la verdad es que donde esté un for o parecido..........

Y hablando del operador condicional, ahí va el primer ejercicio de la segunda tanda ....

Código C++:
Ver original
  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. char* no_Rep ( char *dest , const char *orig , int i , int j ) {
  5.   return (orig [i]=='\0') ? dest [j]='\0' : orig[i]!=orig[i-1] ? dest[j]=orig[i-1], no_Rep(dest,orig,i+1,j+1) : no_Rep(dest,orig,i+1,j),dest ;
  6. }
  7.  
  8. char* noRep(char* destino, const char* origen) {
  9.   return no_Rep ( destino , origen , 1 , 0 ) ;
  10. }
  11.  
  12. int main ( void ) {
  13.   char origen [ ] = "abccccfabaddeff" , destino [ strlen ( origen ) + 1 ] ;
  14.   return printf ( "%s ==> %s\n" , origen , noRep ( destino , origen ) ) , 0;
  15. }



Aprovecho para corregir un pequeño detalle del segundo ejercicio que puse en primer lugar, el de las combinaciones, ya que tenía el tamaño de un array mal dimensionado:

Código C++:
Ver original
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int esVampiro ( int num ) ;
  6. void variaciones_sin_repe ( char numero [ ] , int tam , int permutacioneS , char aux [ ] , char Npermutacion [ permutacioneS ][ tam + 1 ] , int n0 , int n ) ;
  7.  
  8. int main( void ) {
  9.   int num = 13078260 ;
  10.   return printf ( "\n!!! Como lo quiere Pantalaimon ( 0 - 1 ) !!! ==> : [%d]\n\n" , esVampiro ( num ) ) , 0 ;
  11. }
  12.  
  13. int esVampiro (  num ) {
  14.   int i , j , n , tam , permutacioneS = 1 , num0 = num ;
  15.   for ( tam = 1 ; num0 ; tam++ , num0 /= 10 ) ;
  16.   char numero [ tam + 1 ] ;
  17.   if ( tam %2 == 0 )
  18.     return puts ( "NO ES VAMPIRO por numero impar de cifras." ) , 0 ;
  19.   itoa ( num , numero , 10 ) ;
  20.   n = tam / 2 ;
  21.   for( i = 1 , permutacioneS *= ( tam - 1 ) ; i <  n ; ++i , permutacioneS *= ( tam - 1) ) ;
  22.   char aux [ tam + 1 ] , Npermutacion [ permutacioneS ][ tam + 1 ] ;
  23.   variaciones_sin_repe ( numero , tam , permutacioneS , aux , Npermutacion , n, n ) ;
  24.   for( i = 0 ; i < permutacioneS ; i++ )
  25.     for( j = 0 ; j < permutacioneS ; j++ )
  26.       if ( Npermutacion [ i ][ 0 ] == 0 && Npermutacion [ i ][ 0 ] == 0 )
  27.         continue ;
  28.       else if ( ( Npermutacion [ i ][ tam / 2 - 1 ] != 0 || Npermutacion [ i ][ tam / 2 - 1 ] != 0 ) && atoi ( Npermutacion [ i ] ) * atoi ( Npermutacion [ j ] ) == num  ) {
  29.         return printf ( "\nES VAMPIRO: %d = %d * %d\n" , atoi ( Npermutacion [ i ] ) * atoi ( Npermutacion [ j ] ) , atoi ( Npermutacion [ i ] ) , atoi ( Npermutacion [ j ] ) ) , 1 ;
  30.   }
  31.   return puts ( "NO ES VAMPIRO" ) , 0 ;
  32. }
  33.  
  34. void variaciones_sin_repe( char numero [ ] , int tam , int permutacioneS , char aux [ ] , char Npermutacion [ permutacioneS ][ tam + 1 ] , int n0 , int n ){
  35.   int  i ;
  36.   static int j = 0 , permutaciones = 1  ;
  37.   if( n != 0 )
  38.     for( i = 0 ; i < tam - 1 ; ++i ) {
  39.       aux [ j ] = numero [ i ] ;
  40.       ++j ;
  41.       variaciones_sin_repe ( numero , tam , permutacioneS , aux, Npermutacion , n0 , n - 1 );
  42.       --j;
  43.     }
  44.   else {
  45.     aux [ n0 ] = '\0' ;
  46.     strcpy ( Npermutacion [ permutaciones - 1 ] , aux ) ;
  47.     permutaciones++ ;
  48.   }
  49. }

Y ya puestos edito mi segunda opción, toda ella recursiva les recuerdo, pero que ahora muestra los distintos colmillos caso de que los tenga el "vampiro":

Código C++:
Ver original
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int cantidadDigitos ( int num ) ;
  5. int esVampiro ( int numero ) ;
  6. int obtenerNumMinimo ( int digitos ) ;
  7. int obtenerNumMaximo ( int digitos )  ;
  8. int probar ( int numero , int num_1 , int num_0 , int n_minimo , int n_maximo , int digitos , int DigitosNumero [ 10 ] ) ;
  9. int DigitosNumero ( int digitosNumero [ 10 ], int numero , int flag )  ;
  10.  
  11. int main ( ) {
  12.   int numero = 13078260 ;
  13.   return printf ( "\n!!! Como lo quiere Pantalaimon ( 0 - 1 ) !!! ==> : [%d]\n\n" , esVampiro ( numero ) ) , 0 ;
  14.   return 0;
  15. }
  16.  
  17. int cantidadDigitos ( int num ) {
  18.   return ( num == 0 ) ? 0 : 1 + cantidadDigitos ( num / 10 ) ;
  19. }
  20.  
  21. int obtenerNumMinimo ( int digitos ) {
  22.   return ( digitos == 0 ) ? 1 : 10 * obtenerNumMinimo ( - 1 + digitos ) ;
  23. }
  24.  
  25. int obtenerNumMaximo ( int digitos ) {
  26.   return ( digitos == 0 ) ? 1 : 10 * obtenerNumMinimo ( - 1 + digitos ) ;
  27. }
  28.  
  29. void inicializar_digitosNumero ( int digitosNumero [ 10 ] , int indice ) {
  30.   if ( indice < 10 )
  31.     digitosNumero [ indice ] = 0 , inicializar_digitosNumero ( digitosNumero , indice + 1 ) ;
  32. }
  33.  
  34. int DigitosNumero ( int digitosNumero [ 10 ], int numero , int flag ) {
  35.   if ( numero > 0 && flag == 0 )
  36.     digitosNumero [ numero % 10 ]++ , DigitosNumero ( digitosNumero , numero / 10 , 0 ) ;
  37.   else if ( numero > 0 && flag == 1 )
  38.     digitosNumero [ numero % 10 ]-- , DigitosNumero ( digitosNumero , numero / 10 , 1 ) ;
  39.   if ( digitosNumero [ numero % 10 ] < 0 )
  40.     return  0 ;
  41.   else return 1 ;
  42. }
  43.  
  44. int ComprobarDigitos ( int digitosNumero [ 10 ] , int indice , int cont ) {
  45.   if ( indice < 10 )
  46.     if ( digitosNumero [ indice ] == 0 )
  47.       return 1 + ComprobarDigitos ( digitosNumero , indice + 1 , cont + 1 ) ;
  48.     else return
  49.       ComprobarDigitos ( digitosNumero , indice + 1 , cont  ) ;
  50.   return 0 ;
  51. }
  52.  
  53. int esVampiro ( int numero ) {
  54.   int  i , indice = 0 , n_maximo , n_minimo , numero_0 , numero_1 , digitos , digitosNumero [ 10 ] ;
  55.   inicializar_digitosNumero ( digitosNumero , indice ) ;
  56.   DigitosNumero ( digitosNumero , numero , 0 ) ;
  57.   digitos = cantidadDigitos ( numero ) ;
  58.   if ( digitos %2 != 0 )
  59.     return puts ( "\n\n\tNO ES VAMPIRO por numero impar de cifras.\n\n" ) , 0 ;
  60.   n_minimo = obtenerNumMinimo ( - 1 + digitos / 2 ) ;
  61.   n_maximo = obtenerNumMaximo ( digitos / 2 ) ;
  62.   numero_0 = numero_1 = n_minimo ;
  63.   return probar ( numero , numero_1 , numero_0 , n_minimo , n_maximo , digitos , digitosNumero ) ;
  64. }
  65.  
  66.  int probar ( int numero , int num_1 , int num_0 , int n_minimo , int n_maximo , int digitos , int digitosNumero [ 10 ]  ) {
  67.   int  i , indice = 0 ;
  68.   static int flag = 0  ;
  69.   if ( num_1 < n_maximo - 1 && num_0 == n_maximo )
  70.     num_0 = n_minimo , num_1 = numero / n_maximo  ;
  71.   if ( num_0 == n_maximo - 1 && flag == 0 )
  72.     return printf ( "\n\n\t%d NO ES VAMPIRO   flag = %d\n\n"  , numero , flag ) , 0 ;
  73.   if ( num_0 == n_maximo - 1 && flag > 0 )
  74.     return printf ( "\n\n\t%d ES VAMPIRO\n\n"  , numero ) , 1 ;
  75.   if ( num_0 < n_maximo ){
  76.     num_1 = numero / num_0  ;
  77.     if ( num_0 * num_1 == numero  && num_0 > num_1 ) {
  78.     inicializar_digitosNumero ( digitosNumero , 0  ) ;
  79.     DigitosNumero ( digitosNumero , numero , 0 ) ;
  80.     if ( num_0 * num_1 == numero  ) {
  81.       DigitosNumero ( digitosNumero , num_0 , 1 ) ;
  82.       DigitosNumero ( digitosNumero , num_1 , 1 ) ;
  83.       if ( ComprobarDigitos ( digitosNumero , 0 , 0 ) == 10 && ( num_0 % 10 != 0 ||  num_1 % 10 != 0 ) )
  84.         printf ( "\n\n\t%d = %d * %d\n\n" , numero , num_1 , num_0 ) , flag ++ ;
  85.     }
  86.   }
  87.   return  probar ( numero , num_1  , 1 + num_0 , n_minimo , n_maximo , digitos , digitosNumero )  ;
  88.  }
  89. }

Ejemplo de la salida:

Código C++:
Ver original
  1. 13078260 = 2070 * 6318
  2.  
  3. 13078260 = 1863 * 7020
  4.  
  5. 13078260 = 1620 * 8073
  6.  
  7. 13078260 ES VAMPIRO

¡¡¡Saluditos!!!

  #70 (permalink)  
Antiguo 03/12/2014, 01:47
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por leosansan Ver Mensaje
Estoy seguro que si algunos de los que han opinado en contra del operador condicional, incluido el encadenado, lo ponen en práctica cuatro o cinco veces ya no podrán prescindir de él.
La verdad es que se nota que tienes devoción por ese operador jejejeje.

Mi punto de vista personal es que es útil a veces, cuando hay que hacer una comparación sencilla... en otros tantos casos creo que es más rápido de entender un código con el clásico if.

Pero es como todo, son gustos. En mi caso:

* "auto" lo uso casi exclusivamente cuando trabajo con iteradores

Código C++:
Ver original
  1. std::map< std::string, std::string > mapa;
  2.  
  3. // Prefiero esto
  4. for ( auto it = mapa.begin( ); it != mapa.end( ); ++it )
  5.  
  6. // A esto
  7. for ( std::map< std::string, std::string >::iterator it = mapa.begin( );
  8.       it != mapa.end( ); ++it )

* las lambdas las suelo reservar para operacines sencillas sobre contenedores:

Código C++:
Ver original
  1. std::vector< std::pair< int, std::string > > datos = { /* lo que sea */ };
  2. const int numero = 5;
  3. const std::string texto = "prueba";
  4.  
  5. // Prefiero esto
  6. auto it = std::find_if( datos.begin( ), datos.end( ),
  7.                         [numero,texto]( const std::pair< int, std::string > >& pareja )
  8.                         { return pareja.first == numero && pareja.second == texto; } );
  9. if ( it != datos.end( ) )
  10.   // registro encontrado
  11.  
  12. // A esto
  13. for ( auto it = datos.begin( ); it != datos.end( ); ++it )
  14. {
  15.   if ( it->first == numero && it->second == texto )
  16.     // Registro encontrado
  17. }

En este caso, soy consciente de que el código, por longitud, es más largo. Las ventajas que le veo son
  • No me tengo que preocupar por los iteradores
  • Es facil reconocer que con "find_if" estoy buscando un elemento en el vector
  • La lambda es muy sencilla de entender

Debido a esto, creo que el código acaba siendo menos propenso a errores, sobretodo errores tontos de esos que te hacen perder alguna que otra hora hasta que das con ellos.

* El modificador "override" lo uso siempre.

Que el compilador me avise si una función en una clase hija no puede sobreescribir a ninguna función virtual en el padre no tiene precio, sobretodo en aplicaciones de tamaño medio/grande.

--------------------------

Bueno, son cosas que creo que se suelen ver en mis códigos. Como todo en esta vida, a algunos les parecerá mejor y a otros peor. En el fondo tampoco es un tema relevante. Cada uno tiene su propia forma de codificar y, siendo sincero, prefiero veinte condicionales ternarios anidados que algunas de las perlas que me suelo encontrar en mi día a día.
  #71 (permalink)  
Antiguo 03/12/2014, 02:29
Avatar de HackmanC  
Fecha de Ingreso: enero-2008
Ubicación: Guatemala
Mensajes: 1.817
Antigüedad: 16 años, 5 meses
Puntos: 260
Sonrisa Respuesta: Petando la pila. Problemas y retos usando recursividad.

Hola,

Cita:
Iniciado por leosansan Ver Mensaje
En realidad no se trata de permutaciones sino de variaciones. ...
Entre que son peras y son manzanas me tire por las conjugatorias. Ya en serio, el concepto teórico de las permutaciones, variaciones y combinaciones, sin y con repetición, y sin y con orden lo tengo claro. El problema es que no encuentro la forma de generar la secuencia exacta de una forma optimizada, es decir, sin usar ciclos o mas recursiones/comparaciones de las necesarias.

Cita:
Iniciado por Pantaláimon Ver Mensaje
... Dejo este código por si queréis hacer tests: ...
Gracias, me sirvió bastante para hacer algunas pruebas. Aunque ahora pude comprobar que la secuencia de permutaciones es correcta, y los números los comprueba bien, todavía me queda la duda que tenga algún error.


Bueno, entonces así que las permutaciones serán, con el problema que seguramente la mitad de las operaciones las va a realizar de nuevo al transponer los dígitos al otro bando, por ejemplo, 123x456 y 456x123. Al final se generan n! permutaciones, basado el algoritmo de Heap, aunque se generan mas del doble de recursiones.
Código C:
Ver original
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int count(const int value, const int i) {
  5.     return value == 0 ? i : count(value / 10, i + 1);
  6. }
  7.  
  8. void split(const int value, int dst[], const int i) {
  9.     if (value > 0 && i >= 0) {
  10.         dst[i] = value % 10;
  11.         split(value / 10, dst, i - 1);
  12.     }
  13. }
  14.  
  15. int join(int value, const int src[], const int end, const int begin, const int dec) {
  16.     if (end >= begin) {
  17.         value += src[end] * dec;
  18.         return join(value, src, end - 1, begin, dec * 10);
  19.     }
  20.     return value;
  21. }
  22.  
  23. void swap(int dst[], const int a, const int b) {
  24.     int t = dst[b]; dst[b] = dst[a]; dst[a] = t;
  25. }
  26.  
  27. int esvampiro3(const int value, int src[], const int digits) {
  28.     int value1 = join(0, src, (digits / 2) - 1, 0, 1);
  29.     int value2 = join(0, src, digits - 1, (digits / 2), 1);
  30.  
  31.     printf("%.4d x %.4d\n", value1, value2);
  32.  
  33.     if (value1 * value2 == value && !(value1 % 10 == 0 && value2 % 10 == 0)) {
  34.         return 1;
  35.     }
  36.  
  37.     return 0;
  38. }
  39.  
  40. int esvampiro2(const int value, int src[], int c[], const int digits, int i) {
  41.     if(i < digits) {
  42.         if (c[i] < i) {
  43.             swap(src, i, i % 2 ? c[i] : 0);
  44.             if (esvampiro3(value, src, digits)) {
  45.                 return 1;
  46.             }
  47.             c[i]++;
  48.             i = 1;
  49.         } else {
  50.             c[i] = 0;
  51.             i++;
  52.         }
  53.         return esvampiro2(value, src, c, digits, i);
  54.     }
  55.     return 0;
  56. }
  57.  
  58. int esvampiro(const int value, int src[], int c[], const int digits, int i) {
  59.     if (esvampiro3(value, src, digits)) {
  60.         return 1;
  61.     }
  62.     return esvampiro2(value, src, c, digits, i);
  63. }
  64.  
  65. int esVampiro(int num) {
  66.     int i;
  67.     int digits = count(num, 0);
  68.     int n[digits];
  69.     int c[digits];
  70.  
  71.     split(num, n, digits - 1);
  72.     for (i = 0; i < digits; i++) {
  73.         c[i] = 0;
  74.     }
  75.  
  76.     if (digits % 2 == 0) {
  77.         return esvampiro(num, n, c, digits, 1);
  78.     }
  79.  
  80.     return 0;
  81. }
  82.  
  83. int main(int argc, char** argv) {
  84.     printf("%d\n", esVampiro(939658));
  85.     return (EXIT_SUCCESS);
  86. }
Saludos,

ps:

Aparte de que, al parecer, me estoy quedando medio cegatón, anteriormente mencioné que la había comprobado contra la base de datos, lo volví a comprobar y el resultado era 120, no 720 como había indicado anteriormente. Por eso no se salían las cuentas. Ya mas despacio use el formato condicional de Excel para comprobar que los números no se repetían, en lugar de la base de datos.
  #72 (permalink)  
Antiguo 03/12/2014, 06:22
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 8 meses
Puntos: 13
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Lo modifico de forma que también encuentre otros colmillos si es que existen:

Código C++:
Ver original
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. #define MAX(a,b) ((a)>(b)?(a):(b))
  5. #define MIN(a,b) ((a)<(b)?(a):(b))
  6. int dec[5] = {1, 10, 100, 1000, 10000};
  7.  
  8. int cant(int num, int t)
  9. {
  10.     if (num) t +=  1 << (num%10) * 6, cant(num / 10, t);
  11.     else return t;
  12. }
  13. int comprobar(int min, int max, int num, int b, int t, int es)
  14. {
  15.     if(min <= max)
  16.     {
  17.         b = num / min;
  18.         if (min * b == num && ((min % 10) || (b%10))
  19.             && t == cant(min, 0) + cant(b, 0) )
  20.             printf("%d = %d x %d\n", num, min, b), es++;
  21.         comprobar(min + 1, max, num, b, t, es);
  22.     }else return es > 0 ? 1 : 0;
  23. }
  24. int es_vampiro(int num)
  25. {
  26.     int min, max, b = 0, nd = log10(num) + 1, t = cant(num, 0);
  27.     if (nd % 2) return 0;
  28.     nd /= 2;
  29.     min = MAX(dec[nd - 1], (num + dec[nd] - 2)/(dec[nd] - 1));
  30.     max = MIN(num/min, sqrt(num));
  31.     return comprobar(min, max, num, b, t, 0);
  32. }
  33. int main(void)
  34. {
  35.     printf("\n<%d>\n", es_vampiro(13078260));
  36.     return(0);
  37. }

Saludos
  #73 (permalink)  
Antiguo 03/12/2014, 10:13
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 1 mes
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

A la vista de los últimos códigos no me ha quedado más remedio que adelgazar mi último código en ¡¡¡ 40 líneas ¡¡¡ así como el número de argumentos de las funciones:

Código C++:
Ver original
  1. #include<stdio.h>
  2. #include <math.h>
  3.  
  4. int DigitosNumero ( int digitosNumero [ 10 ], int numero , int flag ) {
  5.   if ( numero > 0 && flag == 0 )
  6.     digitosNumero [ numero % 10 ]++ , DigitosNumero ( digitosNumero , numero / 10 , 0 ) ;
  7.   else if ( numero > 0 && flag == 1 )
  8.     digitosNumero [ numero % 10 ]-- , DigitosNumero ( digitosNumero , numero / 10 , 1 ) ;
  9.   else return 1 ;
  10. }
  11.  
  12. int ComprobarDigitos ( int digitosNumero [ 10 ] , int indice , int cont ) {
  13.   if ( indice < 10 )
  14.     return ( digitosNumero [ indice ] == 0 ) ? 1 + ComprobarDigitos ( digitosNumero , indice + 1 , cont + 1 ) : ComprobarDigitos ( digitosNumero , indice + 1 , cont  ) ;
  15.   return 0 ;
  16. }
  17.  
  18. void inicializar_digitosNumero ( int digitosNumero [ 10 ] , int indice ) {
  19.   if ( indice < 10 )
  20.     digitosNumero [ indice ] = 0 , inicializar_digitosNumero ( digitosNumero , indice + 1 ) ;
  21. }
  22.  
  23. int probar ( int numero , int num_1 , int nMin , int nMax , int flag ) {
  24.   int num_2 = 0 , digitosNumero [ 10 ] ;
  25.   if ( num_2 < nMax - 1 && num_1 == nMax )
  26.     num_1 = nMin , num_2 = numero / nMax  ;
  27.   if ( num_1 < nMax ){
  28.     num_2 = numero / num_1  ;
  29.     if ( num_1 * num_2 == numero  && num_1 > num_2 ) {
  30.     inicializar_digitosNumero ( digitosNumero , 0  ) , DigitosNumero ( digitosNumero , numero , 0 ) ;
  31.     DigitosNumero ( digitosNumero , num_1 , 1 ) , DigitosNumero ( digitosNumero , num_2 , 1 ) ;
  32.     if ( ComprobarDigitos ( digitosNumero , 0 , 0 ) == 10 && ( num_1 % 10 != 0 ||  num_2 % 10 != 0 ) )
  33.       printf ( "\n\n\tSI ES VAMPIRO ==> %d = %d * %d\n\n" , numero , num_2 , num_1 ) , flag ++ ;
  34.   }
  35.   return ( num_1 < nMax - 1 ) ? probar ( numero , 1 + num_1 , nMin , nMax , flag ): ( flag == 0 ) ? printf ( "\n\n\t%d NO ES VAMPIRO\n\n"  , numero  ) , 0 : 1 ;
  36.  }
  37. }
  38.  
  39. int esVampiro( int numero ) {
  40.   int  ndigits = log10 ( numero ) , nMin = pow ( 10 , ndigits / 2 ) , nMax = 10 * nMin  ;
  41.   if ( --ndigits %2 != 0 )
  42.     return puts ( "\n\n\tNO ES VAMPIRO por numero impar de cifras.\n\n" ) , 0 ;
  43.   return probar ( numero , nMin , nMin , nMax , 0 ) ;
  44. }
  45.  
  46. int main ( void ) {
  47.   return  printf ( "\n!!! Como lo quiere Pantalaimon ( 0 - 1 ) !!! ==> : [%d]\n\n" , esVampiro ( 13078260  ) ) , 0 ;
  48. }

¡¡¡Saluditos!!!


Última edición por leosansan; 03/12/2014 a las 10:31
  #74 (permalink)  
Antiguo 03/12/2014, 11:31
Avatar de HackmanC  
Fecha de Ingreso: enero-2008
Ubicación: Guatemala
Mensajes: 1.817
Antigüedad: 16 años, 5 meses
Puntos: 260
Sonrisa Respuesta: Petando la pila. Problemas y retos usando recursividad.

Hola,

Cita:
Iniciado por Pantaláimon Ver Mensaje
No es si se un operador ternario se pueda entender o no. El problema es que los operadores ternarios anidados son infumables de leer, sepas o no....
Adicionalmente hay un par de detalles a tomar en cuenta, en algunos casos el código que genera el compilador es el mismo que usando if/then/else. Otro caso es que algunas herramientas de revisión de código, en otros lenguajes, tiene establecido la prohibición del uso del operador ternario; es decir, si se usa el operador no pasa el control de calidad del código.

Prohibirle el uso del operador ternario a un programador en C/C++ creo que es herejía, pero en otros lenguajes, en algunos casos, es común prohibirlo. Como ya mencioné, en algunos casos, no aporta mucho sino complejidad innecesaria.

Saludos,
  #75 (permalink)  
Antiguo 03/12/2014, 14:18
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 18 años
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Hola!

Cita:
Iniciado por leosansan
Yo lo que le propondría a Pantaláimon que alterne Retos de recursividad con otros de mayor libertad. Creo que eso mantendría más activo el tema y se apuntarían más usuarios que en este caso no tienen conocimientos y/o practica suficiente del tema de recursividad y no pueden intervenir. En cambio si se alternan con otros que no sean estrictamente de recursividad seguro que se apuntarían, lo que redundaría en una mayor actividad participativa en el tema.

Como ejemplo, echo de menos la intervención de personas como eferion y amchacon, entre otros, en el último reto. Así que amigo Pantaláimon abre el espectro de problemas, tampoco te vamos a exigir que los supervises, para eso ya estamos los demás usuarios. Tu podrías ser el moderador/supervisor de lo que se vaya proponiendo. aunque tampoco niego el que algún usuario proponga Retos interesantes. amchacon lo intentó pero a mí lo de las listas y árboles como que no, pero otros temas podrían ser interesantes.

Yo tengo en cartera algunos Retos que podrían ser más que interesantes si Pantaláimon lo admite. Hasta entonces me reservo, no quiero fastidiarle su tema.
A mi me parece bien, si creéis que conllevará más participación por mi genial. Si tenéis algún problema interesante quizá me lo podéis decir por privado, discutimos minucias, y yo el viernes me encargaría de redactarlo y pongo quien lo ha propuesto para no quitaros mérito

De todos modos tengo la impresión de que mucha más gente no va a haber por esa situación. Quizá vangodp o dehm se acaben animando. Pero el problema parece ser más de tiempo a disponer que no de conocimientos, pues los problemas iniciales son fáciles. Lo que sucede es que un 99% de gente pasa fugazmente por estos foros para que le resuelvan algún problema y luego desaparece. Así que quizá con paciencia el 1% restante que se incorpora a estos foros les guste este hilo y acaben participando.

Recojo también la opinión de Hackman:
Cita:
Iniciado por Hackman
Realmente es una muy buena idea, habrá que ver si Pantaláimon tiene los recursos necesarios, el tiempo, la dedicación, etc., aunque yo quería evitar eso, y por eso escribí que mi código no estaba optimizado ni especializado, aunque como podrán ver mas arriba, explico que para comprobarlo hice bastantes pruebas.

El problema en mi caso, principalmente es la legibilidad del código, si optimizo cualquiera de las propuestas el código va a ser incomprensible, inclusive para mi mismo (el lenguaje C es bastante obscuro en si mismo); mientras que como está actualmente es bastante claro y mas de algo podrá aprender alguien que tenga un nivel de conocimiento menor.
Claro, a mi en cierto modo, lo interesante de este hilo es también aprender de lo que escriben los demás. Algunas de mis intervenciones han ido en ese sentido, explicando mis soluciones o el algoritmo de complejidad logarítmica para la potencia de kutcher. De todas maneras también entiendo, como dijo eferion que tiene cierto aliciente conseguir el código más eficiente. Y prefiero este tipo de competitividad al de competir por ver quien escribe un código en menos líneas (como estoy viendo en los últimos posts). Pues esta última si que lleva claramente a hacer el código más incomprensible.

Entonces, para llegar a una solución de compromiso entre la competitividad y el aprender, propongo una serie de medidas.
1) Para comparar códigos, me comprometo a medir tiempos de ejecución para los problemas de cierta complejidad (contarNegativos o los juegos de cadenas supongo que no hace falta). A ver si mañana tengo tiempo y publico los tiempos de ejecución para ciertos rangos de numeros de las funciones promedioCollatz y esVampiro.
2) Ahora bien, con el fin de aprender, me gustaría que también hubiera un ambiente de aprendizaje y colaboración. Es decir, si una persona hace un código más eficiente, que no tenga manías en explicar qué "trucos" ha usado. Pues quizá sumando los trucos usados por uno y otro quizá podemos crear soluciones más eficientes, aprender de todos. Pues sentirse parte de un éxito colectivo tampoco está mal, ¿no?
3) Para reducir la tendencia a que los códigos se tornen oscuros, compilaré los códigos en modo optimizado:
Código BASH:
Ver original
  1. g++ -O3 programa.cpp -o programa
Para que códigos no corran más rápido por usar operadores de bits o aritmética entera, un bucle u otro, etc etc... y así priorizando la eficiencia algorítmica frente a los pequeños detalles que siempre se puede encargar de optimizar un compilador.

Cualquier cosa para ir mejorando el tema idme diciendo.

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #76 (permalink)  
Antiguo 03/12/2014, 15:18
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 18 años
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Por cierto, me ha dejado sin palabras la función de kutcher:
Código C:
Ver original
  1. int cant(int num, int t)
  2. {
  3.     if (num) t +=  1 << (num%10) * 6, cant(num / 10, t);
  4.     else return t;
  5. }
No sabía que el return se podía elidir sin que el compilador se queje. la rama del if no devuelve ningún valor pero funciona! ¿Alguna referencia al respecto? Estoy buscando ellipsis return C pero no encuentro nada.

Edit: veo que si compilo en gcc con la etiqueta -Wall me salen warnings en el código. De todas maneras me pregunto si esto tiene un comportamiento válido en C o depende del compilador.
__________________
github.com/xgbuils | npm/xgbuils
  #77 (permalink)  
Antiguo 03/12/2014, 15:41
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 12 años
Puntos: 28
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por Pantaláimon Ver Mensaje
Por cierto, me ha dejado sin palabras la función de kutcher:
Código C:
Ver original
  1. int cant(int num, int t)
  2. {
  3.     if (num) t +=  1 << (num%10) * 6, cant(num / 10, t);
  4.     else return t;
  5. }
No sabía que el return se podía elidir sin que el compilador se queje. la rama del if no devuelve ningún valor pero funciona! ¿Alguna referencia al respecto? Estoy buscando ellipsis return C pero no encuentro nada.

Edit: veo que si compilo en gcc con la etiqueta -Wall me salen warnings en el código. De todas maneras me pregunto si esto tiene un comportamiento válido en C o depende del compilador.
Ese comportamiento es ilegal. La función devolverá basura.
  #78 (permalink)  
Antiguo 03/12/2014, 15:51
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 18 años
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Pero mágicamente con mi compilador gcc funciona. Al igual que la función comprobar.
__________________
github.com/xgbuils | npm/xgbuils
  #79 (permalink)  
Antiguo 03/12/2014, 18:30
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 8 meses
Puntos: 13
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por Pantaláimon Ver Mensaje
No sabía que el return se podía elidir sin que el compilador se queje. la rama del if no devuelve ningún valor pero funciona! ¿Alguna referencia al respecto? Estoy buscando ellipsis return C pero no encuentro nada.

Edit: veo que si compilo en gcc con la etiqueta -Wall me salen warnings en el código. De todas maneras me pregunto si esto tiene un comportamiento válido en C o depende del compilador.
En realidad eso en C tiene un comportamiento indefinido ¿Por que funciona? funciona en la mayoría de los casos porque cant almacena su valor de retorno en la posición utilizada para devolver valores (el registro AX en la CPU) debido a esto en la llamada a la función se encuentra un valor de retorno. Aunque la función no devuelve explícitamente un valor.

Sin embargo, esto se debe evitar no sé en que estaba pensando al hacerlo xD pues ahora quisiera rectificarme:

Código C++:
Ver original
  1. #include <stdio.h>
  2. #include <math.h>
  3. #define MAX(a,b) ((a)>(b)?(a):(b))
  4. #define MIN(a,b) ((a)<(b)?(a):(b))
  5.  
  6. int dec[5] = { 1, 10, 100, 1000, 10000 };
  7. int cant(int num, int t)
  8. {
  9.     if (!num) return t;
  10.     t +=  1 << (num % 10) * 6;
  11.     return cant(num / 10, t);
  12. }
  13. int comprobar(int min, int max, int num, int b, int t, int es)
  14. {
  15.     if(min > max) return es > 0 ? 1 : 0;
  16.     b = num / min;
  17.     if (min * b == num && ((min % 10) || (b%10)) && t == cant(min, 0) + cant(b, 0))
  18.         printf("%d = %d x %d\n", num, min, b), es++;
  19.     return comprobar(min + 1, max, num, b, t, es);
  20. }
  21. int es_vampiro(int num)
  22. {
  23.     int min, max, b = 0, nd = log10(num) + 1, t = cant(num, 0);
  24.     if (nd % 2) return 0;
  25.     nd /= 2;
  26.     min = MAX(dec[nd - 1], (num + dec[nd] - 2)/(dec[nd] - 1));
  27.     max = MIN(num/min, sqrt(num));
  28.     return comprobar(min, max, num, b, t, 0);
  29. }
  30. int main(void)
  31. {
  32.     printf("\n<%d>\n", es_vampiro(13078260));
  33.     return(0);
  34. }

Saludos

Última edición por kutcher; 03/12/2014 a las 19:23
  #80 (permalink)  
Antiguo 04/12/2014, 06:34
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 18 años
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Buenas!

Para tener el código que habéis ido proponiendo más centralizado a la par que pueda poner en cada directorio su eficiencia, y que vosotros podáis ir reclamando si hago trampa o no en su medición, me gustaría subir vuestras soluciones en un repositorio de github donde haría referencia sobre la autoría de cada código y haría referencia al hilo donde se ha escrito.

Si estáis de acuerdo confirmádmelo por privado.

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #81 (permalink)  
Antiguo 04/12/2014, 08:46
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Es un poquito más largo que los últimos que habéis puesto... dado que ya todos habíais puesto vuestras versiones he intentado diferenciarme un poco de lo que se estaba haciendo hasta ahora.

Código C++:
Ver original
  1. #define SWAP(a,b) { int c = *a; *a = *b; *b = c; }
  2.  
  3. const int _factor[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000 };
  4.  
  5. typedef struct _data
  6. {
  7.   int length;
  8.   int digits[15];
  9.   int* endPtr;
  10. } Data;
  11.  
  12. void toArray( int number, Data* data )
  13. {
  14.   if ( number > 0 )
  15.   {
  16.     *data->endPtr = number % 10;
  17.     ++data->endPtr;
  18.     ++data->length;
  19.     toArray( number/10, data );
  20.   }
  21. }
  22.  
  23. int factorial( int n )
  24. {
  25.   if ( n == 2 )
  26.     return 2;
  27.   else
  28.     return n * factorial( n - 1 );
  29. }
  30.  
  31. int toInt( int* first, int* last, const int* factor )
  32. {
  33.   if ( first != last )
  34.   {
  35.     if ( *first )
  36.       return *first * *factor + toInt( first + 1, last, factor + 1 );
  37.     else
  38.       return toInt( ++first, last, factor + 1 );
  39.   }
  40.   else
  41.     return 0;
  42. }
  43.  
  44. void reverse( int* first, int* last )
  45. {
  46.   if ( first <= --last )
  47.   {
  48.     SWAP( first, last );
  49.     reverse( ++first, last );
  50.   }
  51. }
  52.  
  53. int* findLessThan( int* cursor, int* toCompare )
  54. {
  55.   if ( *--cursor > *toCompare )
  56.     return cursor;
  57.  
  58.   return findLessThan( cursor, toCompare );
  59. }
  60.  
  61. void permutation( int* first, int* last, int* cursor )
  62. {
  63.   int* lastCursor = cursor--;
  64.  
  65.   if ( *cursor < *lastCursor )
  66.   {
  67.     int* ptr = findLessThan( last, cursor );
  68.     SWAP( cursor, ptr );
  69.     reverse( lastCursor, last );
  70.   }
  71.   else if ( cursor != first )
  72.     permutation( first, last, cursor );
  73.   else
  74.     reverse( first, last );
  75. }
  76.  
  77. bool es_vampiro( int num, Data* data, int maxPermutaciones )
  78. {
  79.   int* mid = &data->digits[ data->length / 2 ];
  80.   int int1 = toInt( data->digits, mid, _factor );
  81.   int int2 = toInt( mid, data->endPtr, _factor );
  82.  
  83.   if ( ( *data->digits || *mid ) && int1 * int2 == num )
  84.     return true;
  85.  
  86.   if ( --maxPermutaciones )
  87.   {
  88.     permutation( data->digits, data->endPtr, data->endPtr - 1 );
  89.     return es_vampiro( num, data, maxPermutaciones );
  90.   }
  91.  
  92.   return false;
  93. }
  94.  
  95. int es_vampiro( int num )
  96. {
  97.   Data data;
  98.   data.length = 0;
  99.   data.endPtr = data.digits;
  100.   toArray( num, &data );
  101.  
  102.   if ( data.length % 2 )
  103.     return 0;
  104.  
  105.   return es_vampiro( num, &data, factorial( data.length ) )? 1 : 0;
  106. }

Un saludo.
  #82 (permalink)  
Antiguo 04/12/2014, 10:06
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 8 meses
Puntos: 13
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por Pantaláimon Ver Mensaje
Buenas!
Para tener el código que habéis ido proponiendo más centralizado a la par que pueda poner en cada directorio su eficiencia, y que vosotros podáis ir reclamando si hago trampa o no en su medición, me gustaría subir vuestras soluciones en un repositorio de github donde haría referencia sobre la autoría de cada código y haría referencia al hilo donde se ha escrito.

Si estáis de acuerdo confirmádmelo por privado.

Un saludo!
Por mi parte estoy de acuerdo creo que seria lo mas conveniente para mantener el orden y de paso ahora que vuelvo a leer el enunciado la cuestión era retornar uno o cero según el numero dado sea o no vampiro no imprimirlo:

Código C++:
Ver original
  1. #define MAX(a,b) ((a)>(b)?(a):(b))
  2. #define MIN(a,b) ((a)<(b)?(a):(b))
  3.  
  4. int dec[] = { 1, 10, 100, 1000, 10000, 100000 };
  5. int cant(int num, int t)
  6. {
  7.     if (!num) return t;
  8.     t +=  1 << (num % 10) * 6;
  9.     return cant(num / 10, t);
  10. }
  11. int comprobar(int min, int max, int num, int b, int t)
  12. {
  13.     if(min >= max) return 0;
  14.     b = num / min;
  15.     if (min * b == num && ((min % 10) || (b%10))
  16.         && t == cant(min, 0) + cant(b, 0))
  17.         return 1;
  18.     return comprobar(min + 1, max, num, b, t);
  19. }
  20. int es_vampiro(int num)
  21. {
  22.     int min, max, b = 0, nd = log10(num)+1, t = cant(num, 0);
  23.     if (nd % 2) return 0;
  24.     nd /= 2;
  25.     min = MAX(dec[nd - 1], (num + dec[nd] - 2)/(dec[nd] - 1));
  26.     max = MIN(num/min, sqrt(num));
  27.     return comprobar(min, max, num, b, t);
  28. }
  29. int main(void)
  30. {
  31.     printf("\n%d\n", es_vampiro(1001795850));
  32.     return 0;
  33. }

Saludos
  #83 (permalink)  
Antiguo 04/12/2014, 20:09
Avatar de HackmanC  
Fecha de Ingreso: enero-2008
Ubicación: Guatemala
Mensajes: 1.817
Antigüedad: 16 años, 5 meses
Puntos: 260
Sonrisa Respuesta: Petando la pila. Problemas y retos usando recursividad.

Hola,

Cita:
Iniciado por Pantaláimon Ver Mensaje
... Para tener el código que habéis ido proponiendo más centralizado a la par que pueda poner en cada directorio su eficiencia, y que vosotros podáis ir reclamando si hago trampa o no en su medición, ...
En ese caso tendré que hacer algunas modificaciones al código, para optimizarlo por lo menos un poco. Pero aprovechando que en el anterior todavía dejé un ciclo en el main y un array variable, de una vez aprovecho para corregirlo.

Con esas modificaciones esta sería mi solución al reto:
Código C:
Ver original
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int count(const int value, const int i) {
  6.     return value ? count(value / 10, i + 1) : i;
  7. }
  8.  
  9. void split(const int value, int *dst) {
  10.     if (value > 0) {
  11.         *dst = value % 10;
  12.         split(value / 10, dst - 1);
  13.     }
  14. }
  15.  
  16. int join(int value, const int src[], const int end, const int begin, const int dec) {
  17.     if (end - 3 >= begin) {
  18.         value += (src[end - 3] * dec * 1000) + (src[end - 2] * dec * 100) + (src[end - 1] * dec * 10) + (src[end] * dec);
  19.         return join(value, src, end - 4, begin, dec * 10000);
  20.     } else {
  21.         if (end - 2 >= begin) {
  22.             value += (src[end - 2] * dec * 100) + (src[end - 1] * dec * 10) + (src[end] * dec);
  23.             return join(value, src, end - 3, begin, dec * 1000);
  24.         } else {
  25.             if (end - 1 >= begin) {
  26.                 value += (src[end - 1] * dec * 10) + (src[end] * dec);
  27.                 return join(value, src, end - 2, begin, dec * 100);
  28.             } else {
  29.                 if (end >= begin) {
  30.                     value += src[end] * dec;
  31.                     return join(value, src, end - 1, begin, dec * 10);
  32.                 }
  33.             }
  34.         }
  35.     }
  36.     return value;
  37. }
  38.  
  39. void swap(int dst[], const int a, const int b) {
  40.     int t = dst[b]; dst[b] = dst[a]; dst[a] = t;
  41. }
  42.  
  43. int esvampiro3(const int value, int src[], const int digits) {
  44.     int value1 = join(0, src, (digits / 2) - 1, 0, 1);
  45.     int value2 = join(0, src, digits - 1, (digits / 2), 1);
  46.  
  47.     /* printf("%.4d x %.4d\n", value1, value2); */
  48.  
  49.     if (value1 * value2 == value && !(value1 % 10 == 0 && value2 % 10 == 0)) {
  50.         return 1;
  51.     }
  52.  
  53.     return 0;
  54. }
  55.  
  56. int esvampiro2(const int value, int src[], int c[], const int *digits, int i) {
  57.     if(i < *digits) {
  58.         if (c[i] < i) {
  59.             swap(src, i, i % 2 ? c[i] : 0);
  60.             if (esvampiro3(value, src, *digits)) {
  61.                 return 1;
  62.             }
  63.             c[i]++;
  64.             i = 1;
  65.         } else {
  66.             c[i++] = 0;
  67.         }
  68.         return esvampiro2(value, src, c, digits, i);
  69.     }
  70.     return 0;
  71. }
  72.  
  73. int esvampiro(const int value, int src[], int c[], const int *digits, int i) {
  74.     if (esvampiro3(value, src, *digits)) {
  75.         return 1;
  76.     }
  77.     return esvampiro2(value, src, c, digits, i);
  78. }
  79.  
  80. int esVampiro(int num) {
  81.     int digits = count(num, 0);
  82.     int memspc = digits * sizeof(int);
  83.  
  84.     int *n = malloc(memspc);
  85.     int *c = malloc(memspc);
  86.  
  87.     split(num, n + (digits - 1));
  88.     memset(c, 0, memspc);
  89.  
  90.     if (digits % 2 == 0) {
  91.         return esvampiro(num, n, c, &digits, 1);
  92.     }
  93.  
  94.     free(c);
  95.     free(n);
  96.  
  97.     return 0;
  98. }
  99.  
  100. int main(int argc, char** argv) {
  101.     printf("%d\n", esVampiro(1001795850));
  102.     return (EXIT_SUCCESS);
  103. }
Espero que no se me haya pasado algún error,
Saludos,
  #84 (permalink)  
Antiguo 05/12/2014, 02:06
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 1 mes
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

No me dí cuenta de que podía inicializar un array al declaralro. Con esa corrección me ahorro una función y creo que es más eficiente:

Código C++:
Ver original
  1. #include<stdio.h>
  2. #include <math.h>
  3.  
  4. int DigitosNumero ( int digitosNumero [ 10 ], int numero , int flag ) {
  5.   if ( numero > 0 && flag == 0 )
  6.     digitosNumero [ numero % 10 ]++ , DigitosNumero ( digitosNumero , numero / 10 , 0 ) ;
  7.   else if ( numero > 0 && flag == 1 )
  8.     digitosNumero [ numero % 10 ]-- , DigitosNumero ( digitosNumero , numero / 10 , 1 ) ;
  9.   else return 1 ;
  10. }
  11.  
  12. int ComprobarDigitos ( int digitosNumero [ 10 ] , int indice , int cont ) {
  13.   if ( indice < 10 )
  14.     return ( digitosNumero [ indice ] == 0 ) ? 1 + ComprobarDigitos ( digitosNumero , indice + 1 , cont + 1 ) : ComprobarDigitos ( digitosNumero , indice + 1 , cont  ) ;
  15.   return 0 ;
  16. }
  17.  
  18. int probar ( int numero , int num_1 , int nMin , int nMax , int flag ) {
  19.   int i , num_2 = 0 , digitosNumero [ 10 ] = {0};
  20.   if ( num_2 < nMax - 1 && num_1 == nMax )
  21.     num_1 = nMin , num_2 = numero / nMax  ;
  22.   if ( num_1 < nMax ){
  23.     num_2 = numero / num_1  ;
  24.     if ( num_1 * num_2 == numero  && num_1 > num_2 ) {
  25.     DigitosNumero(digitosNumero, numero , 0), DigitosNumero(digitosNumero , num_1 , 1), DigitosNumero(digitosNumero , num_2 , 1) ;
  26.     if ( ComprobarDigitos ( digitosNumero , 0 , 0 ) == 10 && ( num_1 % 10 != 0 ||  num_2 % 10 != 0 ) )
  27.       printf ( "\n\n\tSI ES VAMPIRO ==> %d = %d * %d\n\n" , numero , num_2 , num_1 ) , flag ++ ;
  28.   }
  29.   return ( num_1 < nMax - 1 ) ? probar ( numero , 1 + num_1 , nMin , nMax , flag ): ( flag == 0 ) ? printf ( "\n\n\t%d NO ES VAMPIRO\n\n"  , numero  ) , 0 : 1 ;
  30.  }
  31. }
  32.  
  33. int esVampiro( int numero ) {
  34.   int  ndigits = log10 ( numero ) , nMin = pow ( 10 , ndigits / 2 ) , nMax = 10 * nMin  ;
  35.   return ( --ndigits %2 != 0 ) ? puts ( "\n\n\tNO ES VAMPIRO por numero impar de cifras.\n\n" ) , 0 : probar ( numero , nMin , nMin , nMax , 0 ) ;
  36. }
  37.  
  38. int main ( void ) {
  39.   return  printf ( "\n!!! Como lo quiere Pantalaimon ( 0 - 1 ) !!! ==> : [%d]\n\n" , esVampiro ( 13078260 ) ) , 0 ;
  40. }

¡¡¡Saluditos!!!

  #85 (permalink)  
Antiguo 05/12/2014, 02:10
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por leosansan Ver Mensaje
Código C++:
Ver original
  1. int DigitosNumero ( int digitosNumero [ 10 ], int numero , int flag ) {
  2.   if ( numero > 0 && flag == 0 )
  3.     digitosNumero [ numero % 10 ]++ , DigitosNumero ( digitosNumero , numero / 10 , 0 ) ;
  4.   else if ( numero > 0 && flag == 1 )
  5.     digitosNumero [ numero % 10 ]-- , DigitosNumero ( digitosNumero , numero / 10 , 1 ) ;
  6.   else return 1 ;
  7. }
No te faltan ahí unos "return"??
  #86 (permalink)  
Antiguo 05/12/2014, 02:20
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 1 mes
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por eferion Ver Mensaje
No te faltan ahí unos "return"??
EDITO: Pues creo que no ya que llamo a la función y voy dividiendo por 10 hasta que numero = 0 y ahí entra en acción el return 1.



¡¡¡Saluditos!!!

  #87 (permalink)  
Antiguo 05/12/2014, 03:04
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 9 meses
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

el return está en el último else, si el código entra en, por ejemplo, el primer if, se llama de forma recursiva a DigitosNumero... pero únicamente el último tendrá el return, el resto de llamadas no tendrán escrito su correspondiente return.

Yo esperaría encontrar algo así:

Código C:
Ver original
  1. int DigitosNumero ( int digitosNumero [ 10 ], int numero , int flag ) {
  2.   if ( numero > 0 && flag == 0 )
  3.     return digitosNumero [ numero % 10 ]++ , DigitosNumero ( digitosNumero , numero / 10 , 0 ) ;
  4.   else if ( numero > 0 && flag == 1 )
  5.     return digitosNumero [ numero % 10 ]-- , DigitosNumero ( digitosNumero , numero / 10 , 1 ) ;
  6.   else return 1 ;
  7. }

o así:

Código C:
Ver original
  1. int DigitosNumero ( int digitosNumero [ 10 ], int numero , int flag ) {
  2.   int to_return = 1;
  3.   if ( numero > 0 && flag == 0 )
  4.     digitosNumero [ numero % 10 ]++ , to_return = DigitosNumero ( digitosNumero , numero / 10 , 0 ) ;
  5.   else if ( numero > 0 && flag == 1 )
  6.     digitosNumero [ numero % 10 ]-- , to_return = DigitosNumero ( digitosNumero , numero / 10 , 1 ) ;
  7.   return to_return;
  8. }

Aun así no termino de acostumbrarme a eso de separar las instrucciones por coma en vez de por punto y coma... manías que tiene uno :)
  #88 (permalink)  
Antiguo 05/12/2014, 04:10
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 1 mes
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por eferion Ver Mensaje
el return está en el último else, si el código entra en, por ejemplo, el primer if, se llama de forma recursiva a DigitosNumero... pero únicamente el último tendrá el return, el resto de llamadas no tendrán escrito su correspondiente return.

Yo esperaría encontrar algo así:

Aun así no termino de acostumbrarme a eso de separar las instrucciones por coma en vez de por punto y coma... manías que tiene uno :)
Tal vez me expliqué mal. Está es la cuestión:

Código C++:
Ver original
  1. if ( numero > 0 && flag == 0 )
  2.      digitosNumero [ numero % 10 ]++ , DigitosNumero ( digitosNumero , numero / 10 , 0 ) ;

Si entra en el if es porque "numero es mayor de cero ( y flag también ) y lo que hace el if es incrementar el array y a continuación invoca a la función recursiva con el valor de "numero" dividido entre 10 y sucesivamente es invocada "hasta" que "numero" es es cero, momento en que si que actúa el return 1, pero no antes.

Un fuerte saludo amigo eferion y gracias por mirar con tanto detenimiento el código, gracias y desde ya ¡¡¡ Felices Fiestas ¡¡¡.

¡¡¡Saluditos!!!

  #89 (permalink)  
Antiguo 05/12/2014, 04:27
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 18 años
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Hola,

Realmente no funciona así como explicas, leosan. Y si compilas en modo estricto de dará aviso de que no retornas valor. El problema es el siguiente
Mientras el valor es mayor que 0 llamas recursivamente a la función DigitosNumero, y cuando vale 0 retorna el valor -y aquí viene tu fallo de comprensión- crees que cuando retorna el valor sale de todas las funciones y se va al main. Eso no es así, solo sale de la función actual y vuelve al punto después de la anterior llamada recursiva. Por eso es necesario escribirlo como lo hace eferion.

Inténtalo pensar un poco y lo entenderás. Yo cuando empecé con recursividad también tenía este fallo de concepto.

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #90 (permalink)  
Antiguo 05/12/2014, 04:57
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 12 años, 1 mes
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Captado y me lo aplico..

Saludos.

EDITO: Pues ahora en modo -Wall y -pedantic, y añadiendo un return al final de la función "probar", que ese si que me faltaba, no me lanza ya ningún tipo de warnigs:

Código C++:
Ver original
  1. int DigitosNumero ( int digitosNumero [ 10 ], int numero , int flag ) {
  2.   if ( numero > 0 && flag == 0 )
  3.      digitosNumero [ numero % 10 ]++ , DigitosNumero ( digitosNumero , numero / 10 , 0 ) ;
  4.   else if ( numero > 0 && flag == 1 )
  5.     digitosNumero [ numero % 10 ]-- ,  DigitosNumero ( digitosNumero , numero / 10 , 1 ) ;
  6.   return 1 ;
  7. }

Código C++:
Ver original
  1. Process terminated with status 0 (0 minute(s), 0 second(s))
  2. 0 error(s), 0 warning(s) (0 minute(s), 0 second(s))

Última edición por leosansan; 05/12/2014 a las 05:13

Etiquetas: char, funcion, int, retos, usando
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta

SíEste tema le ha gustado a 5 personas




La zona horaria es GMT -6. Ahora son las 04:22.