java - 我怎样才能避免 java.lang.StackOverflowError :null?

Question

我正在尝试自学一点 Java通常我有足够的资源和像这样的好网站，但现在我只想知道我错在哪里。

所以问题被表述为:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even) n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

我不断收到这些 java.lang.StackOverflowError，有人可以帮助我吗？我的代码:

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;
    }


}

编辑:

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;
    }
}

编辑2:因此，在编辑版本代码中，我从机器中卡住了，但是当我将 int 更改为 long 时，它工作得很好，尽管我知道使用一些 Map 来存储值，您可以更快地找到它。谢谢大家!!

Answer 1

问题是，你有太多的递归调用。对此的最佳解决方案是使代码迭代。只需重做您的 while循环首先检查是否已经找到该号码，如果是，则返回到达该号码所需的步骤总和，并且从该号码到达 1 需要花费的时间。 。否则，只需更新下一步的编号，再次运行循环。同时，您只需跟踪获得已知数字所需的步骤即可。

就我个人而言，我会删除 HashMap总共只有一个简单的while环形:

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

编辑:如果您想添加 HashMap要存储找到的值，您可以这样做(我假设您之前定义了一个名为 HashMap<Long, Integer> 的 foundNumbers ):

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;

}