Petando la pila. Problemas y retos usando recursividad.

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