我可以使关于EulerProblem的代码更快吗？

我写了一个程序，必须找到欧拉问题的解决方案。我想训练我的程序技巧，这就是为什么我已经签署了欧盟。我可以使关于EulerProblem的代码更快吗？

这就是问题：

甲勾股数是一组三个自然数，一个< 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的提示。

来源

2012-02-18 user1007522

为什么使用'！test'作为循环控制表达式？ – 2012-02-18 10:45:15

也许你可以接受你过去的问题的一些答案。 – Coren 2012-02-18 10:45:17

你不会打破最内层的循环，所以它永远循环一次= 1，b = 2。 – soulcheck 2012-02-18 10:45:43

为了优化这个天真的算法，你必须先明白：

你实际的源代码不会停止的。它会运行，只要测试是false。您也冒险遇到c的溢出。
尝试a，b和c的每种可能组合都会导致尝试1000 * 999 * 988 = 997 002 000次（！）。
在这个算法的关键点是：在循环
- 停止条件
- 办法找下一个尝试
- 方式来降低循环如果可能的话

现在，你知道你需要：

想办法避开第税务局环，使用你的问题的条件
想方设法增加A和B更巧妙地利用你的问题的条件
想方设法更早停止循环，使用你的问题的条件

这里有一些方便的优化提示：

作为阿米特& sirko说，你猜ç如果你已经知道一个和b。
你并不需要你检查新型B
你并不需要检查，直到< 1000和b < 999每次重新计算A * A，有远不如种可能的组合

而且一些提示困难的优化：

你不需要重新计算b *每个时间b太
你并不需要浏览每一个可能的组合

来源

2012-02-18 10:54:38 Coren

这个问题被标记为'家庭作业'，因为标签维基说：'不要问'完整'的解决方案的问题;我们不是在这里为你做家庭作业。“家庭作业标记问题的答案不应该是完整答案 - 而是提示和指导方针。 – amit 2012-02-18 10:57:41

这不会强制 2012-02-18 10:58:20

+0

我想你是对的。我会纠正这一点。 – Coren 2012-02-18 10:59:36

1

最后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倍！

编辑：正如在评论中讨论：

有可能是一个更快的解决方案，然后检查c = sqrt(a^2 + b^2)：c = 1000 - a -b，但重要的部分是做什么的O(n^2)，而不是O(n^3)。

这个答案是更准则，然后一个完整的答案。你的循环的停止条件需要做更多的工作。这个答案的目的只是为了让你知道如何以更快的速度完成它。

来源

2012-02-18 10:46:34 amit

+2

'c = 1000 - a - b'，然后检查'a * a + b * b == c * c'是否应该更快。 – Sirko 2012-02-18 10:48:32

+0

它仍然会增加b永远a = 1 – Coren 2012-02-18 10:49:01

+0

@Sirko：是真的，但不是数量级。重要的是要消除最后一个循环，无论如何使解决方案成为“O（n^2）”。 – amit 2012-02-18 10:50:48

0

看一个高大而薄的直角三角形，底部为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答案，它确实错过了，并表明这是不可能的。

来源

2012-02-18 14:51:16

我可以使关于EulerProblem的代码更快吗？

回答

相关问题