優化在Collatz序列

我一直在工作我的方式在project-euler.net優化在Collatz序列

我最近解決的問題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。

來源

2014-01-14 nub1-O-8

將以前計算的結果存儲在數據結構中，而不是每次重新計算它們。 –

你會想要使用HashMap來避免多次重新計算相同的數字。檢查HashMap是否已經包含這個數字是一個快速的過程，並且可以爲您節省很多步驟。

例如：如果第二次獲得數字200,000，您已經知道Collatz序列中還有多少步驟。

來源

2014-01-14 17:52:31

但不是那個是爲那個具體的數字爲例如200,000而不是其他數字 –

nub1-O-8：是的，但你已經知道了你需要多少步驟來達到這個數字。在這一點上，它只是一個附加的問題。 –

優化在Collat​​z序列

回答

相關問題

優化在Collatz序列