优化Collatz序列

Question

我在euler.net项目中一直在努力工作。

我最近解决了问题14-请参阅这里获得完整的描述

这是代码

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的。

Answer 1

您需要使用HashMap来避免多次重新计算相同的数字。检查HashMap是否已经包含了数字是一个快速的过程，可以为您节省许多步骤。

例如:如果你第二次进入数字200,000，你已经知道在Collatz序列中还有多少步骤。