項目歐拉14：問題與數組索引以一種新穎的解決方案

所討論的問題可以在http://projecteuler.net/problem=14 項目歐拉14：問題與數組索引以一種新穎的解決方案

找到我想要什麼，我認爲這是一個新的解決方案。至少這不是蠻力。我的解決方案適用於兩個假設：

1）你已經通過序列迭代次數少，更快，你會得到答案。 2）序列必然比它的每個元素

的的序列長些，因此我實現，可以出現在序列中的所有可能的數字的陣列。開始序列的最高數字是999999（因爲問題只會要求您測試少於1,000,000的數字）;因此，任何序列中可能出現的最高數字都是3 * 999999 + 1 = 2999998（這是偶數，因此序列中的下一個數字將被除以2）。所以陣列只需要這個尺寸。（在我的代碼中，數組實際上是2999999個元素，因爲我包含了0，因此每個數字都與它的數組索引匹配。但是，這不是必需的，它是爲了理解）。

所以一旦一個數是在一個序列中，它的陣列中的值變爲0。如果隨後的序列達到此值時，他們會知道不進一步進行任何的，因爲它假設他們會更長。

然而，當我運行代碼我得到以下錯誤，在該行中引入了「WH：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3188644

出於某種原因，它正試圖訪問上述值的索引，其中當不可因爲它超過了可能的最大值29999999.任何人都可以理解爲什麼會發生這種情況嗎？

請注意，我不知道我的假設是否真的很合適我是一名業餘程序員而不是數學家。我正在做實驗，希望我能夠在索引正確的時候確定它是否正常工作。

代碼如下：

private static final int MAX_START = 999999; 
private static final int MAX_POSSIBLE = 3 * MAX_START + 1; 

public long calculate() 
{ 
    int[] numbers = new int[MAX_POSSIBLE + 1]; 
    for(int index = 0; index <= MAX_POSSIBLE; index++) 
    { 
     numbers[index] = index; 
    } 

    int longestChainStart = 0; 

    for(int index = 1; index <= numbers.length; index++) 
    { 
     int currentValue = index; 


     if(numbers[currentValue] != 0) 
     { 
      longestChainStart = currentValue; 

      while(numbers[currentValue] != 0 && currentValue != 1) 
      { 
       numbers[currentValue] = 0; 

       if(currentValue % 2 == 0) 
       { 
        currentValue /= 2; 
       } 
       else 
       { 
        currentValue = 3 * currentValue + 1; 
       } 
      } 
     } 
    } 

    return longestChainStart; 
}

來源

2012-03-05 Swiftslide

我懷疑，如果你打印出CurrentValue的每個時間的價值很明顯（ISH）解決這個問題。打印可能需要一點時間，但我認爲你只是在增加目前的價值，因爲你已經達到了最高值的三分之一以上的奇數。 – Joel 2012-03-05 08:54:35

我不明白爲什麼你認爲2999998是最大可能的數字...如果你開始在999999，你會得到：999999 - > 2999998 - > 1499999 - > 4499998，但4499998> 2999998 ... – Sorin 2012-03-05 10:32:18

我正在實現那現在。出於某種原因，儘管如此，因爲奇怪的事情會變得平均，它會再次減少，一切都會好的。沒有想到這樣一個事實，即漲幅遠大於跌幅。感謝你們兩位指出這一點。 – Swiftslide 2012-03-05 21:49:56

既然你不能（容易）把限制上的一系列可能的最大數量，你可能想嘗試不同的方法。我可能會建議基於memoization的東西。

假設你有一個大小爲1,000,000的數組。每個條目i將表示從i到1的序列長度。記住，您不需要序列本身，而只需要序列的長度。你可以從1開始填充表格 - 長度爲0.從2開始，你的長度爲1，依此類推。現在，說我們正在查看條目n，這是偶數。您可以查看條目n/2處的序列長度，並在n處將值加1即可。如果您還沒有計算n/2，只需進行正常計算，直到達到您計算的值。如果n是奇數，則類似的過程成立。

這應該把你的算法的運行時間下來顯著，並防止越界 - 錯誤的任何問題。

來源

2012-03-14 16:18:05 Peter

您可以通過這種方式

import java.util.LinkedList; 
public class Problem14 { 

public static void main(String[] args) { 

LinkedList<Long> list = new LinkedList<Long>(); 
long length =0; 
int res =0; 
for(int j=10; j<1000000; j++) 
{ 
    long i=j; 
    while(i!=1) 
    { 
     if(i%2==0) 
     { 
      i =i/2; 
      list.add(i);  
     } 
     else 
     { 
      i =3*i+1;  
      list.add(i); 
     }  
    } 
if(list.size()>length) 
    { 
    length =list.size(); 
    res=j; 
    } 
    list.clear(); 

} 
System.out.println(res+ " highest nuber and its length " + length); 

}}

來源

2013-03-06 09:44:13 Arvind

項目歐拉14：問題與數組索引以一種新穎的解決方案

回答

相關問題