Java：找到Collat​​z序列中最大的鏈

Question

對於Project Euler問題＃14我找不到什麼問題。我的第一步是找到算法，直到數字達到120000左右爲止。代碼破譯並意識到我需要使用BigIntegers。我轉換我的算法以適應這種變化，但現在它不起作用。

我已經添加了System.out.print（chain_length）來幫助我在我的代碼可能會破壞的地方。

public static void main(String[] args) { 
    BigInteger target = new BigInteger("1000000"); 
    BigInteger n = new BigInteger("0"); 

    final BigInteger zero = new BigInteger("0"); 
    final BigInteger one = new BigInteger("1"); 
    final BigInteger two = new BigInteger("2"); 
    final BigInteger three = new BigInteger("3"); 
    final BigInteger ten = new BigInteger("10"); 

    int greatest_index = 0; 
    int greatest_length = 0; 
    int chain_length = 0; 

    BigInteger i = new BigInteger("2"); 
    for(i.equals(2) ; i.compareTo(target) == -1 ; i = i.add(one)) { 
     n = i; 
     chain_length = 1; 
     while(n.compareTo(one) == -1) { 
      chain_length++; 
      if(n.mod(ten).equals(zero) == true){//even 
       n = n.divide(two); 
      }else{//odd 
       n = n.multiply(three); 
       n = n.add(one); 
      } 
      if(n.equals(one) == true && chain_length > greatest_length){ 
       greatest_length = chain_length; 
       greatest_index = i.intValue(); 
      } 
     } 
     System.out.println(chain_length); 
    } 
    System.out.println(greatest_index);   
} 

Answer 1

要測試一個數字是否包括你正在使用模2，不10.更改這一行：

if(n.mod(ten).equals(zero) == true){//even 

要這樣：

if(n.mod(two).equals(zero)) { //even 

我也去掉了不必要的== true。

Answer 2

除了@MarkByers的回答，

while(n.compareTo(one) == -1) 

應該

while(n.compareTo(one) > 0) 

，或者在僞代碼，while n > 1。

你也應該採取

if(n.equals(one) == true && chain_length > greatest_length){ 
    greatest_length = chain_length; 
    greatest_index = i.intValue(); 
} 

跳出while循環，因爲n永遠等於one內循環。 （而且，由於後while循環n將always(?)等於one，你可以擺脫的首要條件完全。）

最後，i.equals(2)在

for(i.equals(2) ; i.compareTo(target) == -1 ; i = i.add(one)) 

沒有做什麼有用的 - 它只是返回false對於大多數的價值。

Answer 3

正如Daniel Fischer指出的那樣，您應該使用long。 小心不要做類似於
long a = 987654321。
正確的版本（如果你想長）：long a = 987654321L。
簡單的版本：

int maxChain = 0; 
    int answer = 0; 
    for (int i = 1_000_000; i > 0; i--) { 
     int chain = 0; 
     long n = i; 
     while (n != 1) { 
      if ((n & 1) != 1) { //Is even 
       n = n/2; 
       chain++; 
      } else { //Is odd 
       n = 3 * n + 1; 
       chain++; 
      } 
     } 
     if (chain > maxChain) { 
      maxChain = chain; 
      answer = i; 
     } 
    } 
    System.out.println(answer); 
    System.out.println(maxChain);