polynomial-math - 求解有限变量中的多项式方程

Question

一个简单的问题。问题是求解这样一个整数多项式方程：x+y+z=num，x,y,z的int值应该是这样的：X1<=x<=X2,Y1<=y< =Y2, Z1<=z<=Z2 ，然后找出满足该方程的 x,y,z 组合的数量。可能有比这更有效的算法：

for(int i=X1;i<=X2;i++)
    for(int j=Y1;j<=Y2;j++)
        for(int k=Z1;k<=Z1;k++)
            if(i+j+z==num)
                print i,j,k;

我不是要代码，而是要想法。感谢任何提供有用信息的人！

Answer 1

您的算法在 O((X2-X1)(Y2-Y1)(Z2-Z1)) 时间内运行。

为了让它更快，你可以让它检查总和是否大于 num，如果是，那么你可以跳出你所在的循环并增加下一个更大的循环。例如，Y 循环可以读取

for(int j = Y1; j <= Y2; j++){
    if(i + j > num){
          j = Y2;
          continue;
    }
    for ( int k = Z1;...){...}
}

这将阻止算法测试一些大于 num 的组合，从而提高运行时间。请注意，您可以对所有三个循环执行此操作，仅包括到目前为止已定义的变量（此示例不测试 k，因为直到第三个循环才定义 k）。