的Java：堆空間錯誤，歐拉項目14

我試圖解決project Euler problem number 14：的Java：堆空間錯誤，歐拉項目14

以下迭代序列爲正整數的集合定義：

ñ→N/2（ñ是偶數）

ñ→3N + 1（ñ爲奇數）

使用上述規則，並用13開始，我們產生以下序列：

13→40→20→10→5→16→8→4→2→1

可以看出，該序列（從13開始並在1結束）包含10個術語。儘管還沒有被證明（Collatz問題），可以認爲所有起始數字都是1.

哪一個起始數字低於一百萬，會產生最長的鏈？

注：一旦鏈條開始，條款允許超過100萬。

這是我的方法：

public class Euler14 { 

public static void main(String[] args) { 
    int temp = 0; 
    ArrayList<Integer> numbers = new ArrayList<>(); 
    ArrayList<Integer> numberOf = new ArrayList<>(); 

    for(int i = 2; i<1000000; i++) { 

     numbers.add(i); 
     temp = i; 

     while(i!=1) { 

      if(i%2==0) { 
       i = i/2; 
      } 

      else{ 
       i = (3*i)+1; 
      }      

      numbers.add(i);     
     } 

      numberOf.add(numbers.size()); 
      Collections.sort(numberOf); 

      if(numberOf.size()>1) { 
       numberOf.remove(0); 
      } 
      numbers.clear(); 
      i = temp; 

      System.out.println("Starting number " + i + "\n" + 
           "Size: " + numberOf + "\n"); 
    }  
}  
}

但是，在運行該程序時我在i = 113282得到這個錯誤：

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

我能做什麼來解決這個錯誤，我該如何改進我的代碼？

來源

2016-01-31 samtob

你最直接的問題是，你再次修改循環裏面的'i'變量。所以你現在不會傳遞2到1000000之間的所有值。另一個提示：如果你已經知道，從13開始的collatz序列長度爲10，你不能用這個事實來計算26的長度嗎？ – Sirko

我明白你的觀點。這是否意味着沒有必要檢查小於500 000的數字？由於2的乘法會導致長度增加1 =>沒有小於500 000的數字會比大於500 000的數字產生更長的collatz序列？ – samtob

沒有。但是，您可以使用查找，將結果保存到計算中。所以當你計算一個序列時，對於每一個新的數字，如果這個數字已經存在，查看這個查找。如果喲，你可以停止並使用現有的結果。您也可以將您在單個序列中遇到的所有數字與它們各自的結果相加。 – Sirko

您得到OutOfMemoryError的原因是序列中某些數字的大小太大而無法存儲在32位Java整數中。因此發生算術溢出並且while循環不會終止（直到列表變得太大並且超過堆空間）。

如果您使用longs而不是整數，您的代碼應該運行完成。

但是，您不需要存儲所有數字。所有你需要跟蹤的是最好的起點和迄今爲止所看到的最長序列的長度。我傾向於提取一個方法/函數，它取一個起始值並返回從那開始的Collatz序列的長度。

來源

2016-01-31 12:27:08

有可能通過使用命令行選項來增加由JVM分配的堆大小：

-Xms<size>  initial Java heap size 
-Xmx<size>  maximum Java heap size

認爲這隻會在你的問題移動。例如，而不是113282，它可能會達到1000,000。

來源

2016-01-31 10:43:46

你走了，沒有優雅的書面，但工作。:)

public static void main(String [] args){ 
    long temp = 1; 
    int MAX = 13; 
    int count = 0; 
    long maxCount = 0; 
    long maxNumber = 0; 
    for(long i = 1000000;i >= 1; i--){ 
     count = 0; 
     temp = i; 
     while(temp != 1){ 
      count++; 
      if(temp % 2 == 0){ 
       temp = temp/2; 
      }else{ 
       temp = temp*3 +1; 
      } 
     } 
     if(maxCount <= count){ 
      maxCount = count; 
      maxNumber = i; 
     } 
     System.out.println("Number : "+i+" count : "+count); 
    } 
    System.out.println("Max Number : "+maxNumber +" Count : "+maxCount); 
}

來源

2016-01-31 14:53:20

的Java：堆空間錯誤，歐拉項目14

回答

相關問題