有问题的问题可以在 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;
}
最佳答案
鉴于您无法(轻松)限制序列的可能最大数量,您可能需要尝试不同的方法。我可能会建议一些基于内存的东西。
假设您有一个大小为 1,000,000 的数组。每个条目 i
将表示从 i
到 1 的序列长度。请记住,您不需要序列本身,而只需要序列的长度。您可以从 1 开始填写表格——长度为 0。从 2 开始,长度为 1,依此类推。现在,假设我们正在查看条目n
,它是偶数。您可以查看条目 n/2
处的序列长度,然后将 n
处的值加 1。如果您还没有计算n/2
,只需进行正常计算,直到得到计算出的值。如果 n
为奇数,则类似的过程成立。
这应该会显着缩短算法的运行时间,并防止任何越界错误的问题。
关于java - 欧拉项目 14 : Issue with array indexing in a novel solution,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9563831/