使用整數和雙打給出不同的答案，當他們不應該

我正在用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

@山貓：謝謝！我很高興它有幫助。 :-) –

使用整數和雙打給出不同的答案，當他們不應該

回答

相關問題