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. Dado que veo que el tema de recursividad está gustando bastante propongo crear este hilo donde iré proponiendo diferentes retos a resolver en C ...

  #1 (permalink)  
Antiguo 14/11/2014, 12:31
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 17 años, 9 meses
Puntos: 32
Petando la pila. Problemas y retos usando recursividad.

Buenas.

Dado que veo que el tema de recursividad está gustando bastante 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. Se pueden usar tantas funciones como se quieran.

De momento iré sacando los problemas de un pdf que tengo de ejercicios en Haskell y los iré adaptando a C. Pues venga, ¡Vamos al grano y presento los dos primeros retos!

1) Escriba una función contarNegativos que cuente cuantos números negativos existen en una lista
Ejemplo: dado el array {1, 4, -3, 2, -1, -8, 0, 1} debe devolver 3:

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

2) Escriba una función diag que tenga una lista de caracteres como parámetro y que dé como resultado los caracteres
en una diagonal.
Cadena:
Código C:
Ver original
  1. "abcde"
Resultado:
Código C:
Ver original
  1. a
  2.  b
  3.   c
  4.    d
  5.     e
Aquí el código de plantilla:
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. char* diag(char* cadena, char* resultado) {
  8.     /* Escribir código */
  9.     resultado[0] = '\0';
  10.     return resultado;
  11. }
  12.  
  13. int main (void) {
  14.     char cadena [] = "abcde";
  15.     int n = strlen(cadena);
  16.  
  17.     char* resultado = malloc(n * n + 1); /* doy mas espacio del necesario */
  18.  
  19.     // a partir de la cadena de caracteres retornar la nueva que tenga los caracteres en diagonal
  20.     resultado = diag(cadena, resultado);
  21.  
  22.     //mostrar resultado
  23.     puts(resultado);
  24.  
  25.     free(resultado);
  26.     return 0;
  27. }

Ya se irá complicando la cosa

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #2 (permalink)  
Antiguo 14/11/2014, 13:33
 
Fecha de Ingreso: octubre-2013
Mensajes: 44
Antigüedad: 10 años, 5 meses
Puntos: 5
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Una forma muy divertida de dominar la recursividad

El primer problema es bastante sencillito, aquí va mi soución:

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

Respecto al segundo, pues no tengo ni idea. ¿De verdad se puede implementar con dos parámetros sin pasarle también el tamaño de la cadena original?

Saludos
  #3 (permalink)  
Antiguo 14/11/2014, 13:39
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 5 meses
Puntos: 13
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Excelente iniciativa Pantaláimon me gusta mucho este tipo de retos

Solución al primer reto:

Código C++:
Ver original
  1. #include <stdio.h>
  2.  
  3. int contarNegativos(int arr[], int n)
  4. {
  5.     if (n == 0) return(0);
  6.     return (arr[n - 1] < 0 ? 1 : 0) + contarNegativos(arr, n - 1);
  7. }
  8.  
  9. int main (void)
  10. {
  11.     int arr[] = {1, 4, -3, 2, -1, -8, 0, 1};
  12.     int n = sizeof arr / sizeof *arr;
  13.  
  14.     int cantidad = contarNegativos(arr, n);
  15.     printf("%d\n", cantidad);
  16.  
  17.     return(0);
  18. }

Segundo:

Código C++:
Ver original
  1. #include <stdio.h>
  2.  
  3. char diag(char *str, int n)
  4. {
  5.     if (str[n] == '\0') return(0);
  6.     printf( "%*c\n", n + 1, str[n]);
  7.     return diag(str, n + 1);
  8. }
  9.  
  10. int main (void)
  11. {
  12.     char cadena [] = "abcde";
  13.     diag (cadena, 0);
  14.  
  15.     return(0);
  16. }

Saludos y a la espera de mas retos

Última edición por kutcher; 14/11/2014 a las 15:07
  #4 (permalink)  
Antiguo 14/11/2014, 16:19
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 11 años, 10 meses
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Porfi, uno o dos días es lo que necesito porque el disco duro ha "petado".

Desde que esté operativo me pongo a ello.

Saluditos de León.
  #5 (permalink)  
Antiguo 14/11/2014, 18:07
Avatar de vangodp  
Fecha de Ingreso: octubre-2013
Mensajes: 934
Antigüedad: 10 años, 6 meses
Puntos: 38
Respuesta: Petando la pila. Problemas y retos usando recursividad.

ok... acepto el reto XD
Ni voy a mirar los otros posts hasta que tenga echo el código.
Pero no tengo mucha exp asi que hare como pueda jaja.
  #6 (permalink)  
Antiguo 14/11/2014, 20:24
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 6 meses
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

La propuesta parece interesante, ya veremos como acaba

ejercicio 1:

Código C++:
Ver original
  1. #include <stdio.h>
  2.  
  3. int contarNegativos(int arr[], int n)
  4. {
  5.   if ( n > 0 )
  6.     return (*arr < 0) + contarNegativos( ++arr, n-1 );
  7.   return 0;
  8. }
  9.  
  10. int main (void)
  11. {
  12.   int arr[] = {1, 4, -3, 2, -1, -8, 0, 1};
  13.   int n = sizeof arr / sizeof *arr;
  14.  
  15.   /* calcular cantidad de negativos */
  16.   int cantidad = contarNegativos(arr, n);
  17.   /* mostrar cantidad de negativos */
  18.   printf("%d\n", cantidad);
  19.   return 0;
  20. }

ejercicio 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. char* diag(char* cadena, char* resultado)
  8. {
  9.   if (*cadena)
  10.   {
  11.     int espacio = *resultado + 1;
  12.     sprintf( resultado, "%*c\n%c", espacio, *cadena, espacio );
  13.     diag( ++cadena, resultado + espacio + 1 );
  14.   }
  15.   else
  16.     *resultado = 0;
  17.   return resultado;
  18. }
  19.  
  20. int main (void) {
  21.     char cadena [] = "abcde";
  22.     int n = strlen(cadena);
  23.  
  24.     char* resultado = (char*)calloc(n * n + 1, sizeof(char)); /* doy mas espacio del necesario */
  25.  
  26.     // a partir de la cadena de caracteres retornar la nueva que tenga los caracteres en diagonal
  27.     resultado = diag(cadena, resultado);
  28.  
  29.     //mostrar resultado
  30.     puts(resultado);
  31.  
  32.     free(resultado);
  33.     return 0;
  34. }

La única licencia que me he permitido es cambiar el malloc por calloc en el segundo ejercicio. Escribir de forma recursiva en un buffer sin inicializar no me parece buena idea.
  #7 (permalink)  
Antiguo 15/11/2014, 16:29
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 17 años, 9 meses
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por eferion Ver Mensaje
La propuesta parece interesante, ya veremos como acaba
La única licencia que me he permitido es cambiar el malloc por calloc en el segundo ejercicio. Escribir de forma recursiva en un buffer sin inicializar no me parece buena idea.
Cierto, me parece conveniente. Gracias, voy a editarlo.

kutcher, el segundo problema trataría de escribir el resultado en una variable y no enviarlo directamente a la salida estándar.

Edit: vaya no puedo editar el primer post pero mejor la opción de usar calloc como dice eferion.
Saludos!!
__________________
github.com/xgbuils | npm/xgbuils

Última edición por Pantaláimon; 15/11/2014 a las 16:34
  #8 (permalink)  
Antiguo 17/11/2014, 13:53
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 5 meses
Puntos: 13
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por Pantaláimon Ver Mensaje
kutcher, el segundo problema trataría de escribir el resultado en una variable y no enviarlo directamente a la salida estándar.
xD es verdad, entonces dejo otra solución algo parecida a la de eferion pero usando snprintf:

Código C++:
Ver original
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. char* diag(char* s, char* resultado)
  6. {
  7.     static int i = 0, j = 0;
  8.     if (*s)
  9.     {
  10.         j += snprintf (resultado + j,  26 - j, "%*c\n", ++i, *s);
  11.         diag (++s, resultado);
  12.     }
  13.     return resultado;
  14. }
  15.  
  16. int main (void)
  17. {
  18.     char cadena [] = "abcde";
  19.     int n = strlen(cadena);
  20.  
  21.     char* resultado = (char*)calloc(n * n + 1, sizeof(char));
  22.     resultado = diag(cadena, resultado);
  23.     puts(resultado);
  24.  
  25.     free(resultado);
  26.     return 0;
  27. }

Saludos y que siga esto no pude pasar por aquí estos últimos días ya que estaba algo ocupado
  #9 (permalink)  
Antiguo 17/11/2014, 14:27
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 6 meses
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por kutcher Ver Mensaje
xD es verdad, entonces dejo otra solución algo parecida a la de eferion pero usando snprintf:
El problema que tiene tu función es que, debido a las variables globales, es de un solo uso. Si la intentas usar más de una vez en la ejecución de un programa vas a tener problemas.

Tienes que intentar solucionar ese problema. Forma parte del reto ;)
  #10 (permalink)  
Antiguo 17/11/2014, 17:27
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 5 meses
Puntos: 13
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por eferion Ver Mensaje
El problema que tiene tu función es que, debido a las variables globales, es de un solo uso. Si la intentas usar más de una vez en la ejecución de un programa vas a tener problemas.

Tienes que intentar solucionar ese problema. Forma parte del reto ;)
Ya veo, modifique la función pero me he permitido agregar un parámetro mas a esta, espero que esto no sea un inconveniente :

Código C++:
Ver original
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5. char* diag(char* s, char* resultado, int i)
  6. {
  7.     if (*s)
  8.     {
  9.         int j = 0;
  10.         j = snprintf (resultado, i + 2, "%*c\n", i, *s);
  11.         diag (++s, resultado + j, ++i);
  12.     }
  13.     return resultado;
  14. }
  15.  
  16. int main (void)
  17. {
  18.     char cadena [] = "abcde";
  19.     int n = strlen(cadena);
  20.  
  21.     char* resultado = (char*)calloc(n * n + 1, sizeof(char));
  22.     resultado = diag(cadena, resultado, 1);
  23.     puts(resultado);
  24.  
  25.     free(resultado);
  26.     return 0;
  27. }

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

En el primer post comenté que no había problema en usar tantas funciones como se quisieran. Incluso dejé un comentario en las plantillas para dejarlo claro:
Código Javascript:
Ver original
  1. /* más codigo si hace falta */


Así que tu código podría quedar así:
Código Javascript:
Ver original
  1. char* auxdiag(char* s, char* resultado, int i)
  2. {
  3.     if (*s)
  4.     {
  5.         int j = 0;
  6.         j = snprintf (resultado, i + 2, "%*c\n", i, *s);
  7.         diag (++s, resultado + j, ++i);
  8.     }
  9.     return resultado;
  10. }
  11.  
  12. char* diag(char* s, char* resultado) {
  13.     return auxdiag(cadena, resultado, 1);
  14. }
  15.  
  16. int main (void)
  17. {
  18.     char cadena [] = "abcde";
  19.     int n = strlen(cadena);
  20.  
  21.     char* resultado = (char*)calloc(n * n + 1, sizeof(char));
  22.     resultado = diag(cadena, resultado);
  23.     puts(resultado);
  24.  
  25.     free(resultado);
  26.     return 0;
  27. }

¿leosan, vangodp, al final no os animáis?

Creo que la idea será ir poniendo dos problemas por semana. Así que el viernes doy las soluciones que tenía yo para estos problemas y propongo dos más.

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

Entonces hay que esperar hasta el viernes para tener nuevos retos ???
  #13 (permalink)  
Antiguo 18/11/2014, 11:23
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 17 años, 9 meses
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por eferion Ver Mensaje
Entonces hay que esperar hasta el viernes para tener nuevos retos ???
Venga va, uno sencillo para ir abriendo boca.

Crear una función la potencia que calcule la potencia entera no-negativa de un número a. Esta es la firma de la función:
Código C:
Ver original
  1. double potencia(double a, unsigned n);

¡Sed imaginativos!
__________________
github.com/xgbuils | npm/xgbuils
  #14 (permalink)  
Antiguo 18/11/2014, 12:29
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 11 años, 10 meses
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por Pantaláimon Ver Mensaje
Venga va, uno sencillo para ir abriendo boca.

Crear una función la potencia que calcule la potencia entera no-negativa de un número a. Esta es la firma de la función:
Código C:
Ver original
  1. double potencia(double a, unsigned n);

¡Sed imaginativos!
Mucha imaginación para esto no creo

Código C++:
Ver original
  1. double potencia ( double base , unsigned exponente ) {
  2.     return  ( exponente == 0 ) ? 1 : base * potencia ( base , exponente - 1 ) ;
  3. }
  4.  
  5. int main ( void ) {
  6.     printf ( "%g" , potencia ( 8 , 3 ) ) ;
  7.     return 0;
  8. }

Por cierto, ya que la base es un entero podríamos haber hecho la función potencia de tipo int en lugar de double.

¡¡¡Saluditos!!!

  #15 (permalink)  
Antiguo 18/11/2014, 12:47
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 5 meses
Puntos: 13
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por Pantaláimon Ver Mensaje
Venga va, uno sencillo para ir abriendo boca.
al fin mas retos, dejo mi solución :

Código C++:
Ver original
  1. double potencia(double a, unsigned n)
  2. {
  3.     if (n == 0) return 1;
  4.     double x = potencia (a, n >> 1);
  5.     return (n & 1) == 0 ? x * x : a * x * x;
  6. }
  7.  
  8. int main(void)
  9. {
  10.   printf("%lf\n", potencia(2, 8));
  11.  
  12.   return (0);
  13. }

Pantaláimon mas difíciles por favor esto ni siquiera me costo cinco minutos
  #16 (permalink)  
Antiguo 18/11/2014, 12:54
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 11 años, 10 meses
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por kutcher Ver Mensaje
al fin mas retos, dejo mi solución :
Mejor usa %g en printf y evitas la retahíla de ceros decimales.

¡¡¡Saluditos!!!

  #17 (permalink)  
Antiguo 20/11/2014, 12:09
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 17 años, 9 meses
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Buenas!

Voy dejando mis soluciones de los retos de la semana. Pero contad que no hay límite de tiempo para resolverlos. Si alguien entra ahora o va a otro ritmo, puede ofrecer sus propuestas sobre retos antiguos sin ningún tipo de problema.

La primera solución fue del mismo estilo de kutcher (empezando a contar por el último), aunque quizá la mía se entiende un poco menos por escribirla en una sola línea:
Código C:
Ver original
  1. int contarNegativos(int arr[], int n) {
  2.     return n > 0 ? (arr[n-1] < 0) + contarNegativos(arr, n - 1) : 0;
  3. }

Y siguiendo la misma lógica (calcular empezando por el final) hice la segunda que a diferencia de las soluciones que habéis dado no añade un carácter de nueva linea al final del string (aunque esto está abierto a interpretaciones):
Código C:
Ver original
  1. char* idiag(char* cadena, int n, int pos, char* resultado) {
  2.     if (n >= 1) {
  3.         if (n != 1)
  4.             sprintf(resultado + pos, "\n%*c", n - 1, ' ');
  5.         resultado[pos + n] = cadena[n - 1];
  6.         idiag(cadena, n - 1, pos - n, resultado);
  7.     }
  8.     return resultado;
  9. }
  10.  
  11. char* diag(char* cadena, char* resultado) {
  12.     int n = strlen(cadena);
  13.     return idiag(cadena, n, n * (n + 1) / 2 - 2, resultado);
  14. }
Aunque, al empezar a rellenar el string por atrás, tuve un pequeño inconveniente: el carácter '\0' se me añadía al final de cada cadena que escribía, no pudiendo, así, resumir la acción en un simple:
Código C:
Ver original
  1. sprintf(resultado + pos, "\n%*c%c", n - 1, ' ', cadena[n - 1]);

Por otro lado, y viendo comportamientos irregulares que tiene C. Por ejemplo, que:
Código C:
Ver original
  1. printf("%*c", 0, 'a');
imprime un carácter 'a'. Y como el hilo es para trabajar con recursividad y temas como el manejo de memoria dinámica los podríamos mandar un poco al garete. Los próximos ejercicios los voy a proponer tanto para resolver en C como C++. Aquí adelanto las solución de diag para C++.

Suponiendo la siguiente firma:
Código C++:
Ver original
  1. std::string diag(const std::string& str);
Mi solución es:
Código C++:
Ver original
  1. #include <string>
  2. #include <iostream>
  3.  
  4. std::string idiag(const std::string& cadena, int n) {
  5.     if(n > 0)
  6.         return idiag(cadena, n - 1) + (n == 1 ? "" : "\n") + std::string(n - 1, ' ') + cadena[n - 1];
  7.     else
  8.         return std::string();
  9. }
  10.  
  11. std::string diag(const std::string& cadena) {
  12.     return idiag(cadena, cadena.length());
  13. }
  14.  
  15. int main (void) {
  16.     std::string cadena = "abcde";
  17.  
  18.     std::string resultado = diag(cadena);
  19.  
  20.     std::cout << resultado << std::endl;
  21.  
  22.     return 0;
  23. }

Cita:
Iniciado por leosansan
Mucha imaginación para esto no creo
Con imaginación, me refería a no tomar la solución más evidente, pues había otras mejores. Estaba esperando una solución como la de kutcher, que independientemente de que use operadores de "gurú del C":
Cita:
(n & 1) == 0 se podría traducir a (n % 2 == 0)
(n >> 1) se podría traducir a (n / 2)
usa un algoritmo de divide y vencerás. Que quizá para pequeños computos no se nota, pero en caso de trasladar esta función para calculo de potencias con exponentes muy grandes el algoritmo de kutcher gana sobradamente. Por poner un ejemplo, si el exponente es 2^32 , tu algoritmo realizará del orden de 2^32 multiplicaciones mientras que el de kutcher realizará 33 multiplicaciones.

Cita:
Iniciado por leosansan
Por cierto, ya que la base es un entero podríamos haber hecho la función potencia de tipo int en lugar de double.
La base no es un entero, la base que propuse es double. Un real elevado a un entero no negativo, en general, da un real. Un entero elevado a un entero no negativo, en general, da un entero. No veo razón para elejir mejor una u otra.

¡Mañana dos nuevos retos!
__________________
github.com/xgbuils | npm/xgbuils

Última edición por Pantaláimon; 20/11/2014 a las 12:20
  #18 (permalink)  
Antiguo 20/11/2014, 13:54
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 11 años, 10 meses
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por Pantaláimon Ver Mensaje
Buenas!
usa un algoritmo de divide y vencerás. Que quizá para pequeños cómputos no se nota, pero en caso de trasladar esta función para calculo de potencias con exponentes muy grandes el algoritmo de kutcher gana sobradamente. Por poner un ejemplo, si el exponente es 2^32 , tu algoritmo realizará del orden de 2^32 multiplicaciones mientras que el de kutcher realizará 33 multiplicaciones.
¿Insinúas que la función recursiva hace esto:

Código C++:
Ver original
  1. potencia ( 2 , 4 )  = 2 * potencia ( 2 , 3 ) =
  2.                     = 2 * 2 * potencia ( 2 , 2 ) =
  3.                     = 2 * 2 * 2 * potencia ( 2 , 1 ) =
  4.                     = 2 * 2 * 2 * 2 * potencia ( 2 , 0 ) =
  5.                     = 2 * 2 * 2 * 2 * 1

en lugar de esto?

Código C++:
Ver original
  1. potencia ( 2 , 4 )  = 2 * potencia ( 2 , 3 )     =
  2.                     = 2 * 2 * potencia ( 2 , 2 ) =
  3.                     = 4 * 2 * potencia ( 2 , 1 ) =
  4.                     = 8 * 2 * potencia ( 2 , 0 ) =
  5.                     = 16 * 1

Por cierto, podríamos ahorrarnos el multiplicar por uno. Por ejemplo:

Código C++:
Ver original
  1. double potencia ( double base , unsigned exponente ) {
  2.   if ( exponente >= 1 ) return base * potencia ( base , exponente - 1 ) ;
  3. }

¡¡¡Saluditos!!!

  #19 (permalink)  
Antiguo 20/11/2014, 17:08
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 11 años, 9 meses
Puntos: 28
Respuesta: Petando la pila. Problemas y retos usando recursividad.

¿Quereís un problema recursivo?

Dado la siguiente estructura:
Código C++:
Ver original
  1. struct arbol
  2. {
  3.     arbol* ramas[2];
  4.     int dato;
  5. };

Dado un array a, transformarlo en un arbol. Os pongo un ejemplo:
Cita:
[1,2,3,4]


No es necesario que esté ordenado.
  #20 (permalink)  
Antiguo 20/11/2014, 17:09
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 11 años, 9 meses
Puntos: 28
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por leosansan Ver Mensaje
Código C++:
Ver original
  1. double potencia ( double base , unsigned exponente ) {
  2.   if ( exponente >= 1 ) return base * potencia ( base , exponente - 1 ) ;
  3. }

¡¡¡Saluditos!!!

Falta un else ahí ^^
  #21 (permalink)  
Antiguo 20/11/2014, 17:34
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 17 años, 9 meses
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

No, leosan, no insinúo eso. En los dos casos que expones se realizan 4 multiplicaciones, tanto si vas multiplicando mientras avanzas al siguiente paso como si las multiplicas todas al final.

Fíjate en lo que hace el algoritmo de kutcher y verás:
Código pseudocódigo:
Ver original
  1. Calculamos potencia(2,8):
  2. potencia(2, 8) = x * x
  3. donde x = potencia(2,4)
  4.  
  5. Calculamos potencia(2,4):
  6. potencia(2, 4) = x * x
  7. donde x = potencia(2,2)
  8.  
  9. Calculamos potencia(2,1):
  10. potencia(2,1) = 2 * x * x
  11. donde x = potencia(2, 0) = 1
  12.  
  13. En total 4 multiplicaciones.

¿Cuanto costaría calcular potencia(2, 32)? sólo dos multiplicaciones más: 6

En cambio con tu algoritmo deberías hacer del orden de 32 multiplicaciones. Esta es la idea escondida.

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

Última edición por Pantaláimon; 20/11/2014 a las 18:04
  #22 (permalink)  
Antiguo 21/11/2014, 02:56
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 17 años, 9 meses
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

¡Hola de nuevo!

¡Llegó el día! Así que aquí os traigo dos problemas más:

1) Crear una función comb que reciba dos parámetros y te devuelva el coeficiente binomial. La fórmula del coeficiente binomial es: n! / (k! * (n-k)!) donde "!" es el signo del factorial. La firma de la función será:
Código C:
Ver original
  1. unsigned comb(unsigned n, unsigned k);

Una de las utilidades del coeficiente binomial es para calcular el numero de subconjuntos sin repetición ni orden que podemos obtener de otro conjunto. Por ejemplo, imaginemos una bolsa con 5 bolas con las letras A, B, C, D y E y que, entonces, sólo podemos coger 3 bolas. ¿Cuantas posibles combinaciones podemos obtener contando que sacar A,B,E es lo mismo que sacar A,E,B? Pues ese número te lo da: comb(5,3)

2) Dado un número, podemos jugar al siguiente juego:
a) Si es par, lo dividimos entre 2.
b) Si es impar, lo multiplicamos por 3 y luego le sumamos 1.
Podemos realizar estas reglas sobre el número que nos retorna tantas veces como nos dé la gana. Por ejemplo con el 6:
Código explicación:
Ver original
  1. 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4 ...

Se puede ver que llega un punto en que hay un ciclo 4 -> 2 -> 1 que se repite indefinidamente. Lothar Collatz, observó que con todos los números que iba probando -tardara más o menos- siempre llegaba al ciclo 4 -> 2 -> 1 y conjeturó que esto debía pasar con todos los números (aún no se ha demostrado que sea cierto pero para el rango de número con que vamos a trabajar es cierto).

En este segundo problema deberemos crear una función promedioCollatz que dado un numero n, nos diga el promedio de pasos que tienen que hacer los numeros del 1 al n para llegar al número 1. Por ejemplo:
1 => 0 pasos para llegar al 1
2 => 1 paso para llegar al 1
3 => 7 pasos para llegar al 1
4 => 2 pasos para llegar al 1
5 => 5 pasos para llegar al 1

Entonces la función promedioCollatz se comportaría de la siguiente manera:
Código explicación:
Ver original
  1. [B]promedioCollatz(1)[/B] == 0 / 1 == 0
  2. [B]promedioCollatz(2)[/B] == (0+1) / 2 == 0.5
  3. [B]promedioCollatz(3)[/B] == (0+1+7) / 3 == 2.6666..
  4. [B]promedioCollatz(4)[/B] == (0+1+7+2) / 4 == 2.5
  5. [B]promedioCollatz(5)[/B] == (0+1+7+2+5) / 5 == 3
  6. etc...

La firma de la función será la siguiente:
Código C:
Ver original
  1. double promedioCollatz(unsigned num)

Los problemas se pueden resolver tanto en C como en C++.

Y ahora, ¡A petar la pila!
__________________
github.com/xgbuils | npm/xgbuils
  #23 (permalink)  
Antiguo 21/11/2014, 03:39
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 9 años, 6 meses
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por Pantaláimon Ver Mensaje
1) Crear una función comb que reciba dos parámetros y te devuelva el coeficiente binomial.
Código C:
Ver original
  1. unsigned int comb(
  2.     unsigned int n,
  3.     unsigned int k )
  4. {
  5.   if ( n <= k )
  6.     return 0;
  7.   else if ( k > 0 )
  8.     return n * ( n - k ) * comb( n - 1, k - 1 ) / ( k * ( n - k ) );
  9.   else
  10.     return 1;
  11. }

Este de momento era fácil, vamos a ver el siguiente.

Cita:
Iniciado por Pantaláimon Ver Mensaje
2) Dado un número, podemos jugar al siguiente juego...
Código C++:
Ver original
  1. unsigned int collatz(
  2.     const unsigned int n )
  3. {
  4.   if ( n == 1 )
  5.     return 0;
  6.   else if ( n % 2 )
  7.     return 1 + collatz( n * 3 + 1 );
  8.   else
  9.     return 1 + collatz( n / 2 );
  10. }
  11.  
  12. double promedioCollatz(
  13.     const unsigned int num )
  14. {
  15.   if ( num > 0 )
  16.     return ( collatz( num ) + ( num - 1 ) * promedioCollatz( num - 1 ) ) / num;
  17.   else
  18.     return 0;
  19. }

Vamos a probar ahora los de amchacon ;)

Cita:
Iniciado por amchacon Ver Mensaje
¿Quereís un problema recursivo?

Dado un array a, transformarlo en un arbol. Os pongo un ejemplo:

Estoooooo el árbol no debería quedar con esta otra estructura??

Código:
 1
  \
   2
    \
     3
      \
       4
O si no... ¿qué valor tendrían los nodos en negro?

Última edición por eferion; 21/11/2014 a las 04:12 Razón: Publicado el 2º ejercicio
  #24 (permalink)  
Antiguo 21/11/2014, 04:51
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 11 años, 10 meses
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por Pantaláimon Ver Mensaje
¡Hola de nuevo!
Y ahora, ¡A petar la pila!
"Güeno" , el primero ( el segundo aún tengo que entenderlo ):
Código C++:
Ver original
  1. #include <stdio.h>
  2.  
  3. int unsigned comb ( unsigned n , unsigned k ) ;
  4.  
  5. int main ( ) {
  6.   printf ( "%u" , comb (  12 , 5 ) ) ;
  7.   return 0 ;
  8. }
  9.  
  10. int unsigned comb ( unsigned n , unsigned k )  {
  11.     if ( k > n / 2 )
  12.         k = n - k ;
  13.     if ( k >= 1 )  return ( n  * comb (  n - 1 , k - 1 ) / k ) ;
  14.     else
  15.         return 1;
  16. }

Observar que aprovecho las propiedades de los números combinatorios y así si piden como ( 25 , 20 ) calculo su equivalente comb ( 25 , 5 ) que realiza menos operaciones.

¡¡¡Saluditos!!!

  #25 (permalink)  
Antiguo 21/11/2014, 05:36
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 5 meses
Puntos: 13
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Mi solución al primer reto:

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

La solución al segundo esta estuvo medio complicada:

Código C++:
Ver original
  1. double promedioCollatz(unsigned num)
  2. {
  3.     unsigned y = num;
  4.     if (y <= 1) return 0;
  5.     return (y % 2 == 0) ? 1 + promedioCollatz( y / 2 )
  6.                         : 1 + promedioCollatz( 3 * y + 1 );
  7. }

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

Cita:
Iniciado por kutcher Ver Mensaje
La solución al segundo esta estuvo medio complicada:
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

No se si me explico.
  #27 (permalink)  
Antiguo 21/11/2014, 07:29
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 11 años, 10 meses
Puntos: 49
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".......................

No se si me explico.
Sí campeón, te explicas alto y claro.

"Creo" no haberla pifiado. En lugar de dos funciones como eferion he usado dos argumentos, espero que sea válido:

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

¡¡¡Saluditos!!!

  #28 (permalink)  
Antiguo 21/11/2014, 07:39
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 11 años, 10 meses
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

EDITO: Aprovecho para "adelgazar" el del coeficiente combinatorio:

Código C++:
Ver original
  1. include <stdio.h>
  2.  
  3. int unsigned comb ( unsigned n , unsigned k ) ;
  4.  
  5. int main ( ) {
  6.   printf ( "%u" , comb (  15 , 5 ) ) ;
  7.   return 0 ;
  8. }
  9.  
  10. int unsigned comb ( unsigned n , unsigned k )  {    
  11.   return ( k > n / 2 ) ?  ( comb (  n , k )  ) : ( k >= 1 ) ?  ( n  * comb (  n - 1 , k - 1 ) / k ) : 1 ;}

¡¡¡ Horror ¡¡¡, no edita sino que crea un nuevo mensaje. Sorry ¡¡¡.

¡¡¡Saluditos!!!


Última edición por leosansan; 21/11/2014 a las 10:05
  #29 (permalink)  
Antiguo 21/11/2014, 11:06
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 17 años, 9 meses
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por leosansan
En lugar de dos funciones como eferion he usado dos argumentos, espero que sea válido:
No es válido leosan, aún no me ha dado tiempo de mirar la solución, pero la firma/prototipo de la función es el requerido por el enunciado. Si la función recursiva tiene más parámetros de los que se requiere, define ésta como una función auxiliar y que la función requerida por el enunciado llame a ésta. Por ejemplo: tal como he hecho para la solución de diag.

Un saludo!
__________________
github.com/xgbuils | npm/xgbuils
  #30 (permalink)  
Antiguo 21/11/2014, 13:18
Avatar de leosansan  
Fecha de Ingreso: mayo-2012
Ubicación: GRAN CANARIA
Mensajes: 194
Antigüedad: 11 años, 10 meses
Puntos: 49
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por Pantaláimon Ver Mensaje
No es válido leosan, aún no me ha dado tiempo de mirar la solución, pero la firma/prototipo de la función es el requerido por el enunciado. Si la función recursiva tiene más parámetros de los que se requiere, define ésta como una función auxiliar y que la función requerida por el enunciado llame a ésta. ............................................
¡¡¡ Quisquilloso, bandido ¡¡¡.


Pero.....mejor que usar otra función, uffffff, ya que nadie ha dicho nada de que esté prohibido usar variables globales :

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



Pero yo propondría que los prototipos que indicas sean tan sólo una ayuda por si alguien está muy perdido, así se mejoraría la inventiva e ingenio de los retos. Pero claro, es tan sólo una opinión.....

¡¡¡Saluditos!!!


Última edición por leosansan; 21/11/2014 a las 14:00

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 11:38.