使用整数和双打给出不同的答案，当他们不应该

我正在用java解决项目欧拉Problem 14。我不是在寻求解决问题的帮助。我已经解决了它，但我遇到了一些我无法弄清楚的东西。使用整数和双打给出不同的答案，当他们不应该

的问题是这样的：

以下迭代序列对于该组正整数定义：

N = N/2，当n为偶数
N = 3N + 1，如果n是奇数

使用上述规则，并用13开始，我们生成以下序列：

13→40→20→10→5→16→8→4→2→1.在这里，链的长度是10个数字。

查找低于1,000,000的起始数字，生成最长的链。

所以我写了这个代码：

public class Euler014 { 
    public static void main(String[] args){ 
     int maxChainCount = 0; 
     int answer = 0; 
     int n; 
     int chainCount = 1; 

     for(int i = 0; i < 1000000; i++){ 
      n = i; 
      while(n > 1){ 
       if(n%2 == 0){  //check if even 
        n /= 2; 
       }else{    //else: odd 
        n = 3*n + 1; 
       } 
       chainCount++; 
      } 
      if(chainCount > maxChainCount){ //check if it's the longest chain so far 
       maxChainCount = chainCount; 
       answer = i; 
      } 
      chainCount = 1; 
     }  
     System.out.println("\n\nLongest chain: i = " + answer);  
    } 
}

这给了我答案910107，这是不对的。但是，如果我改变我的n变量的类型为double n它运行并给我答案837799，这是正确的！

这真让我困惑，因为我看不出会有什么不同。我明白，如果我们使用int并进行分组，我们可以在我们不打算的时候舍入数字。但在这种情况下，我们总是检查看看n是否可以除以2，然后除以2.所以我认为使用整数是完全安全的。我没有看到什么？

这是整个代码，复制，粘贴并运行它，如果你想亲自看看。它在几秒钟内运行，尽管迭代很多。 =）

来源

2013-06-20 Goatcat

'int'太小，会溢出几个值。使用'长'。 –

经过121步后，你得到'int'溢出的第一个值是'113383'。 59步之后'837799'溢出。 –

您的问题溢出。如果您将int n更改为long n，您将得到正确答案。

请记住：序列中的数字可以是真的很大。如此之大，他们溢出int的范围。但不是（在这种情况下）double或long's。

在链中的某一点，n是827,370,449并且您按照3n + 1分支。该值希望为2,482,111,348，但它溢出的容量为int（在积极领域为2,147,483,647），并且带您到-1,812,855,948。事情从那里南下。 :-)

所以你的理论，你会很好整数（我应该说积分）号码是正确的。但他们必须有能力完成这项任务。

来源

2013-06-20 22:51:03

这是一个很好的答案。在保持简单易懂的同时，真正详细解释。谢谢！ – Goatcat

@山猫：谢谢！我很高兴它有帮助。 :-) –

使用整数和双打给出不同的答案，当他们不应该

回答

相关问题