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

Petando la pila. Problemas y retos usando recursividad.

Estas en el tema de Petando la pila. Problemas y retos usando recursividad. en el foro de C/C++ en Foros del Web. Cita: Iniciado por Pantaláimon Pero ahora pienso que sí deberían hacerse por las razones que he explicado. Es decir, la función con ver == 0 ...

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

Cita:
Iniciado por Pantaláimon Ver Mensaje
Pero ahora pienso que sí deberían hacerse por las razones que he explicado. Es decir, la función con ver == 0 debe hacer todos los cálculos excepto los directamente relacionados con la salida estándar.
Mi versión:
Código C++:
Ver original
  1. void bucleChequeo( int numero, int candidato, int primerPrimo, int ver )
  2. {
  3.   int exp = ComprobarPrimo( &numero, candidato );
  4.   if ( exp > 0 && ver)
  5.   {
  6.     if ( primerPrimo == 0 ) printf( " *" );
  7.     if ( exponente == 1 )
  8.       printf( " %d", base );
  9.     else if ( exponente > 0 )
  10.       printf( " %d^%d", base, exponente );
  11.  
  12.     primerPrimo = 0;
  13.   }
  14.  
  15.   candidato += 2;
  16.   if ( numero > 1 )
  17.     bucleChequeo( numero, candidato, primerPrimo, ver );
  18. }

Tu propuesta:
Código C++:
Ver original
  1. void bucleChequeo( int numero, int candidato, int primerPrimo, int ver )
  2. {
  3.   int exp = ComprobarPrimo( &numero, candidato );
  4.   if ( exp > 0 )
  5.   {
  6.     if ( ver && primerPrimo == 0 ) printf( " *" );
  7.     if ( ver && exponente == 1 )
  8.       printf( " %d", base );
  9.     else if ( ver && exponente > 0 )
  10.       printf( " %d^%d", base, exponente );
  11.  
  12.     primerPrimo = 0;
  13.   }
  14.  
  15.   candidato += 2;
  16.   if ( numero > 1 )
  17.     bucleChequeo( numero, candidato, primerPrimo, ver );
  18. }

En ambos casos el algoritmo calcula de forma correcta la descomposición del número, que es lo que se pide en el enunciado... la única diferencia es que mi versión es ligeramente más eficiente.

No se, lo mismo es que hay algo que no entiendo, pero tal y como lo veo, los "if" que acompañan a los printf no tienen nada que ver con la descomposición del número en factores. Su función es componer, si procede, la salida del programa... pero el resultado, se imprima o no, ya está calculado.
  #122 (permalink)  
Antiguo 17/12/2014, 08:31
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 18 años, 2 meses
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Hola leosan,

Código C:
Ver original
  1. int main ( void ) {
  2.     int ver;
  3.     return descompon ( 1500 , 1550,  ver ) , 0 ;
  4. }
Este código puede dar cualquier cosa ya que ver no esta inicializado. Aunque inicializado a 0 aún muestra resultados por pantalla.

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

Bueno, mi solución al segundo problema es esta.

C++11
Código C++:
Ver original
  1. #include <iostream>
  2. #include <map>
  3. #include <cmath>
  4.  
  5. std::map< int, std::pair<int, int> > descomposiciones;
  6.  
  7. void descomponNumero(int num, int root, int i = 2 ) {
  8.     auto iterator = descomposiciones.find(num);
  9.     if (iterator == descomposiciones.end()) {
  10.         if (num > 1 && i <= root) {
  11.             if (num % i == 0) {
  12.                 int n = num / i;
  13.                 descomposiciones[num] = std::make_pair(i, n);
  14.                 descomponNumero(n, (int) std::sqrt(n));
  15.             } else {
  16.                 descomponNumero(num, root, i + 1);
  17.             }
  18.         } else {
  19.             descomposiciones[num] = std::make_pair(num, 1);
  20.         }
  21.     }
  22. }
  23.  
  24. void mostrar(int num, int factor, int exponente, int ver) {
  25.     auto pair = descomposiciones[num];
  26.     if (num <= 1 || factor != pair.first) {
  27.         if (ver)
  28.             std::cout << factor;
  29.         if (exponente > 1 && ver) {
  30.             std::cout << "^" << exponente;
  31.         }
  32.         if (pair.first > 1 && ver) {
  33.             std::cout << " * ";
  34.         }
  35.         exponente = 0;
  36.     }
  37.     if (num > 1) {
  38.         mostrar(pair.second, pair.first, exponente + 1, ver);
  39.     }
  40. }
  41.  
  42. void descompon(int a, int b, int ver) {
  43.     if (a <= b) {
  44.         descomponNumero(a, (int) std::sqrt(a));
  45.        
  46.         if (ver)
  47.             std::cout << a << " = ";
  48.         mostrar(a, descomposiciones[a].first, 0, ver);
  49.         if (ver)
  50.             std::cout << std::endl;
  51.  
  52.         descompon(a + 1, b, ver);
  53.     }
  54. }
  55.  
  56. int main() {
  57.     descompon(2, 100000, 0);
  58.     /*for (auto  i : descomposiciones) {
  59.         std::cout << i.first << " -> " << i.second.first << ", " << i.second.second << std::endl;
  60.     }*/
  61.     return 0;
  62. }

La idea a la hora de resolverlo es no hacer cálculos repetidos. Si he descompuesto los números del 2 al 15, cuando tenga que descomponer el 16 no hace falta que repita cálculos. Pues los factores de 16 son igual a 2 + los factores de 8 (previamente calculados).

Buenas, eferion.
Cita:
Iniciado por eferion
En ambos casos el algoritmo calcula de forma correcta la descomposición del número, que es lo que se pide en el enunciado...
El problema es que calcular de forma correcta la descomposición es una tarea ambigua. Yo podría decir que he descompuesto los números del 2 al 10 cuando genero un map que guarda la siguiente información:

2 -> 2, 1
3 -> 3, 1
4 -> 2, 2
5 -> 5, 1
6 -> 2, 3
7 -> 7, 1
8 -> 2, 4
9 -> 3, 3
10 -> 2, 5

Alguien me diria:
- ¡Ei, que el 8 no lo has descompuesto del todo! Has parado la descomposición en el 4.
Pero yo podría decir:
- No es cierto, la tarea de descomponer el 8 la he realizado. Pues he descompuesto el 8 en 2 * 4 y previamente el 4 lo he descompuesto en 2 * 2.

Con lo cual el cálculo de descomposición de los números del 2 al 10 lo he hecho. Ahora la única tarea que me quedaría seria mostrarlo por pantalla. Pero claro, al igual que tu no haces los cálculos para ponerlo bonito en pantalla, yo podría decir lo mismo y implementar descompon así:
Código C++:
Ver original
  1. void descompon(int a, int b, int ver) {
  2.     if (a <= b) {
  3.         descomponNumero(a, (int) std::sqrt(a));
  4.        
  5.         if (ver) {
  6.             std::cout << a << " = ";
  7.             mostrar(a, descomposiciones[a].first, 0);
  8.             std::cout << std::endl;
  9.         }
  10.  
  11.         descompon(a + 1, b, ver);
  12.     }
  13. }
Ya que la tarea dentro del if (ver) {...} sólo coge los datos de descomposiciones y con éstos lo imprime tal como indica el enunciado. Es decir, una tarea de ponerlo bonito, pero no el cálculo real de la descomposición.

¿Ves correcto que pueda hacer esto?

Yo creo que no, el enunciado, a parte de calcular la factorización de un rango de números también pide mostrarlo bonito. Por tanto, los cálculos para ponerlo bonito también deben evaluarse. Con lo cual mi propuesta sería esta, realmente:

Código C:
Ver original
  1. void bucleChequeo( int numero, int candidato, int primerPrimo, int ver )
  2. {
  3.   int exp = ComprobarPrimo( &numero, candidato );
  4.   if ( exp > 0 )
  5.   {
  6.     if ( primerPrimo == 0 && ver ) printf( " *" );
  7.     if ( exponente == 1 && ver )
  8.       printf( " %d", base );
  9.     else if ( exponente > 0 && ver )
  10.       printf( " %d^%d", base, exponente );
  11.  
  12.     primerPrimo = 0;
  13.   }
  14.  
  15.   candidato += 2;
  16.   if ( numero > 1 )
  17.     bucleChequeo( numero, candidato, primerPrimo, ver );
  18. }

Edit: Antes he dicho que la tarea de factorizar un rango de números es ambigua, y no he explicado la razón. El problema es que cualquier tarea es ambigua si no se dice sobre que estructura de datos se guarda esa información. En anteriores problemas el valor debía devolverse en un array, en un string, en un entero. Aquí la "estructura de datos" en la que se debe guardar la informació es la salida estándar. Por eso creo que está bien evaluar esos cálculos dentro del tiempo de ejecución. Si no, cosas como mi anterior ejemplo podrían ser válidas.

Ese es mi razonamiento. Espero haberlo explicado bien ahora.

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

Última edición por Pantaláimon; 17/12/2014 a las 10:42
  #124 (permalink)  
Antiguo 17/12/2014, 11:30
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 10 años
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Quizás habría sido entonces mejor que la función recibiese un buffer en el que almacenar el resultado en vez de usar la variable booleana... Así la decisión de sacar eso por pantalla o no depende del código que llama a la función
  #125 (permalink)  
Antiguo 20/12/2014, 08:16
 
Fecha de Ingreso: julio-2006
Ubicación: Barcelona
Mensajes: 244
Antigüedad: 18 años, 2 meses
Puntos: 32
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Ok, eferion, lo tendré en cuenta.

Pongo un nuevo problema. Pues tengo otros varios pensados pero he de acabar de perfilarlos.

Area de un polígono.

Dado un array de puntos donde cada punto se une geométricamente por una línea recta al siguiente y el último se une al primero. Esto puede representar un polígono. Se debe crear una función que calcule el area de dicho polígono. Hay que considerar todos los tipos de polígonos que pueden ser descritos:
http://commons.wikimedia.org/wiki/Fi...n_types_es.svg

Se considerara area del polígono la suma de las areas de las regiones cerradas de un polígono (como se puede ver en las imagenes que existen poligonos con más de una región cerrada)

Y aquí el prototipo de la función:
Código C++:
Ver original
  1. struct Punto {
  2.     double x;
  3.     double y;
  4. }
  5.  
  6. double areaPoligono(struct Punto puntos[], int n); // C
  7. double areaPoligono(std::vector<Punto> puntos); // C++

¡Doy libertad para implementarlo cómo queráis!

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

Bueno, aún me quedan por hacer algunas pruebas para certificar su funcionamiento. Lo pongo aquí porque, con las fiestas, lo mismo me quedo sin el código fuente.

Código C++:
Ver original
  1. #include <iostream>
  2.  
  3. struct Punto
  4. {
  5.     double x;
  6.     double y;
  7. };
  8.  
  9. double areaPoligono(struct Punto puntos[], int max, int i )
  10. {
  11.   struct Punto* p0 = &puntos[ i ];
  12.   struct Punto* p1;
  13.  
  14.   ++i;
  15.   if ( i < max )
  16.     p1 = &puntos[ i ];
  17.   else
  18.     p1 = &puntos[ 0 ];
  19.  
  20.   double factor1 = ( p1->y - p0->y ) / ( p1->x - p0->x );
  21.   double factor2 = p0->y - factor1 * p0->x;
  22.   factor1 *= 0.5;
  23.  
  24.   double v0 = ( factor1 * p0->x + factor2 ) * p0->x;
  25.   double v1 = ( factor1 * p1->x + factor2 ) * p1->x;
  26.  
  27.   double area = v1 - v0;
  28.  
  29.   if ( i < max )
  30.     return area + areaPoligono( puntos, max, i );
  31.   else
  32.     return area;
  33. }
  34.  
  35. double areaPoligono(struct Punto puntos[], int n)
  36. {
  37.   return fabs( areaPoligono( puntos, n, 0 ) );
  38. }
  39.  
  40. int main(int , char **)
  41. {
  42.   struct Punto puntos[] = { {3,20}, {15,20}, {6,10}, {9,30}, {12,10} };  // Estrella de 5 puntas
  43.   int n = sizeof( puntos ) / sizeof( struct Punto );
  44.   std::cout << "Area del polígono: " << areaPoligono( puntos, n ) << std::endl;
  45.   return 0;
  46. }

Un saludo

Última edición por eferion; 23/12/2014 a las 00:55
  #127 (permalink)  
Antiguo 26/01/2015, 04:22
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 10 años
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Ya se ha muerto este hilo??? que poco ha durado
  #128 (permalink)  
Antiguo 02/02/2015, 17:16
 
Fecha de Ingreso: noviembre-2014
Mensajes: 36
Antigüedad: 9 años, 11 meses
Puntos: 13
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Vaya, lleva tiempo inactivo este hilo al parecer todos nos echamos unas largas vacaciones xD, por mi parte ya devuelta con las actividades diarias, ahora veamos el ultimo ejercicio propuesto:

Cita:
Iniciado por Pantaláimon Ver Mensaje
Area de un polígono.

Dado un array de puntos donde cada punto se une geométricamente por una línea recta al siguiente y el último se une al primero. Esto puede representar un polígono. Se debe crear una función que calcule el area de dicho polígono. Hay que considerar todos los tipos de polígonos que pueden ser descritos:
http://commons.wikimedia.org/wiki/Fi...n_types_es.svg
Solución:

Código C++:
Ver original
  1. #include <stdio.h>
  2.  
  3. typedef struct
  4. {
  5.     double x, y;
  6. } Punto;
  7.  
  8. double AreaPoligono(Punto *puntos, int N, int i)
  9. {
  10.     return (i < N) ? puntos[i].x * puntos[((i + 1) % N)].y +
  11.            AreaPoligono(puntos, N, i + 1) -
  12.            puntos[i].y * puntos[((i + 1) % N)].x : 0;
  13. }
  14.  
  15. double areaPoligono(Punto *puntos, int N)
  16. {
  17.     double area = AreaPoligono(puntos, N, 0) / 2;
  18.     return (area < 0) ? -area : area;
  19. }
  20.  
  21. int main(void)
  22. {
  23.     Punto puntos[] = { {-3,-2}, {3,-2}, {1,5} };
  24.     int n = sizeof(puntos) / sizeof(Punto);
  25.     printf("Area del poligono: %g\n", areaPoligono(puntos, n));
  26.     return 0;
  27. }

Espero que los demás compañeros se vayan reportando estos días, no eferion ?

Última edición por kutcher; 02/02/2015 a las 18:06
  #129 (permalink)  
Antiguo 03/02/2015, 01:25
 
Fecha de Ingreso: octubre-2014
Ubicación: Madrid
Mensajes: 1.212
Antigüedad: 10 años
Puntos: 204
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Cita:
Iniciado por kutcher Ver Mensaje
Espero que los demás compañeros se vayan reportando estos días, no eferion ?
Hice mi aportación el 22 de diciembre... y llevo esperando desde entonces jejejeje
  #130 (permalink)  
Antiguo 12/04/2015, 04:08
 
Fecha de Ingreso: julio-2012
Mensajes: 375
Antigüedad: 12 años, 2 meses
Puntos: 28
Respuesta: Petando la pila. Problemas y retos usando recursividad.

Refloto el tema para poner una nueva propuesta.

Dado un conjunto {1...N} . Podemos dividirle en dos subconjuntos que su suma den lo mismo. Por ejemplo, para N = 3:

{1,2} = {3}

Puesto que 1+2 = 3.

Otro ejemplo con N = 7:

{1,6,7} = {2,3,4,5}
{2,5,7} = {1,3,4,6}
{3,4,7} = {1,2,5,6}
{1,2,4,7} = {3,5,6}

Dado un N, calcular de cuantas formas podemos hacer los subconjuntos para que se cumpla esta propiedad. Para N = 3 ya hemos visto que hay una posibilidad, para N = 7 tenemos 4 posibilidades. Haz un algoritmo recursivo que lo resuelva para cualquier 0 < N < 39.

Ejemplo de entrada
7

La función debe dar:
4

Ejemplo de entrada2
3

Ejemplo de salida 2
1

¡Venga animaos! ^^

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 10:43.