Petando la pila. Problemas y retos usando recursividad.

[eferion]

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 debe hacer todos los cálculos excepto los directamente relacionados con la salida estándar.

Mi versión:

Código C++:

void bucleChequeo( int numero, int candidato, int primerPrimo, int ver )
{
  int exp = ComprobarPrimo( &numero, candidato );
  if ( exp > 0 && ver)
  {
    if ( primerPrimo == 0 ) printf( " *" );
    if ( exponente == 1 )
      printf( " %d", base );
    else if ( exponente > 0 )
      printf( " %d^%d", base, exponente );
 
    primerPrimo = 0;
  }
 
  candidato += 2;
  if ( numero > 1 )
    bucleChequeo( numero, candidato, primerPrimo, ver );
}
 

Tu propuesta:

Código C++:

void bucleChequeo( int numero, int candidato, int primerPrimo, int ver )
{
  int exp = ComprobarPrimo( &numero, candidato );
  if ( exp > 0 )
  {
    if ( ver && primerPrimo == 0 ) printf( " *" );
    if ( ver && exponente == 1 )
      printf( " %d", base );
    else if ( ver && exponente > 0 )
      printf( " %d^%d", base, exponente );
 
    primerPrimo = 0;
  }
 
  candidato += 2;
  if ( numero > 1 )
    bucleChequeo( numero, candidato, primerPrimo, ver );
}
 

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.

[Pantaláimon]

Hola leosan,

Código C:

int main ( void ) {
    int ver;
    return descompon ( 1500 , 1550,  ver ) , 0 ;
}
 

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!

[Pantaláimon]

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

C++11

Código C++:

#include <iostream>
#include <map>
#include <cmath>
 
std::map< int, std::pair<int, int> > descomposiciones;
 
void descomponNumero(int num, int root, int i = 2 ) {
    auto iterator = descomposiciones.find(num);
    if (iterator == descomposiciones.end()) {
        if (num > 1 && i <= root) {
            if (num % i == 0) {
                int n = num / i;
                descomposiciones[num] = std::make_pair(i, n);
                descomponNumero(n, (int) std::sqrt(n));
            } else {
                descomponNumero(num, root, i + 1);
            }
        } else {
            descomposiciones[num] = std::make_pair(num, 1);
        }
    }
}
 
void mostrar(int num, int factor, int exponente, int ver) {
    auto pair = descomposiciones[num];
    if (num <= 1 || factor != pair.first) {
        if (ver)
            std::cout << factor;
        if (exponente > 1 && ver) {
            std::cout << "^" << exponente;
        }
        if (pair.first > 1 && ver) {
            std::cout << " * ";
        }
        exponente = 0;
    }
    if (num > 1) {
        mostrar(pair.second, pair.first, exponente + 1, ver);
    }
}
 
void descompon(int a, int b, int ver) {
    if (a <= b) {
        descomponNumero(a, (int) std::sqrt(a));
        
        if (ver)
            std::cout << a << " = ";
        mostrar(a, descomposiciones[a].first, 0, ver);
        if (ver)
            std::cout << std::endl;
 
        descompon(a + 1, b, ver);
    }
}
 
int main() {
    descompon(2, 100000, 0);
    /*for (auto  i : descomposiciones) {
        std::cout << i.first << " -> " << i.second.first << ", " << i.second.second << std::endl;
    }*/
    return 0;
}
 

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.

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++:

void descompon(int a, int b, int ver) {
    if (a <= b) {
        descomponNumero(a, (int) std::sqrt(a));
        
        if (ver) {
            std::cout << a << " = ";
            mostrar(a, descomposiciones[a].first, 0);
            std::cout << std::endl;
        }
 
        descompon(a + 1, b, ver);
    }
}
 

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:

void bucleChequeo( int numero, int candidato, int primerPrimo, int ver )
{
  int exp = ComprobarPrimo( &numero, candidato );
  if ( exp > 0 )
  {
    if ( primerPrimo == 0 && ver ) printf( " *" );
    if ( exponente == 1 && ver )
      printf( " %d", base );
    else if ( exponente > 0 && ver )
      printf( " %d^%d", base, exponente );
 
    primerPrimo = 0;
  }
 
  candidato += 2;
  if ( numero > 1 )
    bucleChequeo( numero, candidato, primerPrimo, ver );
}
 

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!

[eferion]

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

[Pantaláimon]

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++:

struct Punto {
    double x;
    double y;
}
 
double areaPoligono(struct Punto puntos[], int n); // C
double areaPoligono(std::vector<Punto> puntos); // C++
 

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

Un saludo!

[eferion]

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++:

#include <iostream>
 
struct Punto
{
    double x;
    double y;
};
 
double areaPoligono(struct Punto puntos[], int max, int i )
{
  struct Punto* p0 = &puntos[ i ];
  struct Punto* p1;
 
  ++i;
  if ( i < max )
    p1 = &puntos[ i ];
  else
    p1 = &puntos[ 0 ];
 
  double factor1 = ( p1->y - p0->y ) / ( p1->x - p0->x );
  double factor2 = p0->y - factor1 * p0->x;
  factor1 *= 0.5;
 
  double v0 = ( factor1 * p0->x + factor2 ) * p0->x;
  double v1 = ( factor1 * p1->x + factor2 ) * p1->x;
 
  double area = v1 - v0;
 
  if ( i < max )
    return area + areaPoligono( puntos, max, i );
  else
    return area;
}
 
double areaPoligono(struct Punto puntos[], int n)
{
  return fabs( areaPoligono( puntos, n, 0 ) );
}
 
int main(int , char **)
{
  struct Punto puntos[] = { {3,20}, {15,20}, {6,10}, {9,30}, {12,10} };  // Estrella de 5 puntas
  int n = sizeof( puntos ) / sizeof( struct Punto );
  std::cout << "Area del polígono: " << areaPoligono( puntos, n ) << std::endl;
  return 0;
}
 

Un saludo

[eferion]

Ya se ha muerto este hilo??? que poco ha durado

[kutcher]

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:

Iniciado por Pantaláimon

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++:

#include <stdio.h>
 
typedef struct
{
    double x, y;
} Punto;
 
double AreaPoligono(Punto *puntos, int N, int i)
{
    return (i < N) ? puntos[i].x * puntos[((i + 1) % N)].y +
           AreaPoligono(puntos, N, i + 1) -
           puntos[i].y * puntos[((i + 1) % N)].x : 0;
}
 
double areaPoligono(Punto *puntos, int N)
{
    double area = AreaPoligono(puntos, N, 0) / 2;
    return (area < 0) ? -area : area;
}
 
int main(void)
{
    Punto puntos[] = { {-3,-2}, {3,-2}, {1,5} };
    int n = sizeof(puntos) / sizeof(Punto);
    printf("Area del poligono: %g\n", areaPoligono(puntos, n));
    return 0;
}
 

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

[eferion]

Iniciado por kutcher

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

[amchacon]

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! ^^