我一直在project-euler.net上努力工作
我最近解决了问题14-请参见here以获取完整描述
这是密码
public static void findHighestCollatzNumber()
{
long greatestNumberOfTerms=0;
long highestTermNumber=0;
for(int i=1;i<=ONE_MILLION;i++)
{
long noOfTerms=getNumberOfCollatzTerms(i);
if(noOfTerms>greatestNumberOfTerms)
{
greatestNumberOfTerms=noOfTerms;
highestTermNumber=i;
}
}
System.out.println("highest number of term "+greatestNumberOfTerms + " for "+highestTermNumber);
}
public static long getNumberOfCollatzTerms(long n)
{
long numberOfTerms=1;
long i=n;
do
{
i=calculateCollatz(i);
if(i>0)
{
numberOfTerms++;
}
}
while(i!=1 && i>0);
return numberOfTerms;
}
public static long calculateCollatz(long n)
{
long collatz=0;
if(n%2==0)
{
collatz=n>>1;
}
else
{
collatz=(n<<1)+1+n;
}
return collatz;
}
它给出了正确的输出,但它需要大量的计算时间
我也尝试过使用按位运算来获得更快的输出,但仍然需要时间,我如何才能减少它?
我已经研究了其他的解决方案,但是发现它们大部分是GHC或C++或Python。
最佳答案
您需要使用HashMap
来避免多次重新计算相同的数字。检查hashmap是否已经包含该数字是一个快速的过程,可以为您节省许多步骤。
例如:
如果你第二次达到200000,你已经知道在collatz序列中还有多少步了。