我可以使關於EulerProblem的代碼更快嗎？

Question

我寫了一個程序，必須找到歐拉問題的解決方案。我想訓練我的程序技巧，這就是爲什麼我已經簽署了歐盟。

這就是問題：

甲勾股數是一組三個自然數，一個< b <的C，爲此， 一個^ 2 + B^2 = C^2

對於例如，3^2 + 4^2 = 9 + 16 = 25 = 5^2。

只存在一個畢達哥拉斯三元組，其中a + b + c = 1000. 查找產品abc。

這是我的代碼，但它運行得很慢，需要幾個小時才能給我正確的abc。

static int findTriplet(int getal) 
{ 
    boolean test = false; 
    for(int a = 1; !test; a++) 
     for(int b = a+1; !test; b++) 
      for(int c = b+1; !test; c++) 
      { 
       if(a*a + b*b == c*c) 
       { 
        if(a+b+c == getal) 
        { 
         return (a*b*c); 
        } 
       } 

      } 
    return 0; 
} 

是否有可能使代碼更快或者是正常的，它需要時間？

親切的問候，

編輯：

感謝您的幫助。 ！測試布爾是無用的抱歉，這工作：這個作品：

static int findTriplet(int getal) 
{ 
    for(int a = 1; a < 1000; a++) 
     for(int b = a+1; b < 1000; b++) 
      for(int c = b+1; c < 1000; c++) 
      { 
       if(a*a + b*b == c*c) 
       { 
        if(a+b+c == getal) 
        { 
         return (a*b*c); 
        } 
       } 

      } 
    return 0; 
} 

我也寫了一個haskell變種，也是伎倆。

認爲這在Haskell中更容易，效率更高。

Thaks的提示。

Answer 1

爲了優化這個天真的算法，你必須先明白：

1. 你實際的源代碼不會停止的。它會運行，只要測試是false。您也冒險遇到c的溢出。
2. 嘗試a，b和c的每種可能組合都會導致嘗試1000 * 999 * 988 = 997 002 000次（！）。
3. 在這個算法的關鍵點是：在循環
   • 停止條件
   • 辦法找下一個嘗試
   • 方式來降低循環如果可能的話

現在，你知道你需要：

1. 想辦法避開第稅務局環，使用你的問題的條件
2. 想方設法增加A和B更巧妙地利用你的問題的條件
3. 想方設法更早停止循環，使用你的問題的條件

這裏有一些方便的優化提示：

• 作爲阿米特& sirko說，你猜ç如果你已經知道一個和b。
• 你並不需要你檢查新型B
• 你並不需要檢查，直到< 1000和b < 999每次重新計算A * A，有遠不如種可能的組合

而且一些提示困難的優化：

• 你不需要重新計算b *每個時間b太
• 你並不需要瀏覽每一個可能的組合

Answer 2

最後for是多餘的，你可以找到c = sqrt(a^2 + b^2)，這會使你的算法快得多。

其實你只需要檢查是否有在Nc [自然數]這樣sqrt(a^2 + b^2) = c，並檢查是否a+b+c == 1000

這optmization會讓你更快的解決方案，而不是O(n^2)O(n^3)，1000倍！

編輯：正如在評論中討論：

1. 有可能是一個更快的解決方案，然後檢查c = sqrt(a^2 + b^2)：c = 1000 - a -b，但重要的部分是做什麼的O(n^2)，而不是O(n^3)。
2. 這個答案是更準則，然後一個完整的答案。你的循環的停止條件需要做更多的工作。這個答案的目的只是爲了讓你知道如何以更快的速度完成它。

Answer 3

看一個高大而薄的直角三角形，底部爲a，高度爲b，斜邊爲c。 第一個a和b總是小於c和c = sqrt(a*a+b*b)所以如其他海報所說，您只需要搜索a和b。 你也知道a+b >= c所以沒有必要去看小a,b對。

現在，假設你開始a=0, b=500，所以c==500，總周長爲1000 現在增加1 a並計算周長。它會超過1000. 然後你減少b 1.然後周長將會略小於1000. 然後增加a 1，直到周長再次大於1000。

所以，只要外圍是< = 1000，就增加a。 只要它> 1000，減少b。 如果它等於1000，那麼你有一個答案。然後繼續。

只要a<b您只需要這樣做。

該算法應該是O(N)，因爲它不會浪費時間與小對。

然後你所要做的就是向自己證明它不會錯過任何答案。 你這樣做，假設有一個有效的a,b答案，它確實錯過了，並表明這是不可能的。