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. Quisquilloso no. Son unas normas para poder comparar el código entre los diferentes propuestas de una manera más rigurosa. Pues aunque tu alardees de usar ...

  #31 (permalink)  
Antiguo 21/11/2014, 22: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.

Quisquilloso no. Son unas normas para poder comparar el código entre los diferentes propuestas de una manera más rigurosa. Pues aunque tu alardees de usar una sola función para resolver el cálculo de obtener el promedio, en realidad no es verdad. Ya que parte del calculo que debería resolver promedioCollatz, lo resuelves en la función main. Con lo cual también estás usando dos funciones para resolver el problema propuesto. Y además con un inconveniente, ¿qué ocurre si quieres llamar a la función promedioCollatz con diferentes números en un mismo código?

Nadie impide usar variables estáticas o globales. Pero es importante que la función de lo mismo independientemente del contexto en que se aplique.

Y no creo que resolver los cálculos, en vez de en la función main, en otra auxiliar tenga porque coartar la inventiva.

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #32 (permalink)  
Antiguo 22/11/2014, 01:41
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.

Con dos funciones llego al mismo resultado que eferion. Lo pongo más compactado pero es lo mismo:

Código C++:
Ver original
  1. #include <stdio.h>
  2. #define NUMERO 17
  3.  
  4. double Collatz ( unsigned num ) ;
  5. double promedioCollatz ( unsigned num ) ;
  6.  
  7. int main ( ) {
  8.   printf ( "\n%g\n" , promedioCollatz ( NUMERO )  ) ;
  9.   return 0 ;
  10. }
  11.  
  12. double Collatz ( unsigned num )  {
  13.   return ( num == 1 ) ? 0 : ( ( num %  2 != 0 ) ?  1 + Collatz ( 3 * num + 1 ) : 1 + Collatz ( num / 2 ) ) ;
  14. }
  15.  
  16. double promedioCollatz ( unsigned num ) {
  17.   return ( num == 1 ) ? 0 : ( Collatz( num ) + ( num - 1 ) * promedioCollatz( num - 1 ) ) / num ;
  18. }

No olvidar mi anterior propuesta usando dos argumentos.

¡¡¡Saluditos!!!

  #33 (permalink)  
Antiguo 22/11/2014, 13:28
 
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 eferion Ver Mensaje
Esa función está mal... no tiene que devolver el número de pasos hasta llegar al 1... tienes que devolver "el promedio", es decir, si esa función recibe un "4" tiene que hacer el siguiente cálculo: ( PASOS_COLLATZ( 4 ) + PASOS_COLLATZ( 3 ) + PASOS_COLLATZ( 2 ) + PASOS_COLLATZ( 1 ) ) / 4
menuda pifiada me he mandado xD.. esto es lo que provoca el andar apurado y el no aisimilar bien el problema pero bueno para el caso dejo mi solución:

Código C++:
Ver original
  1. unsigned collatz(unsigned n )
  2. {
  3.     if ( n == 1 ) return 0;
  4.     return (n % 2) ? 1 + collatz(n * 3 + 1) : 1 + collatz(n / 2);
  5. }
  6. double promedioCollatz(unsigned n)
  7. {
  8.     double x = collatz(n);
  9.     return (n == 1) ? x :(x + (n-1) * promedioCollatz(n-1)) / n;
  10. }

Saludos
  #34 (permalink)  
Antiguo 22/11/2014, 20:03
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,

Al parecer ya van mas adelantados, aún así me uno con las dos propuestas iniciales, seguramente no están optimizadas, son solamente otro punto de vista de los problemas.

Esta ya estaba resuelta anteriormente casi de igual forma, el concepto creo que es el mismo en todos los casos,

Problema #1:

Código C:
Ver original
  1. #include <stdio.h>
  2.  
  3. /* más codigo si hace falta */
  4.  
  5. int contar(const int ds[], const int bx) {
  6.     return (bx < 0 ? 0 : (ds[bx] < 0) + contar(ds, bx - 1));
  7. }
  8.  
  9. int contarNegativos(int arr[], int n) {
  10.     /* Escribir código */
  11.     return contar(arr, n - 1);
  12. }
  13.    
  14. int main (void) {
  15.     int arr[] = {1, 4, -3, 2, -1, -8, 0, 1};
  16.     int n = sizeof arr / sizeof *arr;
  17.  
  18.     /* calcular cantidad de negativos */
  19.     int cantidad = contarNegativos(arr, n);
  20.     /* mostrar cantidad de negativos */
  21.     printf("%d\n", cantidad);
  22.     return 0;
  23. }

Para esta use un concepto un poco diferente, los programadores que tiene tiempo en esto seguramente van a observar un patrón bastante antiguo basado en los segmentos de la memoria, antiguamente no existía la memoria flat como ahora, así que había que trabajar con segmentos y offsets. Es solamente otro punto de vista el problema.

El único cambio a la plantilla original es en el tamaño reservado, que para contener el resultado realmente debía ser mas grande.

Problema #2:

Código C:
Ver original
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. /* más codigo si hace falta */
  6.  
  7. #define SEG(ds, ws) (ds * (ws + 1))
  8.  
  9. char* diacpy(char* dst, const char* src, const int ws, const int ds, const int bx) {
  10.     if (bx >= ws) {
  11.         dst[SEG(ds, ws)] = '\0';
  12.     } else {
  13.         memset(&dst[SEG(ds, ws)], 0x20, ws);
  14.         memcpy(&dst[SEG(ds, ws) + bx], &src[bx], 1);
  15.         dst[SEG(ds, ws) + ws] = 0x0a;
  16.         diacpy(dst, src, ws, ds + 1, bx + 1);
  17.     }
  18.     return dst;
  19. }
  20.  
  21. char* diag(char* cadena, char* resultado) {
  22.     /* Escribir código */
  23.     return diacpy(resultado, cadena, strlen(cadena), 0, 0);
  24. }
  25.  
  26. int main (void) {
  27.     char cadena [] = "abcde";
  28.     int n = strlen(cadena);
  29.  
  30.     char* resultado = malloc((n + 1) * n + 1); /* doy mas espacio del necesario */
  31.  
  32.     // a partir de la cadena de caracteres retornar la nueva que tenga los caracteres en diagonal
  33.     resultado = diag(cadena, resultado);
  34.  
  35.     //mostrar resultado
  36.     puts(resultado);
  37.  
  38.     free(resultado);
  39.     return 0;
  40. }

En sí, no hay nada optimizado ni especializado y posiblemente tenga algún error. Con un poco mas de tiempo voy a pensar en alguna propuesta para los siguientes problemas.

Saludos,
  #35 (permalink)  
Antiguo 24/11/2014, 14: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.

En vista de que todas las soluciones expuestas (respetando la plantilla) son similares a la de eferion quisiera exponer otra pero usando tres funciones para variar :

Código C++:
Ver original
  1. unsigned int collatz(unsigned int n )
  2. {
  3.     if ( n == 1 ) return 0;
  4.     return (n % 2) ? 1 + collatz(n * 3 + 1) : 1 + collatz(n / 2);
  5. }
  6. double totalCollatz(unsigned int n)
  7. {
  8.     return (n != 0) ? collatz(n) + totalCollatz(n - 1) : 0;
  9. }
  10.  
  11. double promedioCollatz(unsigned int n)
  12. {
  13.     return totalCollatz(n)/n;
  14. }

Saludos
  #36 (permalink)  
Antiguo 27/11/2014, 12: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.

Buenas!

Voy dejando mis soluciones:

La primera usa la siguiente regla recurrente:
Código :
Ver original
  1. comb(n, k) = n * comb(n-1, k) * (n - k) para n > k
Y se aprovecha de lo que observó leosansan. Es decir, que no hace falta hacer más de n/2 llamadas recurrentes. Aunque yo he usado una función auxiliar para así no comprobar una condición que será verdadera desde la segunda vez que se llama la función recursiva:

Código C:
Ver original
  1. unsigned icomb (unsigned n, unsigned k) {
  2.     if      (n < k) // fuera de la definición, comportamiento definido por mi arbitrariamente
  3.         return 0;
  4.     else if (n > k)
  5.         return n * icomb(n - 1, k) / (n - k);
  6.     else
  7.         return 1;
  8. }
  9.  
  10. unsigned comb (unsigned n, unsigned k) {
  11.     if (2 * k < n)
  12.         return icomb(n, n - k);
  13.     else
  14.         return icomb(n, k);
  15. }

Por lo que he visto las otras soluciones sobre comb se han basado en otra recurrencia parecida:
Código :
Ver original
  1. comb(n, k) = n * comb(n-1, k-1) / k
Pero mirando esto me he fijado en el caso de eferion y, a parte de algo extraño como multiplicar y luego dividir por el mismo número (n - k) / (n - k), no funciona tal como debería para n == k.
Hay que considerar que según la definición comb(n, n) == 1. En la solución de eferion devuelve 0.

Vamos al segundo problema. En dicho caso he aplicado el patrón mayoritario con una función collatz auxiliar. Sin embargo, en mi caso he añadido algo de "memoria" a la función auxiliar collatz con ayuda de una variable estática. De esta manera no hace cálculos repetidos:

Código C:
Ver original
  1. #include <stdio.h>
  2. #define N 100000
  3.  
  4. unsigned collatz (unsigned num)
  5. {
  6.     static int tabla[N] = {0};
  7.     if ( num <= 1 ) {
  8.         return 0;
  9.     } else if(num < N) {
  10.         if(tabla[num] != 0) {
  11.             return tabla[num];
  12.         } else {
  13.           return tabla[num] = 1 + collatz(num % 2 ? num * 3 + 1 : num / 2);
  14.         }
  15.     } else {
  16.         return 1 + collatz( num % 2 ? num * 3 + 1 : num / 2);
  17.     }
  18. }
  19.  
  20. double promedioCollatz (unsigned num)
  21. {
  22.   if (num > 0)
  23.     return (collatz(num) + (num - 1) * promedioCollatz(num - 1)) / num;
  24.   else
  25.     return 0;
  26. }
  27.  
  28. int main (void) {
  29.   unsigned i;
  30.   for (i = 1; i < 10000; ++i) {
  31.       printf("%6u %lf ", i, promedioCollatz(i));
  32.       puts("");
  33.   }
  34.   return 0;
  35. }

Cita:
Iniciado por Hackman
Para esta use un concepto un poco diferente, los programadores que tiene tiempo en esto seguramente van a observar un patrón bastante antiguo basado en los segmentos de la memoria, antiguamente no existía la memoria flat como ahora, así que había que trabajar con segmentos y offsets. Es solamente otro punto de vista el problema.
Me ha sorprendido tu versión. Buena aportación. Te animo a que sigas por aquí.

Un saludo! ... y mañana más
__________________
github.com/xgbuils | npm/xgbuils

Última edición por Pantaláimon; 27/11/2014 a las 12:56
  #37 (permalink)  
Antiguo 28/11/2014, 02:57
 
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.

¡Viernes otra vez! Así que os traigo dos problemas más.

1) ¡No te repitas!

Escribe una función noRep que dada una cadena de caracteres, construya otra sin repetición de caracteres consecutivos. Por ejemplo si la cadena es "abccccfabaddeff", debe devolver "abcfabadef". El prototipo de la función en C es:
Código C:
Ver original
  1. char* noRep(char* destino, const char* origen);
Donde origen es la cadena con caracteres repetidos y destino es la cadena donde se guardará la cadena resultado sin caracteres no repetidos. La función retorna la cadena destino.
Como restricción de diseño, decir que dentro de noRep no se reservará memoria dinámica tal que luego tenga que ser liberada fuera de la función. Vaya, que en caso de que queráis reservar memoria dinamicamente para destino, hacedlo fuera de la función.

Prototipo para C++:
Código C++:
Ver original
  1. std::string noRep(std::string origen);
origen es la cadena con posibles caracteres repetidos, el valor que retorna es la cadena resultado sin caracteres repetidos.

2) Números vampiros

Dentro de la fauna de números encontramos unos que tienen colmillos. Son los números vampiros. Los números vampiros son aquellos que son resultado del producto de dos números con el mismo número de dígitos, llamados colmillos. Además, el conjunto de dígitos de los dos colmillos ha de ser el mismo conjunto que los digitos del número vampiro. Es decir, 1260 es vampiro porque es el producto de 21*60 y, 21 y 60 en conjunto está formado por los mismos digitos que 1260.
Lo mismo ocurre con 1395 que es producto de 93*15.

Los números tal como los he definido anteriormente son vampiros salvo cierta excepción: un número no es vampiro si solamente se puede contruir como el producto de dos colmillos que ambos acaben en 0. 1260, como decíamos es vampiro, pero 126000 no lo es porque, no hay colmillos que lo construyan sin ser ambos acabados en 0. 126000 = 210 * 600.

El segundo problema consistirá en contruir una función esVampiro que retorne 1 si un número es vampiro ó 0 si no lo es. Prototipo de la función:
Código C:
Ver original
  1. int esVampiro(int num);

Y ahora... ¡A petar la pila!
__________________
github.com/xgbuils | npm/xgbuils

Última edición por Pantaláimon; 28/11/2014 a las 03:03
  #38 (permalink)  
Antiguo 28/11/2014, 04:10
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 12 años
Puntos: 28
Respuesta: Petando la pila. Problemas y retos usando recursividad.

El primer ejecicio:
Código C++:
Ver original
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. string noRep(string cadena)
  6. {
  7.     if (cadena.empty() || cadena.size() == 1) return cadena;
  8.     else
  9.     {
  10.         if (cadena[0] == cadena[1])
  11.         {
  12.             return noRep(cadena.substr(1));
  13.         }
  14.         else
  15.         {
  16.             string a = noRep(cadena.substr(1));
  17.             a.insert(a.begin(),cadena[0]);
  18.             return a;
  19.         }
  20.     }
  21. }
  22.  
  23. int main()
  24. {
  25.     cout<<noRep("abccccfabaddeff")<<endl;
  26. }

Pero si le añadimos el parámetro indice, es mucho más eficiente (y sencillo):

Código C++:
Ver original
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. string noRep(string cadena,unsigned int indice = 0)
  6. {
  7.     if (cadena.empty() || cadena.size() == 1 || indice == cadena.size()-1) return cadena;
  8.     else
  9.     {
  10.         if (cadena[indice] == cadena[indice+1])
  11.         {
  12.             cadena.erase(indice,1);
  13.             return noRep(cadena,indice);
  14.         }
  15.         else
  16.         {
  17.             indice++;
  18.             return noRep(cadena,indice);
  19.         }
  20.     }
  21. }
  22.  
  23. int main()
  24. {
  25.     cout<<noRep("abccccfabaddeff")<<endl;
  26. }

En cuanto al segundo, valen que sean repetidos los colmillos?, por ejemplo el número 25 sería vampiro ya que: 5*5
  #39 (permalink)  
Antiguo 28/11/2014, 04:38
 
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 amchacon
En cuanto al segundo, valen que sean repetidos los colmillos?, por ejemplo el número 25 sería vampiro ya que: 5*5
Dije:
Cita:
Iniciado por Pantalaimon
Además, el conjunto de dígitos de los dos colmillos ha de ser el mismo conjunto que los digitos del número vampiro.
Código :
Ver original
  1. Conjunto de los digitos de 25: {2, 5}
  2. Conjunto de los digitos de los colmillos: {5}
  3. {5} != {2,5}
Por lo tanto, 25 no es vampiro.

De todas maneras creo que me hace falta precisar algo. Cuando dije conjunto, me refería a multiconjunto, pero no quería asustar a la gente. Es decir, hagamos volar la imaginación y supongamos que 145431 == 431 * 155:
Código :
Ver original
  1. Conjunto de los digitos de 145431: {1, 3, 4, 5}
  2. Conjunto de los digitos de los colmillos 431 y 155: {1, 3, 4, 5}
Pero no son vampiros, porque cuando hablaba de conjunto, me refería a conjunto con repeticiones de números, es decir:
Código :
Ver original
  1. Multiconjunto de los digitos de 145431: {1, 1, 3, 4, 4, 5}
  2. Multiconjunto de los digitos de los colmillos 431 y 155: {1, 1, 3, 4, 5, 5}
Como los multiconjuntos no son iguales no es un número vampiro.

Espero que ahora haya quedado un poco más claro. Si no, préguntadme dudas.

Edit: NOTA IMPORTANTE: la firma para noRep en C++ puede tener la variante
Código C++:
Ver original
  1. std::string noRep(const std::string&);
. Antes me he colado y he puesto la firma pasando el parámetro por valor.

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

Última edición por Pantaláimon; 28/11/2014 a las 05:42
  #40 (permalink)  
Antiguo 28/11/2014, 16:37
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
¡Viernes otra vez! Así que os traigo dos problemas más.

1) ¡No te repitas!


2) Números vampiros

Dentro de la fauna de números encontramos unos que tienen colmillos. Son los números vampiros. Los números vampiros son aquellos que son resultado del producto de dos números con el mismo número de dígitos, llamados colmillos. Además, el conjunto de dígitos de los dos colmillos ha de ser el mismo conjunto que los digitos del número vampiro. Es decir, 1260 es vampiro porque es el producto de 21*60 y, 21 y 60 en conjunto está formado por los mismos digitos que 1260.
Lo mismo ocurre con 1395 que es producto de 93*15.

Los números tal como los he definido anteriormente son vampiros salvo cierta excepción: un número no es vampiro si solamente se puede contruir como el producto de dos colmillos que ambos acaben en 0. 1260, como decíamos es vampiro, pero 126000 no lo es porque, no hay colmillos que lo construyan sin ser ambos acabados en 0. 126000 = 210 * 600.

El segundo problema consistirá en contruir una función esVampiro que retorne 1 si un número es vampiro ó 0 si no lo es. Prototipo de la función:
Código C:
Ver original
  1. int esVampiro(int num);

Y ahora... ¡A petar la pila!
¡¡¡ A petarla ¡¡¡

Reconozco que la primera idea ha sido la de usar a la de usar bruta, pero me he contenido y he preferido dejarlo para otra ocasión Así que he optado por un camino más rebuscado, sencillamente a lo que a primera vista invita el reto.

Y es que si un número es de, por ejemplo seis cifras, tan sólo hay un número de variaciones de 6^3 variaciones tomadas las cifras de tres en tres, lo que da tan solo 216 casos posibles. Una vez obtenidas tan solo hay que ir multiplicándolas entre sí a ver si sale el número original,

Las dificultades inherentes ha sido obtener las variaciones y "bambolear" el array de cifras de una función a otra.

Cumple los cometidos encomendados, no valen dos grupos de cifras terminados ambos en cero y filtro aquellos que empiecen por cero por ser en realidad números de dos cifras.

Con estas ideas básicas sale el siguiente código:

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 = 939658 ;
  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 ][ tam ] == 0 && Npermutacion [ i ][ tam ] == 0 ) || ( Npermutacion [ i ][ 0 ] == 0 && Npermutacion [ i ][ 0 ] == 0 ) )
  27.         continue ;
  28.       else if ( 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. }

Ha sido rapidito y queda a expensas de mejoras, pero me quería adelantar por una vez.

Se puede comprobar que 126000 lo da como no vampiro, pero si desactivas el if de los números que termina en cero, dará lógicamente que sí lo es. Pero como no es vampiro no lo da como tal.

Espero que la originalidad de la idea sea merecedora de los tan apreciados usuarios.

A la espera de las críticas y/o correcciones quedo.

P.D: amchacon no me he olvidado de tí. A ver si mañana mismo te mando un mp.

¡¡¡Saluditos!!!



Puntitos Puntitos
Me gusta me gusta

Última edición por leosansan; 28/11/2014 a las 16:56
  #41 (permalink)  
Antiguo 28/11/2014, 18: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.

Bien, bien leosan
Aún no me lo he mirado con profundidad pero remitiéndome al primer post que puse:
Cita:
Iniciado por Pantalaimon
propongo crear este hilo donde iré proponiendo diferentes retos a resolver en C sin usar iteración (bucles for, while, do while) ni goto, claro.
aún debes corregir ciertas cosas para que sea válido!

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #42 (permalink)  
Antiguo 29/11/2014, 03:37
 
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
¡¡¡ A petarla ¡¡¡

Reconozco que la primera idea ha sido la de usar a la de usar bruta, pero me he contenido y he preferido dejarlo para otra ocasión Así que he optado por un camino más rebuscado, sencillamente a lo que a primera vista invita el reto.

Y es que si un número es de, por ejemplo seis cifras, tan sólo hay un número de variaciones de 6^3 variaciones tomadas las cifras de tres en tres, lo que da tan solo 216 casos posibles. Una vez obtenidas tan solo hay que ir multiplicándolas entre sí a ver si sale el número original,

Las dificultades inherentes ha sido obtener las variaciones y "bambolear" el array de cifras de una función a otra.

Cumple los cometidos encomendados, no valen dos grupos de cifras terminados ambos en cero y filtro aquellos que empiecen por cero por ser en realidad números de dos cifras.

Con estas ideas básicas sale el siguiente código:

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 = 939658 ;
  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 ][ tam ] == 0 && Npermutacion [ i ][ tam ] == 0 ) || ( Npermutacion [ i ][ 0 ] == 0 && Npermutacion [ i ][ 0 ] == 0 ) )
  27.         continue ;
  28.       else if ( 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. }

Ha sido rapidito y queda a expensas de mejoras, pero me quería adelantar por una vez.

Se puede comprobar que 126000 lo da como no vampiro, pero si desactivas el if de los números que termina en cero, dará lógicamente que sí lo es. Pero como no es vampiro no lo da como tal.

Espero que la originalidad de la idea sea merecedora de los tan apreciados usuarios.

A la espera de las críticas y/o correcciones quedo.

P.D: amchacon no me he olvidado de tí. A ver si mañana mismo te mando un mp.
Vaya código tan grande te ha salido Leo.

El uso de variables estáticas no me convence mucho, y bueno los bucles habría que quitarlos tramposo ;)

Cita:
Iniciado por Pantaláimon Ver Mensaje
Edit: NOTA IMPORTANTE: la firma para noRep en C++ puede tener la variante
Código C++:
Ver original
  1. std::string noRep(const std::string&);
. Antes me he colado y he puesto la firma pasando el parámetro por valor.

Un saludo!
Tal y como está definido es irresoluble de forma recursiva, no hay ninguna variable con la que puedes jugar ahí.

Si le quitaras el const si se podría hacer algo...
  #43 (permalink)  
Antiguo 29/11/2014, 04:09
 
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 amchacon
Tal y como está definido es irresoluble de forma recursiva, no hay ninguna variable con la que puedes jugar ahí.

Si le quitaras el const si se podría hacer algo...
Yo lo tengo implementado así y no he tenido ningún problema. Hay que entender que el problema no se trata de modificar el origen, sino, crear una nueva cadena sin caracteres repetidos:
Cita:
Iniciado por Pantalaimon
dada una cadena de caracteres, construya otra sin repetición de caracteres consecutivos.
__________________
github.com/xgbuils | npm/xgbuils
  #44 (permalink)  
Antiguo 29/11/2014, 04:46
 
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
Yo lo tengo implementado así y no he tenido ningún problema. Hay que entender que el problema no se trata de modificar el origen, sino, crear una nueva cadena sin caracteres repetidos:
Ya, pero porque tendrás una segunda función para hacer la recursión tramposo ¬¬
  #45 (permalink)  
Antiguo 29/11/2014, 05:55
 
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.

Usar una segunda función no es trampa. Pero ya te digo que no la uso. Como ya he dicho, no se trata de modificar la variable que pasas por parámetro, sino devolver uno nuevo en función de la otra.

Como aún no quiero poner mi resultado te doy un ejemplo distinto. Crear una función anadeX que dado un string, a cada caracter le preceda una 'x': "abcd" -> "xaxbxcxd".
Código C++:
Ver original
  1. std::string anadeX(const std::string& str) {
  2.     if (str.empty()) {
  3.         return std::string();
  4.     } else {
  5.         return std::string("x") + str[0] + anadeX(str.substr(1));
  6.     }
  7. }
  8.  
  9. int main (void) {
  10.     std::string arr[] = {
  11.         "",
  12.         "abcde",
  13.         "aab",
  14.         "abb",
  15.         "aa",
  16.         "bb",
  17.         "a",
  18.         "b",
  19.         "abccccfabaddeff"
  20.     };
  21.     int i;
  22.     for (i = 0; i < 9; ++i) {
  23.         std::cout << arr[i] << " -> " << anadeX(arr[i]) << std::endl;
  24.     }
  25.     return 0;
  26. }
¿Ves que no ocurre nada por usar const?

Otra cosa es que tus funciones no puedan aplicarse para ese prototipo de función con const porque usas métodos que modifican la cadena origen. Pero no te preocupes, permito los dos prototipos.

Un saludo.
__________________
github.com/xgbuils | npm/xgbuils
  #46 (permalink)  
Antiguo 29/11/2014, 15:15
Avatar de kspr  
Fecha de Ingreso: agosto-2011
Ubicación: Ecuador
Mensajes: 43
Antigüedad: 12 años, 11 meses
Puntos: 7
Respuesta: Petando la pila. Problemas y retos usando recursividad.

intentare los retos haber si me salen
  #47 (permalink)  
Antiguo 29/11/2014, 15:49
Avatar de kspr  
Fecha de Ingreso: agosto-2011
Ubicación: Ecuador
Mensajes: 43
Antigüedad: 12 años, 11 meses
Puntos: 7
Respuesta: Petando la pila. Problemas y retos usando recursividad.

El primer ejercicio lo intente simulando un pase por referencia,

Código C:
Ver original
  1. #include <stdio.h>
  2.  
  3. /* más codigo si hace falta */
  4.  
  5. void contarNegativos(int arr[], int n, int *cantidad)
  6. {
  7.     if(n > 0)
  8.     {
  9.         if(arr[n-1] < 0)
  10.         *cantidad = *cantidad + 1;
  11.  
  12.         contarNegativos(arr, n-1, cantidad);
  13.     }
  14. }
  15.  
  16. int main (void)
  17. {
  18.     int arr[] = {-1, -4, -3, 2, 1, 8, 0, 1};
  19.     int n = sizeof arr / sizeof *arr;
  20.     int cantidad = 0;
  21.  
  22.     /* calcular cantidad de negativos */
  23.     contarNegativos(arr, n, &cantidad);
  24.  
  25.     /* mostrar cantidad de negativos */
  26.     printf("\ntotal: %d\n", cantidad);
  27.  
  28.     return 0;
  29. }


solucion 2: http://ideone.com/MZsKX1

Última edición por kspr; 29/11/2014 a las 23:36
  #48 (permalink)  
Antiguo 30/11/2014, 01:00
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,

Creo que voy a hacer un poco de trampa, me voy a saltar algunos ejercicios, primero porque las soluciones expuestas son difíciles de mejorar. Segundo porque las combinatorias y el tema en sí ha sido algo 'recursivo' (no pun intended) para mí en foros del web, por ejemplo, 1, 2, 3; y por eso ya lo he tratado varias veces.

Así que mejor solamente expongo mis soluciones a los problemas actuales,

Problema #1
Cita:
Iniciado por Pantaláimon Ver Mensaje
... Como restricción de diseño, decir que dentro de noRep no se reservará memoria dinámica tal que luego tenga que ser liberada fuera de la función. Vaya, que en caso de que queráis reservar memoria dinamicamente para destino, hacedlo fuera de la función. ...
No estoy completamente seguro, pero voy a suponer que fuera de la función significa en el main, por lo menos en el caso de C, de otra forma solo conozco dos soluciones, una variable global o un memory leak. Así que en mi caso preferí dejarlo en el main.
Código C:
Ver original
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. char* norep(char* dst, const char* src) {
  6.     if (*src == 0x0) {
  7.         *(dst + 1) = *src;
  8.     } else {
  9.         if (*src == *dst) {
  10.             norep(dst, src + 1);
  11.         } else {
  12.             *(dst + 1) = *src;
  13.             norep(dst + 1, src + 1);
  14.         }
  15.     }
  16.     return dst;
  17. }
  18.  
  19. char* noRep(char* destino, const char* origen) {
  20.     *destino = *origen;
  21.     return norep(destino, origen);
  22. }
  23.  
  24. int main(int argc, char** argv) {
  25.     char data[] = "abccccfabaddeff";
  26.     char* destino = calloc(strlen(data) + 1, sizeof(char));
  27.     printf("%s\n", noRep(destino, data));
  28.     free(destino);
  29.     return (EXIT_SUCCESS);
  30. }
Problema #2
Cita:
Iniciado por Pantaláimon Ver Mensaje
... el conjunto de dígitos de los dos colmillos ha de ser el mismo conjunto que los digitos del número vampiro. ...
Esa parte no la entendí muy bien, la parte de los conjuntos y multiconjuntos, y las permutaciones, así que básicamente permuté todas las posibilidades sin orden de los números. Por este concepto en algunos casos duplica algunos cálculos dependiendo del número, por ejemplo 611161, en ese caso al permutar el 1 con los otros 1 realiza operaciones duplicadas, pero siguiendo la función de las permutaciones 6! pues es lo que hay :D. El problema, posiblemente, es que para evitarlo tendría que guardar en una lista todas las operaciones anteriores o la lógica sería demasiado compleja.

Código C:
Ver original
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int fact(const int i) {
  6.     return i == 0 ? 1 : i * fact(i - 1);
  7. }
  8.  
  9. int count(const int value, const int i) {
  10.     return value == 0 ? i : count(value / 10, i + 1);
  11. }
  12.  
  13. void split(const int value, int dst[], const int i) {
  14.     if (value > 0 && i >= 0) {
  15.         dst[i] = value % 10;
  16.         split(value / 10, dst, i - 1);
  17.     }
  18. }
  19.  
  20. int join(int value, const int src[], const int end, const int begin, const int dec) {
  21.     if (end >= begin) {
  22.         value += src[end] * dec;
  23.         return join(value, src, end - 1, begin, dec * 10);
  24.     }
  25.     return value;
  26. }
  27.  
  28. void swap(int dst[], const int a, const int b) {
  29.     int t = dst[b]; dst[b] = dst[a]; dst[a] = t;
  30. }
  31.  
  32. int esvampiro_row(const int value, int src[], const int digits, const int i, const int row) {
  33.     int value1 = join(0, src, (digits / 2) - 1, 0, 1);
  34.     int value2 = join(0, src, digits - 1, (digits / 2), 1);
  35.  
  36.     printf("%.4d : %.3d x %.3d\n", row, value1, value2);
  37.  
  38.     if (value1 * value2 == value && !(value1 % 10 == 0 && value2 % 10 == 0)) {
  39.         return 1;
  40.     } else {
  41.         if (i < digits - 1) {
  42.             swap(src, i, i + 1);
  43.             return esvampiro_row(value, src, digits, i + 1, row + 1);
  44.         }
  45.     }
  46.  
  47.     return 0;
  48. }
  49.  
  50. int esvampiro(const int value, int src[], const int digits, const int i, const int row, const int f, const int visited) {
  51.     int tmp[digits];
  52.  
  53.     memcpy(tmp, src, digits * sizeof(int));
  54.     if (!visited && esvampiro_row(value, tmp, digits, 0, row + 1)) {
  55.         return 1;
  56.     } else {
  57.         if (i > 1) {
  58.             swap(src, i, i - 1);
  59.             return esvampiro(value, src, digits, i - 1, row + digits, f, 0);
  60.         } else {
  61.             if (row < f) {
  62.                 return esvampiro(value, src, digits, digits - 1, row, f, 1);
  63.             }
  64.         }
  65.     }
  66.  
  67.     return 0;
  68. }
  69.  
  70. int esVampiro(int num) {
  71.     int digits = count(num, 0);
  72.     int n[digits];
  73.  
  74.     split(num, n, digits - 1);
  75.  
  76.     if (digits % 2 == 0) {
  77.         int f = fact(digits);
  78.         return esvampiro(num, n, digits, digits - 1, 0, f, 0);
  79.     }
  80.  
  81.     return 0;
  82. }
  83.  
  84. int main(int argc, char** argv) {
  85.     printf("%d\n", esVampiro(1395));
  86.     return (EXIT_SUCCESS);
  87. }
Como siempre, los algoritmos no están optimizados ni especializados, y posiblemente se me haya pasado mas de algún error, y como ya es la una de la mañana por aquí, pues básicamente ese es el concepto de mis propuestas.

Saludos,
  #49 (permalink)  
Antiguo 30/11/2014, 02:39
 
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 Hackman
Problema #1

Cita:
Iniciado por Pantaláimon
... Como restricción de diseño, decir que dentro de noRep no se reservará memoria dinámica tal que luego tenga que ser liberada fuera de la función. Vaya, que en caso de que queráis reservar memoria dinamicamente para destino, hacedlo fuera de la función. ...
No estoy completamente seguro, pero voy a suponer que fuera de la función significa en el main, por lo menos en el caso de C, de otra forma solo conozco dos soluciones, una variable global o un memory leak. Así que en mi caso preferí dejarlo en el main.
Exacto, quería decir fuera de la función que es el ejercicio. En resumen, quería asegurarme que diseñarais la función con el mismo patrón que otras funciones de C como strcpy, memcpy, las cuales no reservan memoria dinámica.

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #50 (permalink)  
Antiguo 01/12/2014, 04:15
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
Bien, bien leosan
Aún no me lo he mirado con profundidad pero remitiéndome al primer post que puse:

aún debes corregir ciertas cosas para que sea válido!

Un saludo!
Buuueno, pero que conste que es de lo más efectivo el código anterior.

Pero las reglas son las reglas y las has puesto tú aunque un poco de manga ancha no vendría mal.

Para que no se diga: sin un for ni do ni while ni goto. Tutti con funciones recursivas, y son unas cuantas para que no se diga.

La idea es usar la fuerza bruta, pero de forma proporcional.

* Obtengo el tamaño del número, vamos sus dígitos.

* Saco los valores mínimo y máxima que pueden alcanzar los dos números que multiplicados nos darán el número original.

* Pruebo los posibles productos a partir de los valores anteriores que nos puedan dar el número.

* Obtenido cualquier posibilidad, compruebo que los dígitos que componen los números parciales se corresponden con el número original: si es sí, O.k, es Vampiro y si no, no lo es.

Sencillito, ¿ verdad ? y todo usando una "nomenclatura" que puedan seguir los usuarios menos avanzados. De ahí que me haya molestado en poner nombres muy descriptivos a las variables....eferion estará muy contento por ello.

¡¡¡ Ahí va el "pedazo" de código:

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 = 939658 ; /** 939658 = 953 * 986 **/
  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 , flag = 0  ;
  68.   if ( num_1 < n_maximo - 1 && num_0 == n_maximo )
  69.     num_0 = n_minimo , num_1 = numero / n_maximo  ;
  70.   if ( num_0 == n_maximo - 1 )
  71.     return printf ( "\n\n\t::%d NO ES VAMPIRO\n\n"  , numero ) , 0 ;
  72.   if ( num_0 < n_maximo ){
  73.     num_1 = numero / num_0  ;
  74.     if ( num_0 * num_1 == numero  ) {
  75.     inicializar_digitosNumero ( digitosNumero , 0  ) ;
  76.     DigitosNumero ( digitosNumero , numero , 0 ) ;
  77.     if ( num_0 * num_1 == numero  ) {
  78.       DigitosNumero ( digitosNumero , num_0 , 1 ) ;
  79.       DigitosNumero ( digitosNumero , num_1 , 1 ) ;
  80.       if ( ComprobarDigitos ( digitosNumero , 0 , 0 ) == 10 && ( num_0 % 10 != 0 ||  num_1 % 10 != 0 ) )
  81.         return printf ( "\n\n\tES VAMPIRO: %d = %d * %d\n\n" , numero , num_1 , num_0 ) , 1 ;
  82.     }
  83.   }
  84.   return  probar ( numero , num_1  , 1 + num_0 , n_minimo , n_maximo , digitos , digitosNumero )  ;
  85.  }
  86. }

Lo he testeado un ratito así que espero no tenga bugs y si no ya me lo dirán.....

Por cierto, dar la bienvenida a kspr, HackmanC y amchacon por su incorporación a los retos.

Notita::1:: HaxkmanC no me da como vampiro el "939658".

Notita::2::
Cita:
amchcon:: Vaya código tan grande te ha salido Leo.

El uso de variables estáticas no me convence mucho, y bueno los bucles habría que quitarlos tramposo ;)
Pues el código es increiblemente eficiente comparado con los otros propuestos. Pero ya ves que me he aplicado y pongo ahora uno "sin trampas", campeón. Yo por lo menos me he lanzado a por el difícil, je,je.

Por cierto, paso una breve lista de números vampiros:

Código C++:
Ver original
  1. 1395=15*93
  2. 1260=21*60
  3. 1827=21*87
  4. 2187=27*81
  5. 1530=30*51
  6. 1435=35*41
  7. 6880=80*86
  8. 108135=135*801
  9. 129640=140*926
  10. 118440=141*840
  11. 136948=146*938
  12. 105750=150*705
  13. 139500=150*930
  14. 115672=152*761
  15. 125248=152*824
  16. 146952=156*942
  17. 110758=158*701
  18. 116725=161*725
  19. 156915=165*951
  20. 117067=167*701
  21. 162976=176*926
  22. 129775=179*725
  23. 102510=201*510
  24. 120600=201*600
  25. 126027=201*627
  26. 180297=201*897
  27. 105264=204*516
  28. 125460=204*615
  29. 105210=210*501
  30. 126000=210*600
  31. 182700=210*870
  32. 190260=210*906
  33. 192150=210*915
  34. 136525=215*635
  35. 186624=216*864
  36. 211896=216*981
  37. 172822=221*782
  38. 180225=225*801
  39. 182250=225*810
  40. 123354=231*534
  41. 125433=231*543
  42. 135828=231*588
  43. 173250=231*750
  44. 175329=231*759
  45. 156240=240*651
  46. 125460=246*510
  47. 218488=248*881
  48. 229648=248*926
  49. 125500=251*500
  50. 152608=251*608
  51. 215860=251*860
  52. 201852=252*801
  53. 205785=255*807
  54. 104260=260*401
  55. 126846=261*486
  56. 152685=261*585
  57. 156289=269*581
  58. 226498=269*842
  59. 218700=270*810
  60. 197725=275*719
  61. 226872=276*822
  62. 124483=281*443
  63. 182650=281*650
  64. 262984=284*926
  65. 251896=296*851
  66. 150300=300*501
  67. 153000=300*510
  68. 131242=311*422
  69. 133245=315*423
  70. 134725=317*425
  71. 146137=317*461
  72. 296320=320*926
  73. 217638=321*678
  74. 312975=321*975
  75. 132430=323*410
  76. 216733=323*671
  77. 260338=323*806
  78. 193257=327*591
  79. 319536=336*951
  80. 233896=338*692
  81. 213466=341*626
  82. 329346=342*963
  83. 140350=350*401
  84. 143500=350*410
  85. 253750=350*725
  86. 135837=351*387
  87. 145314=351*414
  88. 315900=351*900
  89. 319059=351*909
  90. 153436=356*431
  91. 329656=356*926
  92. 336960=360*936
  93. 346968=366*948
  94. 361989=369*981
  95. 174370=371*470
  96. 369189=381*969
  97. 371893=383*971
  98. 338296=392*863
  99. 362992=392*926
  100. 193945=395*491
  101. 163944=396*414
  102. 284760=420*678
  103. 245182=422*581
  104. 304717=431*707
  105. 312475=431*725
  106. 378418=431*878
  107. 384912=432*891
  108. 378450=435*870
  109. 263074=437*602
  110. 404968=446*908
  111. 241564=461*524
  112. 429664=464*926
  113. 386415=465*831
  114. 286416=468*612
  115. 416988=468*891
  116. 254740=470*542
  117. 378400=473*800
  118. 447916=476*941
  119. 428980=482*890
  120. 284598=489*582
  121. 414895=491*845
  122. 326452=524*623
  123. 336550=530*635
  124. 341653=533*641
  125. 365638=533*686
  126. 315594=534*591
  127. 456840=540*846
  128. 489955=545*899
  129. 458640=546*840
  130. 489159=549*891
  131. 536539=563*953
  132. 475380=570*834
  133. 529672=572*926
  134. 368550=585*630
  135. 559188=588*951
  136. 498550=590*845
  137. 392566=593*662
  138. 486720=624*780
  139. 538650=630*855
  140. 416650=641*650
  141. 457600=650*704
  142. 568750=650*875
  143. 638950=650*983
  144. 567648=657*864
  145. 629680=680*926
  146. 516879=681*759
  147. 673920=720*936
  148. 679500=750*906
  149. 736695=765*963
  150. 769792=776*992
  151. 729688=788*926
  152. 688000=800*860
  153. 794088=807*984
  154. 789525=825*957
  155. 738468=843*876
  156. 792585=855*927
  157. 815958=858*951
  158. 789250=875*902
  159. 809919=891*909
  160. 841995=891*945
  161. 809964=894*906
  162. 829696=896*926
  163. 939658=953*986

¡¡¡Saluditos!!!



Puntitos Puntitos
Me gusta me gusta
[/QUOTE]
  #51 (permalink)  
Antiguo 01/12/2014, 04:30
 
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.

Y digo yo... ¿No sería mejor definir una serie de criterios para evaluar los códigos (tiempo de ejecución, consumo de memoria, ... ) y después sacar una tabla con los resultados??

Hacer uso de un árbitro que monitorice la ejecución del algoritmo para sacar una clasificación.

No se, creo que daría algo más de emoción a la propuesta.

Se que hay varias webs que tienen este sistema... pero la gente se ha dedicado a poner todos los posibles resultados a pelo en el código y sus tiempos de ejecución rozan el 0... razón por la cual no es divertido participar. Sin embargo aquí se ven las implementaciones de cada uno y se les va a poder poner una nota objetiva.

Cierto es que el título original del hilo podría perder algo de significado.

No se, ya me contaréis vuestra opinión.
  #52 (permalink)  
Antiguo 01/12/2014, 06:39
 
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!

La idea principal era hacer un post para practicar recursividad, a medida que he ido poniendo retos me he decantado por poner 1 problema sencillo y otro un poco más complicado cada semana, pero aplicando siempre recursividad. Sin embargo, si queréis iteración requerirá más tiempo por mi parte a la hora de inventarme los problemas. Aplicando sólo recursividad tenia la gracia que con problemas no tan complicados, al no estar acostumbrados a usar recursividad, eran más difíciles de realizar.

Me gusta mucho la idea de una web que clasifique los resultados, pero no sé nada sobre estos temas. ¿Cual recomiendas eferion? Esto me ha recordado a la página http://uva.onlinejudge.org/ donde hay una buena colección de problemas y que los clasifica según su tiempo de ejecución. Pero allí lo que pasa es que hay tanto crack suelto que acaba frustrándote ver que no te acercas ni de coña a los puestos más altos. A parte de que como no se pueden ver los códigos de los otros, no puedes aprender de ello. A cuenta de esto, otra opción que se me ocurre sería coger problemas de allí para la competición. Y si eso, traducir los problemas al castellano para que más gente se anime a participar.

Sólo doy ideas, si tenéis otras, comentad.
__________________
github.com/xgbuils | npm/xgbuils
  #53 (permalink)  
Antiguo 01/12/2014, 06:44
 
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.

Yo no pensaba, de momento, en una web... sino en tener una aplicación tipo árbitro y que hubiese alguien encargado de lanzar el código propuesto por cada uno de los que se apunten.

La ventaja de usar un árbitro común es que todos los códigos corren en la misma plataforma, con los mismos recursos, se han compilado con la misma configuración, etc. Luego así ya si que existe un mecanismo que permite comparar los diferentes algoritmos.

Yo tengo un prototipo un poco básico de árbitro... aún no es capaz de compilar pero si toma nota del tiempo de ejecución y del uso de memoria. Además permite lanzar tests aleatorios al ejecutable a testear y verificar que la respuesta sea correcta.

No he tenido tiempo ni de desarrollarlo en exceso ni tampoco de pulir su funcionamiento, pero todo es cuestión de ponerse.
  #54 (permalink)  
Antiguo 01/12/2014, 11:06
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
... Notita::1:: HaxkmanC no me da como vampiro el "939658". ...
Buena observación leosansan, aunque no estoy completamente seguro, posiblemente yo no entendí bien el problema a resolver, así dejaré que sea Pantaláimon, por ser el arbitro, verifique esa información.

Mi forma de comprobar que funcionara fue la siguiente, primero hice la prueba con el número 123456, de esa forma puedo comprobar que realmente se estén haciendo todas las permutaciones posibles, si uso dígitos repetidos, como por ejemplo, 121212 no lo podía comprobar. Como en mi algoritmo imprime todas las multiplicaciones que realiza, extraje en una hoja de Microsoft Excel lo que imprime en pantalla mi programa, con un par de formulas concatené los números que se están multiplicando y lo metí en una base de datos (para mi era lo más fácil). En la base de datos hice una consulta que me devolviera la cantidad de registros distintos (distinct) y el resultado fue 720, todo usando el tipo de datos char para que no haya ajustes con los dígitos 0 u otros.

Es decir, con eso comprobé que realmente fueran 720 variaciones diferentes del número 123456, que según la formula de las permutaciones sin orden es de 6! = 720. Después, si es otro número no importa porque ya comprobé que las permutaciones fueran exactas, el hecho que el número sea otro no importaría en cualquier caso puesto que no se basa en el número para permutar, sino en las posiciones del vector de integer (cambia las mismas posiciones la misma cantidad de veces, mientras no encuentre el vampiro).

Por ese motivo es que no puedo estar seguro, según mi criterio el número 939658 no es vampiro, pero puede ser que yo no haya comprendido bien el problema o que realmente tenga algún error.

Siempre te agradezco mucho la observación, así lo voy a verificar.

Cita:
Iniciado por eferion Ver Mensaje
... La ventaja de usar un árbitro común es que todos los códigos corren en la misma plataforma, con los mismos recursos, se han compilado con la misma configuración, etc. Luego así ya si que existe un mecanismo que permite comparar los diferentes algoritmos. ....
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. Pero si se deciden a optimizar, con gusto participo, realmente es una parte de la programación que me agrada bastante.

Pero primero voy a corregir el problema que me reportó leosansan.

Saludos,

Última edición por HackmanC; 01/12/2014 a las 11:49 Razón: agregar char
  #55 (permalink)  
Antiguo 01/12/2014, 12: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.

Hola Hackman,

939658 es un número vampiro porque:
1) es el producto de 953 y 986.
2) ni 953 ni 986 acaban en 0.
3) El multiconjunto de dígitos de 939658 ({3,5,6,8,9,9}) es el mismo que el multiconjunto de los dígitos 953 y 986 ({3,5,6,8,9,9})

En principio, si permutas los digitos de 939658, en algun momento te saldrá la permutación 953,986, la cual verás que al multiplicarla te da 939658. Alguna cosa se te habrá pasado en algún lugar.

Dejo este código por si queréis hacer tests:
https://github.com/xgbuils/vampire_g...ster/vamp4.cpp
Es un generador de números vampiros muy optimizado que creé hace algún tiempo.

Funciona así:
Unix:
Código BASH:
Ver original
  1. ./programa base minDigitos maxDigitos
Windows:
Código BASH:
Ver original
  1. programa.exe base minDigitos maxDigitos

A nosotros nos interesan los vampiros en base 10, y si queremos por ejemplo, los vampiros de 6 a 8 digitos hay que poner:
Código BASH:
Ver original
  1. ./programa 10 6 8
Cuidado, pues por razones de eficiencia cuando creé este generador de números vampiros, está hecho de tal modo que los genera desordenadamente y puede salir algun vampiro repetido (aquellos vampiros que tengan más de una combinación de colmillos).

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

Hola,

Cita:
Iniciado por Pantaláimon Ver Mensaje
... En principio, si permutas los digitos de 939658, en algun momento te saldrá la permutación 953,986, la cual verás que al multiplicarla te da 939658. Alguna cosa se te habrá pasado en algún lugar.
Gracias por comprobarlo. Es correcto, en el resultado no aparecer ese valor, al parecer mi problema está en que me estoy basando en la fórmula incorrecta, la cantidad de resultados no es el 6!, no estoy generando todas las posibles permutaciones o combinaciones reales. Lo voy a revisar de nuevo y optimizar un poco.

Saludos,
  #57 (permalink)  
Antiguo 01/12/2014, 20:16
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 HackmanC Ver Mensaje
Hola,
Gracias por comprobarlo. Es correcto, en el resultado no aparecer ese valor, al parecer mi problema está en que me estoy basando en la fórmula incorrecta, la cantidad de resultados no es el 6!, no estoy generando todas las posibles permutaciones o combinaciones reales. Lo voy a revisar de nuevo y optimizar un poco.
Saludos,
En realidad no se trata de permutaciones sino de variaciones.

Me explico. Si tienes el número "123456" los dos números que multiplicados darían ese número, con los mismos dígitos, se corresponden con las variaciones tomadas de tres en tres de esos seis dígitos. Y eso da 6^3 = 216 en lugar de 6! = 720. Fíjate que si usas este último caso estarías repitiendo operaciones ya que entre las permutaciones te saldrían: 123 345 y la 345 123 y así sucesivamente, con lo que estarías tomando de más. No está mal pero es menos eficiente porque repites operaciones. En el primer código que usé tomé variaciones y aún así, si se repiten dígitos, se te suela algún que otro caso repetido.

En el segundo fíjate que he hecho uso de los dígitos que aparecen en el número y los que aparecen en los dos factores, cosa que llevo a cabo en la función "DigitosNumero". En ella pongo en un array a "1" los dígitos que aparecen en el número y luego voy restando los que corresponden a los dos factores. Si no hay valores negativos en el array es que se corresponden los multiconjuntos de dígitos del número y el de los factores.

Y respecto al otro tema que abrió eferion opino, y es tan solo una opinión, que tampoco hay que llegar a los extremos de comparar exhaustivamente los códigos propuestos. Soy de la opinión de que "nos ven" muchos usuarios que beben de nuestros conocimientos y el llevar los códigos a la extrema eficiencia nos llevaría a "códigos ofuscados" para la gran mayoría debido al uso, entre otras cosas, que haríamos de operadores a nivel de bits, parte de códigos en ensamblador y otras cosas similares. Por eso me he propuesto usar nombres de variables y funciones que expliciten lo que representen o hagan. Además hay códigos que a lo mejor no son tan eficientes pero si la mar de ingeniosos y eso también cuenta.

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.

Un fuerte saludo a todos y muy contento por las nuevas incorporaciones, así todos vamos aprendiendo, yo al menos sí.

¡¡¡Saluditos!!!

  #58 (permalink)  
Antiguo 02/12/2014, 00:44
 
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
el llevar los códigos a la extrema eficiencia nos llevaría a "códigos ofuscados"
Código C++:
Ver original
  1. int unsigned comb ( unsigned n , unsigned k )  {    
  2.   return ( k > n / 2 ) ?  ( comb (  n , k )  ) : ( k >= 1 ) ?  ( n  * comb (  n - 1 , k - 1 ) / k ) : 1 ;}

Yo podría decirte de varias personas que necesitarían papel y lápiz o depurar el código para entender lo que hace esta función jejejejeje :P
  #59 (permalink)  
Antiguo 02/12/2014, 03:13
 
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.

Ahora no tengo tiempo para responderlo todo pero quiero aclarar este punto:

Cita:
Iniciado por leosansan
En realidad no se trata de permutaciones sino de variaciones.

Me explico. Si tienes el número "123456" los dos números que multiplicados darían ese número, con los mismos dígitos, se corresponden con las variaciones tomadas de tres en tres de esos seis dígitos. Y eso da 6^3 = 216 en lugar de 6! = 720. Fíjate que si usas este último caso estarías repitiendo operaciones ya que entre las permutaciones te saldrían: 123 345 y la 345 123 y así sucesivamente, con lo que estarías tomando de más. No está mal pero es menos eficiente porque repites operaciones. En el primer código que usé tomé variaciones y aún así, si se repiten dígitos, se te suela algún que otro caso repetido.
Permutaciones de 123:
Código :
Ver original
  1. 123, 132, 213, 231, 312, 321
En total son 3!

Variaciones con repetición en grupos de 2 de 1234:
Código :
Ver original
  1. 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44.
En total son 4^2

http://www.vitutor.com/pro/1/a_r.html

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #60 (permalink)  
Antiguo 02/12/2014, 03: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 eferion Ver Mensaje
Código C++:
Ver original
  1. int unsigned comb ( unsigned n , unsigned k )  {    
  2.   return ( k > n / 2 ) ?  ( comb (  n , k )  ) : ( k >= 1 ) ?  ( n  * comb (  n - 1 , k - 1 ) / k ) : 1 ;}

Yo podría decirte de varias personas que necesitarían papel y lápiz o depurar el código para entender lo que hace esta función jejejejeje :P
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......

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.

¡¡¡Saluditos!!!


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