c++ - 穷举(蛮力)算法改进

Question

我从以下要求开始:

m,n 是整数。用

搜索(x,y,z)

• x+y+z=n
• x^3 + y^3 + z^3 = m

还有我的代码

for(int x = 1; x<n; x++)
{
   for(int y = 1; y<n; y++)
   {
      for(int z=1; z<n; z++)
      {
         if((x*x*x + y*y*y + z*z+z*z == m) &&(x+y+z==n))
         {
             cout<<x<<"  "<<y<<"  "<<z;
         }
      }
   }
}

BigO = n^3

使用上面的 block 代码，算法非常慢。您知道如何提高速度吗？

Answer 1

不需要内循环；给出x和 y , 你可以拿z = n-x-y .这将它减少到 O(n^2) .

第二个循环只需要循环while x+y<n ，因为除此之外没有积极的 z这样 x+y+z==n .这将剩余工作减半。

完成此操作后，无需进行第二次测试(因为您已经选择了 z 来实现)；修正第一个测试中的拼写错误，你会得到

for (int x = 1; x<n; x++) {
    for (int y = 1; x+y<n; y++) {
        int z = n-x-y;
        if (x*x*x + y*y*y + z*z*z == m) {
            // found it
        }
    }
}