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. Buenas! Ya he creado el repositorio. Tengo que ir organizando el código y mejorar los scripts bash que he hecho, pero de momento ya he ...

  #91 (permalink)  
Antiguo 05/12/2014, 11:47
 
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!

Ya he creado el repositorio. Tengo que ir organizando el código y mejorar los scripts bash que he hecho, pero de momento ya he creado los primeros resultados de eficiencia para los números vampiros:
Código BASH:
Ver original
  1. eferion/01/
  2.  
  3. real    2m0.002s
  4. user    1m59.811s
  5. sys 0m0.000s
  6. hackmanc/01/
  7.  
  8. real    2m0.002s
  9. user    1m59.803s
  10. sys 0m0.008s
  11. kutcher/01/
  12. 234
  13. real    0m15.188s
  14. user    0m15.161s
  15. sys 0m0.000s
  16. leosansan/01/ (con iteraciones)
  17.  
  18. real    0m0.605s
  19. user    0m0.552s
  20. sys 0m0.000s
  21. leosansan/02/
  22.  
  23. real    2m0.001s
  24. user    1m59.767s
  25. sys 0m0.000s
  26. pantalaimon/01/
  27. 234
  28. real    0m15.191s
  29. user    0m15.161s
  30. sys 0m0.000s
He hecho una prueba para los vampiros entre 10000000 y 12000000 que no sobrepasen los 2 minutos. El que tiene iteraciones de leosan me da error de ejecución, por eso sale un tiempo tan rápido.

He tenido que modificar algunos códigos pues no compilaban y ahí la he podido liar:
El uso de bool requiere la cabecera stdbool.h, itoa no es del estandar C por lo que he visto. También he borrado printfs y puts para que esto no retrasara la ejecución y he cambiado algun es_vampiro por esVampiro como requeria la especificación. En próximos códigos no me preocuparé de esto pues me quita demasiado tiempo y lo consideraré como error.

Dejo el repositorio con los códigos para que los reviséis si son correctos (los de leosan aún no los he puesto porque no me ha dado su permiso):
https://github.com/xgbuils/retos-c_cpp-foros-del-web

Perdonad que aún no haya puesto los siguientes problemas. A ver si mañana tengo un poco de tiempo y pongo los dos siguientes (más o menos ya los tengo pensados )

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #92 (permalink)  
Antiguo 05/12/2014, 13:04
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,

¿Ya comenzamos a ser trampa Pantaláimon?



Cita:
Iniciado por Pantaláimon Ver Mensaje
... He hecho una prueba para los vampiros entre 10000000 y 12000000 que no sobrepasen los 2 minutos. El que tiene iteraciones de leosan me da error de ejecución, por eso sale un tiempo tan rápido. ...
Bueno, no quiero que se sientan mal, era lógico que yo ganara. ¿O qué? ¿No era el que se tardara más? Sino es así no entendí, yo creí que se trataba de que fuera lo mas lento posible.



Ya en serio, creo que no fue muy buena idea intentar generar la secuencia de números, no me estoy justificando, pero para mí fue muy importante poder generar esa secuencia de permutaciones y me enfoqué mas en eso que en cualquier otra cosa, aunque en este caso evidentemente era mejor una solución diferente.

Lo que si es cierto es que he aprendido bastantes cosas del lenguaje C/C++ en este hilo, el leído el código de cada uno y me parece fascinante, y en sí eso me agrada bastante. Pero habría que cambiarle el título (aunque sé que ya no se puede) a competencias mas que retos, que para mí, aunque se parecen tienen una connotación diferente dependiendo del contexto.

Saludos,
  #93 (permalink)  
Antiguo 05/12/2014, 14:18
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 Pantaláimon Ver Mensaje
Buenas!
.................
(los de leosan aún no los he puesto porque no me ha dado su permiso):
Tienes todos los permisos para hacer lo que quieras, esto es compartir, para lo bueno y lo malo, je je.

Gracias a tí por el "curro que te estas metiendo aunque no soy tan partidario de "competir en eficiencia, lo cual depende en gran medida del tiempo de que dispongas y que no se te adelanten, como de "participar", comparar soluciones y, en definitiva, aprender los unos de los otros. Pero se acepta si es menester.

Un fuerte saludo Pantaláimon y nuevamente gracias por el tiempo y las molestias que te estas tomando.

Saludos también para todos los demás lectores y ¡¡¡ Felices Fiestas ¡¡¡.

P.D: Agradecimiento público para eferion por su explicación vía mp del tema del return. Todo un detalle que dice mucho de su persona. Gracias.


  #94 (permalink)  
Antiguo 05/12/2014, 14:41
 
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 HackmanC Ver Mensaje
Ya en serio, creo que no fue muy buena idea intentar generar la secuencia de números, no me estoy justificando, pero para mí fue muy importante poder generar esa secuencia de permutaciones y me enfoqué mas en eso que en cualquier otra cosa, aunque en este caso evidentemente era mejor una solución diferente.
No se trata de hacer el código mas eficiente, la idea que tenia en mente cuando propuse medir los tiempos eradar un aliciente para qur los algoritmos fuesen lo mas eficientes posible.

Yo por ejemplo prefiero que el código que pongo sea legible a que sea el más rápido... Pero eso no quita para que una vez terminado le de un repaso para ver si se puede mejorar.

Tambien te digo que centrarse únicamente en el tiempo en el caso de funciones recursivas es una tontería porque la mayor parte del tiempo se pierde en las llamadas a las funciones.

No se, yo veo interesante la propuesta y me resulta muy llamativo que estemos la mayoría en el mismo tiempo
  #95 (permalink)  
Antiguo 05/12/2014, 16:58
 
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.

Cuidado! dije que este test que he hecho le he dado un máximo de 2 minutos. Si da el mismo tiempo a muchos es porque sobrepasa los 2 minutos y entonces se corta la ejecución. Vaya, que los códigos que superan esta prueba de momento son el de kutcher y el mío. Si eso, cuando generalice un poco los scripts pongo más pruebas con números más pequeños en el directorio esVampiro/tester/

Tengo en la cabeza un algoritmo usando permutaciones de números que tengo ganas de implementar para demostrar que haciendo bambolear los números también se puede ser eficiente. Pero tengo que ponerme a escribirlo

Por cierto, el tiempo que tenéis para mejorar soluciones es infinito. Iré poniendo las diferentes versiones que propongáis en vuestra carpeta.

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #96 (permalink)  
Antiguo 06/12/2014, 09:06
 
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!

Ahí van dos problemas más:
1) Ordena un array:
Crea una función ordena que dado un array con n enteros, lo transforme en otro con sus elementos ordenados de menor a mayor. El prototipo de la función es:
Código C:
Ver original
  1. void ordena(int array[], int n);
Este problema lo recomiendo hacer 100% recursivo, almenos los participantes habituales, que en eso reside la gracia del problema.

2) Números en descomposición.
Crea una función descompon que descomponga un intervalo de números de a a b ambos inclusive, en sus factores primos. Esta función mostrará el resultado salida estándar. Por ejemplo:
Código C:
Ver original
  1. descompon(2, 10);
Salida:
Código BASH:
Ver original
  1. 2 = 2
  2. 3 = 3
  3. 4 = 2^2
  4. 5 = 5
  5. 6 = 2 * 3
  6. 7 = 7
  7. 8 = 2^3
  8. 9 = 3^2
  9. 10 = 2 * 5
- los factores se mostraran ordenados de menor a mayor
- si el factor no existe no se escribirá
- si el factor sólo aparece una vez no se mostrará elevado a 1 ("5 = 5" y no 5 = 5^1)
- habrá un espacio a izquierda y derecha de los simbolos = y *
- no habrá espacios entre el símbolo de elevar ^

El prototipo de la función es el siguiente:
Código C:
Ver original
  1. void descompon(int a, int b, int ver);
Cuando ver != 0 se mostrará la salida tal como he explicado.
Si ver == 0 se ejecuran los calculos que hayáis implementado pero no se mostrará nada por la salida estándar.
Este lo podéis hacer como queráis, pero recursivo conseguiréis más puntos.

Pues ahora... ¡a petar la pila! O no...

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #97 (permalink)  
Antiguo 06/12/2014, 14:16
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.

Excelente, primero voy a ver si le bajo el tiempo de ejecución al anterior, después le entro a estos, están interesantes los problemas,

Saludos,
  #98 (permalink)  
Antiguo 09/12/2014, 00:53
 
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.

Como no quiero que me pase como con el de los números vampiros, aquí está mi primera propuesta para el ejercicio de ordenar:

Código C:
Ver original
  1. #define NUEVO_NODO(nodo,valor,padre)\
  2.   nodo = &padre->memoria->datos[ padre->memoria->nextIndex++ ]; \
  3.   nodo->ant = 0; nodo->sig = 0; \
  4.   nodo->repeticiones = 1; nodo->valor = valor; \
  5.   nodo->memoria = padre->memoria
  6.  
  7. struct Memoria;
  8.  
  9. struct Nodo
  10. {
  11.   int valor;
  12.   int repeticiones;
  13.  
  14.   struct Nodo* ant;
  15.   struct Nodo* sig;
  16.  
  17.   struct Memoria* memoria;
  18. };
  19.  
  20. struct Memoria
  21. {
  22.   struct Nodo* datos;
  23.   int nextIndex;
  24. };
  25.  
  26. void BuscarValor( struct Nodo* nodo, int valor )
  27. {
  28.   if ( nodo->valor < valor )
  29.   {
  30.     if ( nodo->sig == 0 )
  31.     {
  32.       NUEVO_NODO( nodo->sig, valor, nodo );
  33.     }
  34.     else
  35.     {
  36.       BuscarValor( nodo->sig, valor );
  37.     }
  38.   }
  39.   else if ( nodo->valor > valor )
  40.   {
  41.     if ( nodo->ant == 0 )
  42.     {
  43.       NUEVO_NODO( nodo->ant, valor, nodo );
  44.     }
  45.     else
  46.     {
  47.       BuscarValor( nodo->ant, valor );
  48.     }
  49.   }
  50.   else
  51.     ++nodo->repeticiones;
  52. }
  53.  
  54. void CrearArbol( struct Nodo* nodo, int* array, int longitud )
  55. {
  56.   BuscarValor( nodo, *array );
  57.  
  58.   if ( --longitud )
  59.     CrearArbol( nodo, ++array, longitud );
  60. }
  61.  
  62. void RegenerarArray( int* array, struct Nodo* nodo, int *pos )
  63. {
  64.   if ( nodo->ant )
  65.   {
  66.     RegenerarArray( array, nodo->ant, pos );
  67.     nodo->ant = 0;
  68.   }
  69.  
  70.   if ( nodo->repeticiones )
  71.   {
  72.     array[ (*pos)++ ] = nodo->valor;
  73.     if ( --nodo->repeticiones )
  74.       RegenerarArray( array, nodo, pos );
  75.   }
  76.  
  77.   if ( nodo->sig )
  78.   {
  79.     RegenerarArray( array, nodo->sig, pos );
  80.     nodo->sig = 0;
  81.   }
  82. }
  83.  
  84. void ordena(int array[], int n )
  85. {
  86.   Memoria memoria;
  87.   memoria.datos = (struct Nodo*)malloc( n * sizeof( struct Nodo ) );
  88.   memoria.nextIndex = 1;
  89.  
  90.   struct Nodo* root = memoria.datos;
  91.   root->valor = array[ 0 ];
  92.   root->repeticiones = 1;
  93.   root->sig = 0;
  94.   root->ant = 0;
  95.   root->memoria = &memoria;
  96.  
  97.   CrearArbol( root, &array[ 1 ], n-1 );
  98.  
  99.   int pos = 0;
  100.   RegenerarArray( array, root, &pos );
  101.  
  102.   free( memoria.datos );
  103. }

-------

EDITO: Bueno, ya puestos pongo también una primera aproximación al segundo ejercicio:

Código C:
Ver original
  1. #define IMPRIMIR( base, exponente, primerPrimo ) \
  2.   if ( primerPrimo == 0 ) printf( " *" ); \
  3.   if ( exponente == 1 ) printf( " %d", base ); \
  4.   else if ( exponente > 0 ) printf( " %d^%d", base, exponente )
  5.  
  6. int ComprobarPrimo( int* numero, int candidato )
  7. {
  8.   if ( *numero % candidato == 0 )
  9.   {
  10.     *numero /= candidato;
  11.     return 1 + ComprobarPrimo( numero, candidato );
  12.   }
  13.   return 0;
  14. }
  15.  
  16. void bucleChequeo( int numero, int candidato, int primerPrimo, int ver )
  17. {
  18.   int exp = ComprobarPrimo( &numero, candidato );
  19.   if ( exp > 0 && ver)
  20.   {
  21.     IMPRIMIR( candidato, exp, primerPrimo );
  22.     primerPrimo = 0;
  23.   }
  24.  
  25.   candidato += 2;
  26.   if ( numero > 1 )
  27.     bucleChequeo( numero, candidato, primerPrimo, ver );
  28. }
  29.  
  30. void descompon(int a, int b, int ver)
  31. {
  32.   int actual = a;
  33.   int exp = ComprobarPrimo( &actual, 2 );
  34.   if ( ver )
  35.   {
  36.     printf( "%d =", a );
  37.     IMPRIMIR( 2, exp, 1 );
  38.   }
  39.  
  40.   bucleChequeo( actual, 3, exp == 0, ver );
  41.  
  42.   if ( ver )
  43.     printf ( "\n" );
  44.  
  45.   if ( a < b )
  46.     descompon( ++a, b, ver );
  47. }
Un saludo.

Última edición por eferion; 09/12/2014 a las 02:50
  #99 (permalink)  
Antiguo 09/12/2014, 11:21
 
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
2) Números en descomposición.
Crea una función descompon que descomponga un intervalo de números de a a b ambos inclusive, en sus factores primos. Esta función mostrará el resultado salida estándar
De momento dejo una primera aproximación al segundo ejercicio que ira mejorando lo escribí en C++; en este momento dispongo de poco tiempo, pero voy a ver que se me ocurre para el primer ejercicio :

Código C++:
Ver original
  1. int comprobar_primo( int* num, int e )
  2. {
  3.     if ( *num % e == 0 )
  4.     {
  5.         *num /= e;
  6.         return 1 + comprobar_primo( num, e );
  7.     }
  8.     return 0;
  9. }
  10. string factor_primo(int a, int b, std::stringstream& fact)
  11. {
  12.     unsigned exp = comprobar_primo(&a, b);
  13.  
  14.     if (exp >= 1)
  15.     {
  16.         fact << b;
  17.         if (exp > 1) fact << '^' << exp;
  18.         if (a != 1) fact << " * ";
  19.     }
  20.     if (a > 1) factor_primo(a, b + 1, fact);
  21.  
  22.     return fact.str();
  23. }
  24. void descompon(int a, int b, int ver)
  25. {
  26.     std::stringstream fact;
  27.     if(ver)
  28.         cout << a << " = " << factor_primo(a, 2, fact) << endl;
  29.     if(a < b)
  30.         descompon( a + 1, b, ver);
  31. }

Saludos

Última edición por kutcher; 09/12/2014 a las 11:35
  #100 (permalink)  
Antiguo 10/12/2014, 17: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.

Antes que nada dar la enhorabuena a los participantes , especialmente en el caso de los números vampiros. Ha sido un placer ver los distintos enfoques que se han aplicado para resolver el mismo problema, todo un placer aprender de ustedes.

En realidad considero ganadores morales a todos ya que los tiempos para un solo número son parecidos, no así para un intervalo de 2000000 de valores donde se penaliza ciertas licencias. Pongo como ejemplo mi caso en que inicializo una matriz y al aplicarlo a esos dos millones pues claro que se ralentiza mucho.

Así que no me he resistido a dar, aunque fuera de tiempo cosa que no me importa mucho, "lo importante es participar aunque sea tarde", una solución más matemática al estilo de la propuesta de kutcher.

Me diferencia de la de kutcher pequeños detalles solamente ya que en lo básico es similar:

* No hago uso de macros.

* No uso variables ni arrays globales.

* Calculo los máximos y mínimos de forma ligeramente diferente ya que no hago uso de arrays para el calculo de los mismos.

* Y lo más importante, aplico otra expresión matemática para verificar que los dígitos del número y los factores tienen el mismo conjunto de valores.

Y para esto último he hecho uso del Teorema [47] de Cálculo de León, que dice algo así que para números de un número par de cifras ( al menos hasta ocho ) que se pueden descomponer en dos factores con la mitad de cifras cada uno y el mismo conjunto de cifras, se verifica que la suma de los dígitos del número más las de sus potencias sexta es igual a la suma de esas mismas cantidades aplicadas a sus factores.

Con todo ello me queda el código:

Código C++:
Ver original
  1. #include<stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. int SumaDigitos( int num , int suma ) {
  6.   int factor = ( ( num ) % 10 ) * ( ( num ) % 10 ) ;
  7.   if ( num ) { suma += ( num ) % 10 + factor * factor * factor ; return SumaDigitos ( num / 10 , suma ) ; }
  8.   else return suma ;
  9. }
  10.  
  11. int criba ( int numero , int num_1 , int nMax , int sumaDigitNum  ) {
  12.   static int conT = 0 ;
  13.   int num_2 = numero / num_1 ;
  14.   if( num_1 <= nMax ) {
  15.     num_2 = numero / num_1;
  16.     if ( num_1 * num_2 == numero && ( num_1 % 10 != 0 || num_2 % 10 != 0  )
  17.         && sumaDigitNum == SumaDigitos( num_1 , 0 ) + SumaDigitos( num_2 , 0 ) )
  18.       { printf ( "%d = %d x %d  [%3u]\n", numero , num_1 , num_2, ++conT )  ; return 1 ; }
  19.   return criba ( numero , num_1 + 1 , nMax , sumaDigitNum ) ;
  20.   }
  21.   return 0 ;
  22. }
  23.  
  24. int esVampiro( int numero ) {
  25.   int  sumaDigitNum = SumaDigitos ( numero , 0 ) , ndigits = log10 ( numero ), nMin = 1 + numero / pow ( 10 , 1 + ndigits / 2 ), nMax = sqrt ( numero ) ;
  26.   if ( --ndigits %2 != 0 ) return 0 ;
  27.   return ( criba ( numero , nMin , nMax , sumaDigitNum ) == 0 ) ? 0 : 1 ;
  28. }
  29.  
  30. int main ( void ) {
  31.   int i ;
  32.   for (i = 10000000, esVampiro ( i ) ; i <= 12000000 ; i ++ , esVampiro ( i ) ) ;
  33.   return  0 ;
  34. }
  35.  
  36. /**
  37. int main ( void ) {
  38.   return  printf ( "\n!!! Como lo quiere Pantalaimon ( 0 - 1 ) !!! ==> : [%d]\n\n" , esVampiro ( 11420923 ) ) , 0 ;
  39. }
  40. **/

Y ahora si que estoy en los tiempos del ganador: ¡¡¡¡ kutcher ¡¡¡.

Y ahora un par de comentarios respecto de los códigos de los ganadores:

kutcher:

* Se produce más una salida repetida en los valores, pero sin mayor importancia ya que son apenas dos o tres valores, dependiendo del tamaño y amplitud de la muestra.

Como ejemplo, y usando un contador, se obtiene como salida:

Código C++:
Ver original
  1. 125433 = 231 x 543  [ 23]
  2. 125460 = 204 x 615  [ 24] <==
  3. 125460 = 246 x 510  [ 25] <==
  4. 125500 = 251 x 500  [ 26]
  5. .....................
  6. .....................

Observa que el valor 24 y 25 se repite, cuando no estamos en el caso de buscar distintos colmillos de un mismo número. Creo que el pequeño bug se corrige cambiando:

Código C++:
Ver original
  1. comprobar(min + 1, max, num, b, t, es);
  2.     }else return es > 0 ? 1 : 0;

por:

Código C++:
Ver original
  1. if ( es > 0 ) return 1 ;
  2.         comprobar(min + 1, max, num, b, t, es);
  3.     }else return 0;

Una nimiedad, vamos.

Y ahora una duda que tengo, a ver si me ayudan a resolverla. Al hacer kutcher uso de desplazamientos de bits se obtienen valores muy grandes., si es que yo he interpretado de forma correcta la operación desplazamiento¡to , y si no es así aclarármelo por favor. En esencia esto es lo que yo "creo" que hace:

Código C++:
Ver original
  1. 1 << ( 35 % 10 ) * 6 = 1 << 5 * 6 = 2^30 = 1073741824
  2.  
  3. 5 + 5^6 = 15630

Se ve la diferencia en cuanto al tamaño del método de kutcher y el mío, todo suponiendo que mi interpretación es correcta.

Y la duda viene cuando la cifra módulo es, por ejemplo, nueve, ya que este caso se obtendría:

Código C++:
Ver original
  1. 1 << ( 39 % 10 ) * 6 = 1 << 9 * 6 = 2^54 = 18014398509481984
  2.  
  3.  9 + 9^6 = 531 450

¡¡¡ Duda, duda ¡¡¡. ¿Y cúal es la duda?. Sencillo el valor que se obtiene supera los límites del tipo "int" y como los resultados obtenidos con el código son correctos me lleva a plantearme dos posibilidades:

** El programa trunca el valor, pero al hacerlo tanto en la cifra del número como en la del factor donde aparece dicho dígito, se compensan los errores.

** El programa al encontrarse un valor tan alto pasa a tomarlo como float, manteniendo todas sus cifras, y tampoco se produce error.

En mi caso, al no obtener ni de lejos valores tan altos, no se me plantea esa duda.

Pantaláimon: Me mosquea el resultado que obtengo. Le he añadido al código que colgaste en Internet este main:

Código C++:
Ver original
  1. int main ( void ) {
  2.   int i ;
  3.   for (i = 1260   ; i <= 1260   ; i ++  )
  4.     if ( esVampiro ( i ) == 1 ) ;
  5.   return  0 ;
  6. }

Y el resultado obtenido es realmente extraño:

Código C++:
Ver original
  1. 13 x 99 = 1260

No es ya que las cifras de los factores no coincidan con la del número, es que ni el producto da dicho número. Igual estoy torpe y y no manejo con soltura el copy-paste, pero es que al aplicarlo a un intervalo da como vampiros los que no son y como no a los que si lo son. A ver si me puedes ayudar a entender lo que ocurre

Espero que quede de manifiesto que no sólo nos limitamos a colgar códigos en el tema sino en que como ven esos códigos se estudian, vamos que no es un trabajo que acabe es saco roto.

Y respecto a los otros códigos sólo comentar que de todos he aprendido algo que al fin y al cabo es una de ventajas que obtenemos en este tema. Gracias.

Y ya tan sólo............ ¡¡¡¡ FELICES FIESTAS ¡¡¡¡

¡¡¡Saluditos!!!



  #101 (permalink)  
Antiguo 10/12/2014, 17:38
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 Pantaláimon Ver Mensaje
Buenas!

Ahí van dos problemas más:
1) Ordena un array:
Crea una función ordena que dado un array con n enteros, lo transforme en otro con sus elementos ordenados de menor a mayor. El prototipo de la función es:
Código C:
Ver original
  1. void ordena(int array[], int n);
Este problema lo recomiendo hacer 100% recursivo, al menos los participantes habituales, que en eso reside la gracia del problema.
.................................................
Código BASH:
Ver original
  1. 2 = 2
  2. 3 = 3
  3. 4 = 2^2
  4. 5 = 5
  5. 6 = 2 * 3
  6. 7 = 7
  7. 8 = 2^3
  8. 9 = 3^2
  9. 10 = 2 * 5
- los factores se mostraran ordenados de menor a mayor
- si el factor no existe no se escribirá
- si el factor sólo aparece una vez no se mostrará elevado a 1 ("5 = 5" y no 5 = 5^1)
- habrá un espacio a izquierda y derecha de los simbolos = y *
- no habrá espacios entre el símbolo de elevar ^

El prototipo de la función es el siguiente:
Código C:
Ver original
  1. void descompon(int a, int b, int ver);
Cuando ver != 0 se mostrará la salida tal como he explicado.
Si ver == 0 se ejecuran los calculos que hayáis implementado pero no se mostrará nada por la salida estándar.
Este lo podéis hacer como queráis,
Pues ahora... ¡a petar la pila! O no...

Un saludo!
¡¡¡ Por fin sin ataduras ¡¡¡ . A pelo a mi me queda esto:

Código C++:
Ver original
  1. #include<stdio.h>
  2.  
  3. void descompon ( int a , int b , int ver ) ;
  4.  
  5. int main ( ) {
  6.     return descompon ( 1500 , 1550 , 0 ) , 0 ;
  7. }
  8.  
  9. void descompon( int a , int b , int ver ) {
  10.   int i , numero , n ;
  11.   for ( numero = a ; numero <= b ; numero ++) {
  12.     n = numero ;
  13.     while ( n > 1 ) {
  14.       printf( "%d = " , n ) ;
  15.       for ( i = 2 ; i <= n ; i++ , ver = 0 ) {
  16.         while ( n % i == 0 )  n /=  i , ver++ ;
  17.        if ( ver != 0 ) {
  18.           if ( ver == 1 && i < n )
  19.             printf( "%d * " ,i ) ;
  20.           else if ( ver == 1 && i > n )
  21.             printf( "%d" ,i ) ;
  22.           else if ( ver > 1 && i < n )
  23.             printf( "%d^%d * " ,i , ver ) ;
  24.           else if ( ver > 1 && i > n )
  25.             printf( "%d^%d" ,i , ver )  ;
  26.           }
  27.       }
  28.       putchar ( '\n' );
  29.     }
  30.   }
  31. }

Pero que veo:

Cita:
Iniciado por Pantaláimon Ver Mensaje
Buenas!

Ahí van dos problemas más:
.......................... pero recursivo conseguiréis más puntos.
Pues nada, a por el recursivo y los puntitos:
Código C++:
Ver original
  1. #include<stdio.h>
  2.  
  3. int descompon ( int a , int b , int ver ) ;
  4. int factorizar1 (  int i , int numero , int b , int ver ) ;
  5. void factorizar2 (  int i , int *n , int b , int ver  ) ;
  6. void imprimir( int i , int n, int b  , int ver ) ;
  7.  
  8. int main ( void ) {
  9.     return descompon ( 1500 , 1550, 0 ) , 0 ;
  10. }
  11.  
  12. int descompon ( int a , int b , int ver ) {
  13.   if ( a <= b ) {
  14.     printf( "%d = " , a ) ;
  15.     factorizar1 ( 2 , a ,  b  ,  ver ) ;
  16.     putchar ( '\n' );
  17.     return descompon (  a + 1 ,  b ,  ver ) ;
  18.   }
  19.   return 0 ;
  20. }
  21.  
  22. int factorizar1 (  int i , int numero , int b , int ver ) {
  23.   int n = numero ;
  24.   if ( i <= n ) {
  25.     factorizar2 ( i , &n  , b , ver ) ;
  26.     return factorizar1 ( i + 1  , n  ,  b  ,  ver ) ;
  27.   }
  28.   return 0 ;
  29. }
  30.  
  31. void factorizar2 (  int i , int *n , int b , int ver  ) {
  32.   while ( *n % i == 0 )
  33.     *n /=  i , ver++ ;
  34.   imprimir( i , *n , b , ver ) ;
  35. }
  36.  
  37. void imprimir( int i , int n, int b  , int ver ) {
  38.   if ( ver != 0 ) {
  39.     if ( ver == 1 && i < n )
  40.       printf( "%d * " ,i ) ;
  41.     else if ( ver == 1 && i > n )
  42.       printf( "%d" ,i ) ;
  43.     else if ( ver > 1 && i < n )
  44.       printf( "%d^%d * " ,i , ver ) ;
  45.     else if ( ver > 1 && i > n )
  46.       printf( "%d^%d" ,i , ver )  ;
  47.   }
  48. }

Y aquí una salida de muestra:

Código BASH:
Ver original
  1. 1500 = 2^2 * 3 * 5^3
  2. 1501 = 19 * 79
  3. 1502 = 2 * 751
  4. 1503 = 3^2 * 167
  5. 1504 = 2^5 * 47
  6. 1505 = 5 * 7 * 43
  7. 1506 = 2 * 3 * 251
  8. 1507 = 11 * 137
  9. 1508 = 2^2 * 13 * 29
  10. 1509 = 3 * 503
  11. 1510 = 2 * 5 * 151
  12. 1511 = 1511
  13. 1512 = 2^3 * 3^3 * 7
  14. 1513 = 17 * 89
  15. 1514 = 2 * 757
  16. 1515 = 3 * 5 * 101
  17. 1516 = 2^2 * 379
  18. 1517 = 37 * 41
  19. 1518 = 2 * 3 * 11 * 23
  20. 1519 = 7^2 * 31
  21. 1520 = 2^4 * 5 * 19
  22. 1521 = 3^2 * 13^2
  23. 1522 = 2 * 761
  24. 1523 = 1523
  25. 1524 = 2^2 * 3 * 127
  26. 1525 = 5^2 * 61

NOTITA: He visto en los últimos códigos que no incluyen la función main. Vamos compañeros que al público en general le puede resultar un mundo obtenerla y, al fin y al cabo, son unas pocas líneas de más, ánimo e incluir a a main.

¡¡¡Saluditos!!!

  #102 (permalink)  
Antiguo 10/12/2014, 17:49
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.

Error¡¡¡, no se edito el que quería para corregir una pequeña falta.

Saluditos otra vez.
  #103 (permalink)  
Antiguo 11/12/2014, 05:38
 
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.

Otra posible solución al problema de los vampiros.

Visto que mi planteamiento inicial de hacer permutaciones era demasiado lento he cambiado el punto de vista.

Al final, visto lo visto, se parece un poco al resto de soluciones. En mi caso, para llevar el conteo de los dígitos compongo una máscara que me permite saber si los números comparten el mismo grupo de dígitos.

Código C++:
Ver original
  1. const int _factor[] = { (int)1e0, (int)1e1, (int)1e2,
  2.                         (int)1e3, (int)1e4, (int)1e5,
  3.                         (int)1e6, (int)1e7, (int)1e8,
  4.                         (int)1e9 };
  5.  
  6.  
  7. int Mask( int num )
  8. {
  9.   int digit = num % 10;
  10.  
  11.   if ( num >= 10 )
  12.     return _factor[ digit ] + Mask( num / 10 );
  13.   else
  14.     return _factor[ digit ];
  15. }
  16.  
  17. int es_vampiro( int num, int min, int max, int mask )
  18. {
  19.   if ( num % min == 0 )
  20.   {
  21.     int num2 = num / min;
  22.  
  23.     if ( min % 10 || num2 % 10 )
  24.     {
  25.       if ( Mask( min ) + Mask( num2 ) == mask )
  26.         return 1;
  27.     }
  28.   }
  29.  
  30.   if ( min < max )
  31.     return es_vampiro( num, min + 1, max, mask );
  32.  
  33.   return 0;
  34. }
  35.  
  36. int esVampiro( int num )
  37. {
  38.   int digits = log10( num ) + 1;
  39.  
  40.   if ( digits % 2 )
  41.     return 0;
  42.  
  43.   if ( !(num % 100) && !( num - num / _factor[ digits - 2 ] * _factor[ digits - 2 ] ) )
  44.     return 0;
  45.  
  46.   int mask = Mask( num );
  47.   int min = _factor[ digits / 2 - 1 ] + 1;
  48.   int max = sqrt( 1 + 4.0f * num ) / 2;
  49.  
  50.   return es_vampiro( num, min, max, mask );
  51. }
  52.  
  53. int main(int , char ** )
  54. {
  55.   int counter = 0;
  56.   for ( int i=10000000 ; i<=12000000 ; ++i )
  57.     counter += esVampiro( i );
  58.  
  59.   printf( "%d\n", counter );
  60. }
  #104 (permalink)  
Antiguo 11/12/2014, 06:11
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
Otra posible solución al problema de los vampiros.

Visto que mi planteamiento inicial de hacer permutaciones era demasiado lento he cambiado el punto de vista.

Al final, visto lo visto, se parece un poco al resto de soluciones. En mi caso, para llevar el conteo de los dígitos compongo una máscara que me permite saber si los números comparten el mismo grupo de dígitos.


Me has ganado por un cuerpo de ventaja,. Justamente estaba en ello.

Dejo la función que tenía preparada, pero reconozco que te me has adelantado:

Código C++:
Ver original
  1. int SumaDigitos( int num , int suma ) {
  2.   const int binario [] = {(int)1e0, (int)1e1, (int)1e2,
  3.                           (int)1e3, (int)1e4, (int)1e5,
  4.                           (int)1e6, (int)1e7, (int)1e8,
  5.                           (int)1e9 };
  6.  if ( num ) { suma += (num % 10) * binario [num % 10]  ; return SumaDigitos ( num / 10 , suma ) ; }
  7.   else return suma ;
  8. }

Enhorabuena, fenómeno.

¡¡¡Saluditos!!!

  #105 (permalink)  
Antiguo 11/12/2014, 06:14
 
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
[CENTER]
Me has ganado por un cuerpo de ventaja,. Justamente estaba en ello.
jajajajaja


menos mal que me he dado prisa... no me apetecía tener que pensar otro método diferente a los ya utilizados... que la recursividad penaliza muchísimo el tiempo de ejecución.



La verdad es que cada día está más entretenido este hilo :)

PD.: me ha parecido muy curiosa también la versión que pusiste anoche

Un saludo.
  #106 (permalink)  
Antiguo 11/12/2014, 07:55
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 leosansan Ver Mensaje
Pantaláimon: Me mosquea el resultado que obtengo.
No he dicho nada, puse el printf donde no iba. Ya me extrañaba que la hubieses pifiado, pero no la pifie yo. Sorry¡¡¡

¡¡¡Saluditos!!!



EDITO: Pero con esto:

Código C++:
Ver original
  1. int main ( void ) {
  2.   int i ,cont = 0;
  3.   for (i = 10000000  ; i <= 12000000  ; i ++  )
  4.     if ( esVampiro ( i ) == 1 )  cont++;
  5.   printf("\n\n%d\n", cont);
  6.   return  0 ;
  7. }

no me sale el resultado correcto.

Y con esto otro tampoco:

Código C++:
Ver original
  1. int main ( void ) {
  2.   return  printf ( "\n[%d] ==> [%d]\n\n" , 1260 , esVampiro ( 1260 ) ), 0 ;
  3. }


Última edición por leosansan; 11/12/2014 a las 08:07
  #107 (permalink)  
Antiguo 11/12/2014, 13:00
 
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 leosansan Ver Mensaje
¡¡¡ Duda, duda ¡¡¡. ¿Y cúal es la duda?. Sencillo el valor que se obtiene supera los límites del tipo "int" y como los resultados obtenidos con el código son correctos me lleva a plantearme dos posibilidades:

** El programa trunca el valor, pero al hacerlo tanto en la cifra del número como en la del factor donde aparece dicho dígito, se compensan los errores.

** El programa al encontrarse un valor tan alto pasa a tomarlo como float, manteniendo todas sus cifras, y tampoco se produce error.
Excelente observación leosansan y ahora paso a explicar porque funciona,
como pueden notar nos encontramos ante un comportamiento indefinido en el lenguaje C en este caso con respecto al operador de desplazamiento a la izquierda:

"El resultado es indefinido si el operando de la derecha es negativo, o mayor o igual que el número de bits en el tipo de la expresión izquierda."

Como sabemos al desplazar:

Código C++:
Ver original
  1. 1 << 54

Se espera como resultado el cero, debido a que los bits que salen por la izquierda se pierden, los que entran por la derecha se rellenan con ceros pero en la expresión que utilizo eso no sucede ocurre una especie de rotación aquí dejo una pagina que explica porque pasa eso en los procesadores Intel arquitectura x86:

http://choorucode.com/2004/12/20/c-shift-operator-mayhem/

Ocurre el siguiente desplazamiento con el ejemplo de leosansan el numero 39:
Código C++:
Ver original
  1. 1 << (39 % 10) * 6 = 1 << 9 * 6 = 1 << 54 = 4194304
Código C++:
Ver original
  1. 00000000 01000000 00000000 00000000
Y en vista de todo esto expongo otra opción pero utilizando otro método para identificar los dígitos, como van a ver hago uso del producto de los números primos:

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 primos[10] = {2, 3, 5, 7, 11, 13, 17, 23, 29, 31};
  6.  
  7. int fact(int num, int t)
  8. {
  9.     if (!num) return t;
  10.     t *= primos[num % 10];
  11.     return fact(num/10, t);
  12. }
  13. int comprobar(int min, int max, int num, int b, int t)
  14. {
  15.     if(min >= max) return 0;
  16.  
  17.     b = num / min;
  18.     if (min * b == num && ((min % 10) || (b%10))
  19.         && t == fact(min,1) * fact(b,1) )
  20.         return 1;
  21.  
  22.     return comprobar(min + 1, max, num, b, t);
  23. }
  24. int esVampiro(int num)
  25. {
  26.     int min, max, b = 0, nd = log10(num)+1, t = fact(num, 1);
  27.  
  28.     if (nd % 2) return 0;
  29.     nd /= 2;
  30.     min = MAX(dec[nd - 1], (num + dec[nd] - 2)/(dec[nd] - 1));
  31.     max = MIN(num/min, sqrt(num));
  32.  
  33.     return comprobar(min, max, num, b, t);
  34. }

Un saludo

Última edición por kutcher; 11/12/2014 a las 13:09
  #108 (permalink)  
Antiguo 11/12/2014, 16:40
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 kutcher Ver Mensaje
Excelente observación leosansan y ahora paso a explicar porque funciona,
como pueden notar nos encontramos ante un comportamiento indefinido en el lenguaje C en este caso con respecto al operador de desplazamiento a la izquierda:
.................................................. ........
Se espera como resultado el cero, debido a que los bits que salen por la izquierda se pierden, los que entran por la derecha se rellenan con ceros pero en la expresión que utilizo eso no sucede ocurre una especie de rotación
.................................................. ........
Excelente explicación amigo kutcher, pero en mi ordenata se obtiene el cero:

Código C++:
Ver original
  1. [0] = 1 << 9 * 6

Cita:
Iniciado por kutcher Ver Mensaje
Y en vista de todo esto expongo otra opción pero utilizando otro método para identificar los dígitos, como van a ver hago uso del producto de los números primos:

Código C++:
Ver original
  1. int primos[10] = {2, 3, 5, 7, 11, 13, 17, 23, 29, 31};
También puedes usar los números de la sucesión de Fibonacci no repes inicialmente:

Código C++:
Ver original
  1. int primos[10] = {1,2, 3, 5, 13, 21, 34, 55, 89, 144};

¡¡¡Saluditos!!!

  #109 (permalink)  
Antiguo 11/12/2014, 17:25
 
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 leosansan Ver Mensaje
Excelente explicación amigo kutcher, pero en mi ordenata se obtiene el cero:

Código C++:
Ver original
  1. [0] = 1 << 9 * 6
A ver prueba sin usar números mágicos así:

Código C:
Ver original
  1. int x = 9;
  2. printf("%d", 1 << (x * 6));

Ahora yo tengo una duda ¿Porque no funciona con números mágicos?
  #110 (permalink)  
Antiguo 12/12/2014, 04:00
 
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
Excelente explicación amigo kutcher, pero en mi ordenata se obtiene el cero:

Código C++:
Ver original
  1. [0] = 1 << 9 * 6
Estas usando constantes.

Es muy probable que el compilador haga los cálculos en compilación y ponga el resultado, sin traducir directamente a la arquitectura.

Tienes que declarar una variable con algún valor aleatorio (por ejemplo el teclado), hacer esa operación y usarla en otro sitio para evitar que el compilador haga alguna optimización.

Pasandole el flag -S al compilador te lo compila a código ASM, y ahí se puede ver como ha traducido el compilador tú código.
  #111 (permalink)  
Antiguo 16/12/2014, 11:17
 
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!

Disculpad mi ausencia. Estos días me ha sido complicado pasar por aquí y no he podido publicar nuevos problemas. Este viernes publico dos más.

Aquí tenéis el enlace de momento sólo con los códigos de esVampiro actualizado:
https://github.com/xgbuils/retos-c_c...nges/esVampiro

La versión de código de un usuario de un desafío en concreto esta en:
Código BASH:
Ver original
  1. /challenges/{nombre_desafio}/users/{nombre_usuario}/{numero_version}/src/{usuario_version}.c
Los tests aplicados a un desafío están en:
Código BASH:
Ver original
  1. challenges/{nombre_desafio}/tests/test{numero}.c

Los tiempos los calculo en Ubuntu con el comando time y sumando el tiempo de usario + el de sistema. En principio si son programas de un sólo hilo debería ser una medida correcta. Si alguien sabe de alguna otra manera mejor de evaluar el tiempo de ejecución del programa sin tener las interferencias de otros procesos que se estén ejecutando a la vez, que me lo comenté e intento aplicarlo.

Próximamente cuando mejore los scripts para automatizar la compilación y generación de código (Al final he decidido crear los scripts en node.js) y sean más portables. Crearé un fichero readme.md con la explicación de cómo lo podéis compilar vosotros mismos y probar la ejecución de los códigos.

De momento para la gente que use algún derivado de UNIX, use gcc y tenga instalado los comandos time y timeout y node.js y git.
Puede clonar el repositorio, instalar las dependencias con el comando:
Código BASH:
Ver original
  1. npm install
Y luego puede con los siguientes comandos:
- Generar códigos fuente (sólo requiere node):
Código BASH:
Ver original
  1. node make src
- Generar códigos fuente y binarios (requiere node y gcc):
Código BASH:
Ver original
  1. node make
- Generar códigos fuente, binarios, y mostrar resultados de los tests por pantalla (require node, gcc, time y timeout):
Código BASH:
Ver original
  1. node make ranking

Aplicando este último comando para el reto de los vampiros tenemos estos resultados:
Código BASH:
Ver original
  1. { test01:
  2.    [ { time: 8.49, user: 'eferion-01' },
  3.      { time: 8.7, user: 'eferion-02' },
  4.      { time: 9.62, user: 'hackmanc-01' },
  5.      { time: 0.56, user: 'kutcher-01' },
  6.      { time: 0.56, user: 'kutcher-02' },
  7.      { time: 7.58, user: 'leosansan-01' },
  8.      { time: 0.63, user: 'leosansan-02' },
  9.      { time: 0.6, user: 'pantalaimon-01' } ],
  10.   test02:
  11.    [ { time: 0, user: 'eferion-01' },
  12.      { time: 0, user: 'eferion-02' },
  13.      { time: 0, user: 'hackmanc-01' },
  14.      { time: 0, user: 'kutcher-01' },
  15.      { time: 0, user: 'kutcher-02' },
  16.      { time: 0, user: 'leosansan-01' },
  17.      { time: 0, user: 'leosansan-02' },
  18.      { time: 0, user: 'pantalaimon-01' } ],
  19.   test03:
  20.    [ { time: 59.49, user: 'eferion-01' },
  21.      { time: 59.51, user: 'eferion-02' },
  22.      { time: 59.03, user: 'hackmanc-01' },
  23.      { time: 0.73, user: 'kutcher-01' },
  24.      { time: 0.73, user: 'kutcher-02' },
  25.      { time: 11.5, user: 'leosansan-01' },
  26.      { time: 0.74, user: 'leosansan-02' },
  27.      { time: 0.74, user: 'pantalaimon-01' } ] }

A ver si estos días me pongo con los problemas que propuse. Me extraña que excepto eferion nadie haya tocado el problama del algoritmo de ordenación. Con de la de algoritmos que hay. La gracia para los que tuvimos que estudiarlos, es aplicar alguno pero de manera recursiva.

Un saludo!

PD.: Por cierto, leosan, si me pasas el código de los vampiros no recursivo pero sin printfs y puts y siguiendo un estándar estricto (recuerdo que te tuve que cambiar el itoa por un sprintf), lo podría colgar y pruebo si funciona y que tan rapido es. Porque el que probé la otra vez que modifiqué yo me daba errores de ejecución. Quizá toqué algo que no debía.
__________________
github.com/xgbuils | npm/xgbuils

Última edición por Pantaláimon; 16/12/2014 a las 11:23
  #112 (permalink)  
Antiguo 17/12/2014, 04:30
 
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

Fijándome en los códigos de la función descompon, estoy viendo implementaciones que no respetan del todo lo que pedí en el enunciado. O al menos que no siguen la idea que quise expresar con esa norma.
Cita:
Cuando ver != 0 se mostrará la salida tal como he explicado.
Si ver == 0 se ejecuran los calculos que hayáis implementado pero no se mostrará nada por la salida estándar.
La idea de tener una bandera ver era para poder ponerla a 0 y medir el tiempo de ejecución del código sin las interferencias que pudiera producir mostrar la salida estándar. El problema es que hay códigos que dejan de hacer ciertos cálculos que no son meramente de mostrar los resultados cuando ver == 0.

Un ejemplo claro es el de kutcher donde hay el siguiente código:
Código C++:
Ver original
  1. if(ver)
  2.         cout << a << " = " << factor_primo(a, 2, fact) << endl;
si ver == 0 no se ejecutará factor_primo que, a parte de instrucciones de visualización, también ejecuta otras instrucciones como la función comprobar_primo que son 100% de cálculo.

La interpretación de leosan ha sido tratar el flag ver como un exponente. O almenos eso parece en la función imprimir. De hecho, el código de leosan no implementa lo pedido ya que llama a descompon ( 1500 , 1550, 0 ) y esto no debería mostrar ninguna salida por pantalla.

La implementación de eferion es la que es más parecida a lo que quería. Si ver == 0 el cálculo de los factores y su exponente se hace siempre. En cambio el conjunto de cálculos sobre cómo mostrarlos (encapsulados en la macro IMPRIMIR) no se hacen.

Yo quizá buscaba la interpretación más estricta, haciendo todos los cálculos, incluso ejecutando las condiciones que calculan cómo mostrar la descomposición de factores de los números y sólo evitando las funciones de salida estándar como printf, puts, el operador << de C++.

Pongo el código de eferion modificado para poner de ejemplo de la idea que quiero expresar:
Código C:
Ver original
  1. #include <stdio.h>
  2.  
  3. #define IMPRIMIR( base, exponente, primerPrimo, ver ) \
  4.   if ( primerPrimo == 0 && ver) printf( " *" ); \
  5.   if ( exponente == 1 && ver) printf( " %d", base ); \
  6.   else if ( exponente > 0 && ver) printf( " %d^%d", base, exponente )
  7.  
  8. int ComprobarPrimo( int* numero, int candidato )
  9. {
  10.   if ( *numero % candidato == 0 )
  11.   {
  12.     *numero /= candidato;
  13.     return 1 + ComprobarPrimo( numero, candidato );
  14.   }
  15.   return 0;
  16. }
  17.  
  18. void bucleChequeo( int numero, int candidato, int primerPrimo, int ver )
  19. {
  20.   int exp = ComprobarPrimo( &numero, candidato );
  21.   if ( exp > 0)
  22.   {
  23.     IMPRIMIR( candidato, exp, primerPrimo, ver);
  24.     primerPrimo = 0;
  25.   }
  26.  
  27.   candidato += 2;
  28.   if ( numero > 1 )
  29.     bucleChequeo( numero, candidato, primerPrimo, ver );
  30. }
  31.  
  32. void descompon(int a, int b, int ver)
  33. {
  34.   int actual = a;
  35.   int exp = ComprobarPrimo( &actual, 2 );
  36.  
  37.   if ( ver ) printf( "%d =", a );
  38.   IMPRIMIR( 2, exp, 1, ver );
  39.  
  40.   bucleChequeo( actual, 3, exp == 0, ver );
  41.  
  42.   if ( ver )
  43.     printf ( "\n" );
  44.  
  45.   if ( a < b )
  46.     descompon( ++a, b, ver );
  47. }
  48.  
  49. int main() {
  50.     descompon(2, 1000, 0);
  51.     return 0;
  52. }

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils

Última edición por Pantaláimon; 17/12/2014 a las 04:41
  #113 (permalink)  
Antiguo 17/12/2014, 04:56
 
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 Pantaláimon Ver Mensaje
En cambio el conjunto de cálculos sobre cómo mostrarlos (encapsulados en la macro IMPRIMIR) no se hacen.
No se no se... me parece muy estricto el tener que preguntar tres veces lo mismo:

  • Si ver entonces imprimo el signo de multiplicar
  • Si ver y el exponente es uno entonces imprimo la base
  • Si ver y el exponente es mayor que uno entonces saco la base por el exponente

Eso es equivalente a:

  • Si ver:
    • Imprimo el signo de multiplicar
    • Si el exponente es uno, imprimo la base
    • Si el exponente es mayor que uno, saco la base por el exponente

Solo que ligerísimamente más rápido y, hasta cierto punto, natural.

No son cálculos significativos, yo entiendo que el núcleo del algoritmo es, precisamente, descomponer el número y es eso lo que se pretende evaluar.

Al menos yo lo entendí así.
  #114 (permalink)  
Antiguo 17/12/2014, 05:41
 
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.

Ya... se supone que todas las soluciones más o menos funcionarán igual. Calcularán los factores y su exponente y en función de estos valores se mostrarán de una manera u otra. A primera vista, creo que los cálculos condicionales de cómo mostrar el resultado serán prácticamente iguales y no tendrán la menor trascendencia. Pero quería ser precavido, pues no sé si alguien se le puede ocurrir una manera muy diferente de solucionar el problema y, entonces, seria más dificil poner el límite. Mientras que poner el limite justo en los printf's es algo que no tiene ningún tipo de ambigüedad.

De todos modos quizá me estoy pasando de precavido. En una primera vista, con tu solución ya me quedaba satisfecho. La de kutcher y leosansan, no :p

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #115 (permalink)  
Antiguo 17/12/2014, 05:51
 
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.

La idea que yo me hice cuando vi el enunciado es que "ver=0" iba a servir para lanzar la batería de tests... así se consigue que los tests se ejecuten rápidamente.

"ver=1" se reserva para las pruebas de cada uno... así no hay que tocar el código a la hora de elegir entre pruebas de funcionamiento y de rendimiento.

Con esa premisa en mente, lo único a tener en cuenta sería que, si "ver=0" lo único que no se ha de ejecutar es el código que imprime en pantalla... el cómo se lo curre cada uno ya...

jejeje

Un saludo
  #116 (permalink)  
Antiguo 17/12/2014, 06:14
 
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
La idea de tener una bandera ver era para poder ponerla a 0 y medir el tiempo de ejecución del código sin las interferencias que pudiera producir mostrar la salida estándar. El problema es que hay códigos que dejan de hacer ciertos cálculos que no son meramente de mostrar los resultados cuando ver == 0.

Un ejemplo claro es el de kutcher donde hay el siguiente código:
Entiendo en un primer momento lo mal interprete, pero bueno a corregirlo:

Código C++:
Ver original
  1. #include <iostream>
  2. #include <sstream>
  3.  
  4. int comprobar_primo( int* num, int e )
  5. {
  6.     if (*num%e == 0)
  7.     {
  8.         *num /= e;
  9.         return 1 + comprobar_primo(num, e);
  10.     }
  11.     return 0;
  12. }
  13. std::string factor_primo(int a, int b, std::stringstream& fact)
  14. {
  15.     unsigned exp = comprobar_primo(&a, b);
  16.     if (exp >= 1)
  17.     {
  18.         fact << b;
  19.         if (exp > 1) fact << '^' << exp;
  20.         if (a != 1) fact << " * ";
  21.     }
  22.     if (a > 1) factor_primo(a, b + 1, fact);
  23.     return fact.str();
  24. }
  25. void descompon(int a, int b, int ver)
  26. {
  27.     std::stringstream fact;
  28.     std::string result = factor_primo(a, 2, fact);
  29.     if(ver)
  30.         std::cout << a << " = " << result << std::endl;
  31.     if(a < b)
  32.         descompon( a + 1, b, ver);
  33. }
  34. int main(void)
  35. {
  36.     descompon(2, 1000, 1);
  37.     return 0;
  38. }

Y ahora con respecto al primer reto, al decir tu lo transforme en otro con sus elementos ordenados te refieres a almacenar los elementos ordenados en un segundo array

Un saludo
  #117 (permalink)  
Antiguo 17/12/2014, 06:19
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 Pantaláimon Ver Mensaje
De todos modos quizá me estoy pasando de precavido. En una primera vista, con tu solución ya me quedaba satisfecho. La de kutcher y leosansan, no :p

Un saludo!

Corrigo. Ahora en la función imprimir se imprime sólo si ver!=0...otra cosa es que lo aproveche como exponente. Y es que si el exponente es cero sencillamente no es un factor primo y no se imprime:

Código C++:
Ver original
  1. #include<stdio.h>
  2.  
  3. int descompon ( int a , int b  , int ver ) ;
  4. int factorizar1 (  int i , int numero , int b , int ver ) ;
  5. void factorizar2 (  int i , int *n , int b , int ver  ) ;
  6. void imprimir( int i , int n, int b  , int ver ) ;
  7.  
  8. int main ( void ) {
  9.     int ver ;
  10.     return descompon ( 1500 , 1550,  ver ) , 0 ;
  11. }
  12.  
  13. int descompon ( int a , int b , int ver ) {
  14.   if ( a <= b ) {
  15.     printf( "%d = " , a ) ;
  16.     factorizar1 ( 2 , a ,  b  ,  ver ) ;
  17.     putchar ( '\n' );
  18.     return descompon (  a + 1 ,  b ,  ver ) ;
  19.   }
  20.   return 0 ;
  21. }
  22.  
  23. int factorizar1 (  int i , int numero , int b , int ver ) {
  24.   int n = numero ;
  25.   if ( i <= n ) {
  26.     factorizar2 ( i , &n  , b , ver ) ;
  27.     return factorizar1 ( i + 1  , n  ,  b  ,  ver ) ;
  28.   }
  29.   return 0 ;
  30. }
  31.  
  32. void factorizar2 (  int i , int *n , int b , int ver  ) {
  33.   while ( *n % i == 0 )
  34.     *n /=  i , ver++ ;
  35.   imprimir( i , *n , b , ver ) ;
  36. }
  37.  
  38. void imprimir( int i , int n, int b , int ver ) {
  39.   if ( ver != 0 ) {
  40.     if ( ver == 1 && i < n )
  41.       printf( "%d * " ,i ) ;
  42.     else if ( ver == 1 && i > n )
  43.       printf( "%d" ,i ) ;
  44.     else if ( ver > 1 && i < n )
  45.       printf( "%d^%d * " ,i , ver ) ;
  46.     else if ( ver > 1 && i > n )
  47.       printf( "%d^%d" ,i , ver )  ;
  48.   }
  49. }

¡¡¡Saluditos!!!

  #118 (permalink)  
Antiguo 17/12/2014, 06:40
 
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.

Cita:
Iniciado por eferion
Con esa premisa en mente, lo único a tener en cuenta sería que, si "ver=0" lo único que no se ha de ejecutar es el código que imprime en pantalla... el cómo se lo curre cada uno ya...
Claro, por eso me puse estricto al máximo diciendo que lo único que había que no ejecutar son los printfs y los demás cálculos sí. Ahora se me ha ocurrido un ejemplo:

De momento los algoritmos usados hacen los cálculos al vuelo y no lo guardan en ninguna estructura de datos. Imaginemos que alguien encuentra un algoritmo que más eficiente que los de ahora que trabaja con un array de strings y los va rellenando de la siguiente forma:

Inicio:
Código C:
Ver original
  1. array = {
  2.   "", // 2
  3.   "", // 3
  4.   "", // 4
  5.   "", // 5
  6.   ""  // 6
  7. }
Paso 1:
Código C:
Ver original
  1. array = {
  2.   "2", // 2
  3.   "", // 3
  4.   "2^2", // 4
  5.   "", // 5
  6.   "2"  // 6
  7. }
Paso 2:
Código C:
Ver original
  1. array = {
  2.   "2", // 2
  3.   "3", // 3
  4.   "2^2", // 4
  5.   "", // 5
  6.   "2 * 3"  // 6
  7. }
Paso 3:
Código C:
Ver original
  1. array = {
  2.   "2", // 2
  3.   "3", // 3
  4.   "2^2", // 4
  5.   "5", // 5
  6.   "2 * 3"  // 6
  7. }

Y luego se usa esa estructura para mostrar los resultados. ¿Debería contar como cálculo el recorrer el array para mostrar las soluciones, aunque no se muestren? ¿O con llenar el array con esos datos ya valdría? Esta estructura de datos es sencilla, pero podrían inventarse otras, y quizá costaría más ver el límite.

Por eso cada vez estoy más convencido que con ver == 0 se hagan todos los cálculos salvo los printfs. Es lo menos ambiguo.
__________________
github.com/xgbuils | npm/xgbuils
  #119 (permalink)  
Antiguo 17/12/2014, 06: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.

Cita:
Iniciado por Pantaláimon Ver Mensaje
Imaginemos que alguien encuentra un algoritmo que más eficiente que los de ahora que trabaja con un array de strings y los va rellenando de la siguiente forma:
En ese caso, es un requisito del algoritmo usar ese mapa de memoria, por lo que tiene que apechugar con las consecuencias que ello conlleva.

Si el requisito del algoritmo es que debe realizar los cálculos pero no imprimirlos por pantalla, mientras cumpla es correcto.

Por otro lado, si alguien implementa un algoritmo usando algo como en tu ejemplo, se entiende que el uso de ese mapa le aporta beneficios por otro lado... al final la conclusión a la que llego es la misma:

* Si "ver=0" hace los cálculos? SI
* Los cálculos que hace son correctos? SI
* En base a lo anterior, es válido el algoritmo? SI

Por ejemplo, en el ejercicio de ordenar yo he optado por usar una estructura intermedia en vez de hacer las operaciones al vuelo... es mi decisión, no puedo quejarme si debido a ello mi código resulta ser más lento.

No se si se entiende la idea.
  #120 (permalink)  
Antiguo 17/12/2014, 07:26
 
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.

Cita:
Iniciado por eferion
Por otro lado, si alguien implementa un algoritmo usando algo como en tu ejemplo, se entiende que el uso de ese mapa le aporta beneficios por otro lado... al final la conclusión a la que llego es la misma:

* Si "ver=0" hace los cálculos? SI
* Los cálculos que hace son correctos? SI
* En base a lo anterior, es válido el algoritmo? SI
Creo que en eso estamos de acuerdo, el punto en cuestión es qué cálculos deben hacerse cuando ver == 0.
¿Los cálculos de las condiciones de tu macro IMPRIMIR deberían realizarse independientemente de si ver == 0 o no?
Yo en cierto momento me he sentido satisfecho pensando que quizá no haría falta. Pero ahora pienso que sí deberían hacerse por las razones que he explicado. Es decir, la función con ver == 0 debe hacer todos los cálculos excepto los directamente relacionados con la salida estándar.

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils

Última edición por Pantaláimon; 17/12/2014 a las 07:33

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 17:54.