我可以更快地制作关于EulerProblem的代码吗？

Question

我编写了一个必须找到EulerProblem解决方案的程序.我想训练我的程序技能,这就是我注册欧拉的原因.

这就是问题:

毕达哥拉斯三元组是一组三个自然数,a <b <c,其中a ^ 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;
}

是否可以使代码更快或者是否需要数小时？

亲切的问候,

编辑:

谢谢你的帮助.!test boolean对此无效,这很有效:

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中更容易,效率更高.

想要提示.

Answer 1

为了优化这种天真的算法,您首先要了解:

1. 您的实际源代码根本不会停止.只要测试,它就会运行false.你也冒险遇到溢出c.
2. 尝试a,b和c的每种可能组合将导致尝试1000*999*988 = 997 002 000次(!).
3. 该算法的关键点是:
   • 在循环中停止条件
   • 寻找下一个尝试的方法
   • 如果可能的话减少循环的方法

现在,你知道你需要:

1. 找到避免第三次循环的方法,使用问题的条件
2. 找到使用问题条件更聪明地增加a和b的方法
3. 找到使用问题条件提前停止循环的方法

以下是一些易于优化的提示:

• 作为阿米特和sirko说,你猜Ç如果你已经知道一个和b.
• 每次检查新b时,都不需要重新计算*a
• 在<1000和b <999之前,您不需要检查,组合的可能性要小得多

以及一些更难以优化的提示:

• 您不需要每次都重新计算b*b
• 您不需要浏览所有可能的组合