Estoy tratando de aprender Java por mi cuenta y normalmente tengo más recursos que suficientes con buenos sitios como estos, pero ahora solo quiero saber dónde me equivoco.

Entonces, el problema se expresó como:

La siguiente secuencia iterativa se define para el conjunto de enteros positivos:

n → n / 2 (n es par) n → 3n + 1 (n es impar)

Usando la regla anterior y comenzando con 13, generamos la siguiente secuencia:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 Se puede ver que esta secuencia (comenzando en 13 y terminando en 1) contiene 10 términos. Aunque aún no se ha probado (Problema de Collatz), se piensa que todos los números iniciales terminan en 1.

¿Qué número inicial, menos de un millón, produce la cadena más larga?

NOTA: Una vez que la cadena comienza, se permite que los términos superen el millón.

Sigo recibiendo estos java.lang.StackOverflowError, podría alguien ayudarme por favor. Mi código:

import java.util.HashMap;

public class Euler
{
    HashMap<Integer,Integer> check;
    int result;

    public Euler()
    {
        check = new HashMap<Integer,Integer>();     
    }

    public int search(int number)
    {

        int startingNumber = number;

        while (check.get(number)==null && number!=1){

            if (number%2==0){
                number = number / 2;
                result = search(number);
                result++;               
            }

            else {
                number = (3*number)+1;
                result = search(number);
                result++;
            }
        }

        if (check.get(startingNumber)!=null){
            result=result+check.get(number);
            check.put(startingNumber,result);

        }
        else{
            check.put(startingNumber,result);
        }

        return result;
    }

    public int test()
    {
        int temp = 0;
        int highest=0;
        int get = 0;
        for (int i=1000001;i>1;i--){
            result = 0;
            temp = search(i);
            if(temp>highest){
                highest=temp;
                get = i;
            }
            System.out.println(i);
        }

        return get;
    }


}

Editar:

public class Euler
{
   public Euler()
    {
    }

    public int quickSearch(int numb)
    {
        int steps = 0;
        while (numb != 1) {
            if (numb % 2 == 0) {
                numb /= 2;
            }
            else {
                numb = 3 * numb + 1;
            }
            steps++;
        }
        return steps;
    }


    public int test()
    {
        int temp = 0;
        int highest=0;
        int get = 0;
        for (int i=1;i<1000001;i=i+2){

            temp = quickSearch(i);
            if(temp>highest){
                highest=temp;
                get = i;
            }
            System.out.println(i);

        }

        return get;
    }
}

EDIT2: Entonces, en el código de la versión EDIT, obtuve una congelación de la máquina, pero cuando cambié int a long, funcionó perfectamente, aunque entiendo que con algunos Map para almacenar valores, puedes encontrarlo más rápido. Gracias a todos !!

1
Robert 28 sep. 2016 a las 13:46

3 respuestas

La mejor respuesta

El problema es que tiene demasiadas llamadas recursivas. La mejor solución para esto sería hacer que el código sea iterativo. Simplemente vuelva a trabajar su ciclo while para verificar primero si el número ya se encontró. Si es así, devuelva la suma de los pasos que tomó para llegar a ese número y se necesitará para pasar de ese número a 1. De lo contrario, actualice el número para el siguiente paso y vuelva a ejecutar el ciclo. Mientras tanto, solo debe realizar un seguimiento de los pasos que tomó para llegar a un número conocido.

Personalmente, eliminaría el HashMap por completo y solo tendría un bucle while simple:

int steps = 0;
while (number != 1) {
    if (number % 2 == 0) number /= 2;
    else number = 3 * number + 1
    steps++;
}

Editar: si desea agregar un HashMap para almacenar los valores encontrados, puede hacerlo así (supongo que definió un HashMap<Long, Integer> llamado foundNumbers anteriormente):

public int search(long number) {

    int steps = 0;
    long initialNumber = number;
    while (number != 1) {
        if (number % 2 == 0) number /= 2;
        else number = 3 * number + 1
        steps++;

        if (foundNumbers.containsKey(number)) {
            steps += foundNumbers.get(number)
            foundNumbers.put(initialNumber, steps);
            return steps;
        }
    }

    foundNumbers.put(initialNumber, steps);
    return steps;

}
0
Leon 28 sep. 2016 a las 11:41

El problema está aquí:

public int search(int number)
{

    int startingNumber = number;

    while (check.get(number)==null && number!=1){

        if (number%2==0){
            number = number / 2;
            result = search(number);
            result++;               
        }

        else {
            number = (3*number)+1;
            result = search(number);
            result++;
        }
    }

    if (check.get(startingNumber)!=null){
        result=result+check.get(number);
        check.put(startingNumber,result);

    }
    else{
        check.put(startingNumber,result);
    }

    return result;
}

Llamas a search (int) de forma recursiva y provoca apilamiento.

-1
Shaq 28 sep. 2016 a las 10:56

Aunque el código de recursividad es fácil y compacto en muchos casos, existe la posibilidad de desbordamiento de pila, especialmente si se desconoce la longitud de la cadena de recursividad.

Su caso es simple y se puede abordar fácilmente mediante iteraciones. Entonces, intente usar un modelo iterativo en lugar de un modelo recursivo.

0
Amber Beriwal 28 sep. 2016 a las 11:44