java - 欧拉项目 14 : Issue with array indexing in a novel solution

Question

有问题的问题可以在 http://projecteuler.net/problem=14 找到

我正在尝试我认为新颖的解决方案。至少不是蛮力。我的解决方案基于两个假设:

1) 迭代序列的次数越少，得到答案的速度就越快。 2) 序列必然比其每个元素的序列长

所以我实现了一个包含序列中可能出现的所有可能数字的数组。开始序列的最大数字是 999999(因为该问题只要求您测试小于 1,000,000 的数字)；因此，任何序列中的最大可能数字是 3 * 999999 + 1 = 2999998 (这是偶数，因此将除以 2 以获得序列中的下一个数字)。所以数组只需要这个大小。 (在我的代码中，数组实际上是 2999999 个元素，因为我包含了 0，以便每个数字与其数组索引相匹配。但是，这不是必需的，它是为了理解)。

因此，一旦一个数字进入序列，它在数组中的值就会变为 0。如果后续序列达到该值，它们将知道不再继续进行，因为假设它们会更长。

但是，当我运行代码时，在引入“wh:”的行中出现以下错误:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3188644

出于某种原因，它试图访问上述值的索引，但该索引不应该访问，因为它超过了可能的最大值 29999999。任何人都可以理解为什么会发生这种情况吗？

请注意，我不知道我的假设是否正确。我是一名业余程序员，而不是数学家。我正在尝试。希望一旦索引正确，我就能知道它是否有效。

代码如下:

private static final int MAX_START = 999999;
private static final int MAX_POSSIBLE = 3 * MAX_START + 1;

public long calculate()
{
    int[] numbers = new int[MAX_POSSIBLE + 1];
    for(int index = 0; index <= MAX_POSSIBLE; index++)
    {
        numbers[index] = index;
    }

    int longestChainStart = 0;

    for(int index = 1; index <= numbers.length; index++)
    {
        int currentValue = index;


        if(numbers[currentValue] != 0)
        {
            longestChainStart = currentValue;

            while(numbers[currentValue] != 0 && currentValue != 1)
            {   
                numbers[currentValue] = 0;

                if(currentValue % 2 == 0)
                {
                    currentValue /= 2;
                }
                else
                {
                    currentValue = 3 * currentValue + 1;
                }
            }
        }
    }

    return longestChainStart;
}

Answer 1

鉴于您无法(轻松)限制序列的可能最大数量，您可能需要尝试不同的方法。我可能会建议一些基于内存的东西。

假设您有一个大小为 1,000,000 的数组。每个条目 i 将表示从 i 到 1 的序列长度。请记住，您不需要序列本身，而只需要序列的长度。您可以从 1 开始填写表格——长度为 0。从 2 开始，长度为 1，依此类推。现在，假设我们正在查看条目n，它是偶数。您可以查看条目 n/2 处的序列长度，然后将 n 处的值加 1。如果您还没有计算n/2，只需进行正常计算，直到得到计算出的值。如果 n 为奇数，则类似的过程成立。

这应该会显着缩短算法的运行时间，并防止任何越界错误的问题。