5

我正在使用 java解决 Project Euler问题 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 整除。所以我认为使用整数是完全安全的。我没看到什么？

这是完整的代码，如果您想亲自查看，请复制、粘贴并运行它。尽管有很多迭代，但它会在几秒钟内运行。=)

4

1 回答 1

10

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

请记住：序列中的数字可能非常大。如此之大，它们超出了int的范围。但不是（在这种情况下）double's 或long's。

在链中的某一点，n是827,370,449，你跟随3n + 1分支。该值想要成为2,482,111,348，但它溢出了int（2,147,483,647在积极领域中）的容量并带您到-1,812,855,948。事情从那里往南走。:-)

因此，您认为整数（我应该说整数）数字会很好的理论是正确的。但他们必须有能力完成这项任务。

于 2013-06-20T22:51:03.883 回答