如何高效地从多项式的根中找到系数？

Question

给定一个首项系数为1的多项式，它有 n 个根。如何高效地找到这个多项式的系数呢？

从数学上讲，如果第一项系数是1，那么取 k 个根的积的和将是多项式的第 k+1 项系数。

我的代码就是基于这个方法。

换句话说，如何最优地找出从列表中取出 k 个数的积的和。

int main()
{

    int n, sum;
    cin >> n;
    int a[n];
    for (int i=0; i<n; i++) cin >> a[i];
    //for the second coefficient
    sum=0;
    for (int i=0; i<n; i++)
    {
        sum+=a[i];
    }
    cout << sum << endl;
    //for the third coefficient
    sum=0;
    for (int i=0; i<n; i++)
    {
        for (int j=i+1; j<n; j++)
        {
            sum+=a[i]*a[j];
        }
    }
    cout << sum << endl;
}

为了提高系数，我考虑将数字标记为是否已经包含在产品中，但是如果多项式的次数很大，实际上这个想法没有什么用处，所以我并没有编写相关代码。

- anukul

---

如果我没记错的话，直接计算多项式的时间复杂度是O(n^2)。 - n. m.

请看我在这里的回答：https://dev59.com/rX_aa4cB1Zd3GeqP33sM#23537841。 - MBo

谢谢@MBo。无法将评论标记为答案。您能添加一个答案吗？（使用伪代码/Python/C++）？我不理解那段代码中的SetLength函数。 - anukul

@MBo 这个 Delphi 代码的实现是否正确？http://pastebin.com/Lyqya3N8 - anukul

是的。请注意，答案是针对单个系数的，但您需要所有系数，输出“coeff”数组。因此，您不需要“int m”参数，并添加额外的循环来否定交替系数，而不是返回子句。 - MBo

Answer 1

您需要计算线性因数的乘积

(x-z1)·(x-z2)·…·(x-zn)

可以通过反复将多项式与线性因数相乘来实现归纳。

(a[0]+a[1]·x+…+a[m-1]·x^(m-1))·(x-zm)

= (-a[0]·zm) + (a[0]-a[1]·zm)·x + … + (a[m-2]-a[m-1]·zm) ·x^(m-1) + a[m-1]·x^m

在原地，这可以作为循环实现。

a[m] = a[m-1]
for k = m-1 downto 1
    a[k] = a[k-1] - a[k]*zm
end
a[0] = -a[0]*zm

这意味着对于所有n个线性因式的乘法，将需要n²/2次乘法和相同数量的减法。

- Lutz Lehmann

Answer 2

首先在C++中，a[n]是一个静态数组，所以编译器需要在编译时知道n的值，而这里并非如此。因此，在C++中，该代码是“不正确”的。我知道它可以在gcc或其他编译器中编译，但这违反了C++标准。请参见C++ declare an array based on a non-constant variable?。在这里，您需要使用动态数组，使用new和delete命令，或者您可以使用更安全的STL中的std::vector类。

现在，这里的主要问题是，如果您想要计算第k个系数（我假设1是0th系数，而不是1st，只是习惯），则需要k个嵌套循环。因此，您需要在代码中实现可变数量的嵌套for循环。我将发布解决您问题的解决方案，其中我使用了一种方法来实现可变数量的嵌套for循环。希望这能解决您的问题。

#include <iostream>
#include <cmath>
#include <vector>  // include vector class

using namespace std;

double coeff(int,const vector<double>& );  // function declaration to to calculate coefficients

int main()
{

  int N = 5; // no. of roots

  // dynamic vector containing values of roots
  vector<double> Roots(N); 
  for(int i = 0 ; i<N ; ++i)
    Roots[i] = (double)(i+1);  // just an example, you can use std::cin


  int K = 2;  // say you want to know K th coefficient of the polynomial

  double K_th_coeff = coeff(K,Roots); // function call

  cout<<K_th_coeff<<endl; // print the value

  return 0;
}


double coeff(int k,const vector<double>& roots)
{

  int size = roots.size(); // total no. of roots

  int loop_no = k; // total no. of nested loops
  vector<int> loop_counter(loop_no+1); // loop_counter's are the actual iterators through the nested loops
  // like i_1, i_2, i_3 etc., loop_counter[loop_no] is needed to maintain the condition of the loops

  for(int i=0; i<loop_no+1; ++i)
    loop_counter[i]=0;   // initialize all iterators to zero


  vector<int> MAX(loop_no+1); // MAX value for a loop, like  for(int i_1=0; i_1 < MAX[1]; i++)... 
    for(int i=0 ; i<loop_no ; ++i)
      MAX[i] = size - loop_no  + i + 1; // calculated from the algorithm

    MAX[loop_no]=2; // do'es no matter, just != 1

    int  p1=0; // required to maintain the condition of the loops

    double sum(0); // sum of all products

    while(loop_counter[loop_no]==0)
    {
      // variable nested loops starts here

      int counter(0);
      // check that i_1 < i_2 < i_3 ....
      for(int i = 1 ; i < loop_no; ++i)
      {
        if(loop_counter[i-1] < loop_counter[i])
          ++counter;
      }


      if(counter == loop_no - 1) // true if i_1 < i_2 < i_3 ....
      {
        double prod(1);
        for(int i = 0 ; i < loop_no ; ++i)  
          prod *= roots[loop_counter[i]];   // taking products

        sum += prod;  // increament
      }


    // variable nested loops ends here...


    ++loop_counter[0];
    while(loop_counter[p1]==MAX[p1])
      {
        loop_counter[p1]=0;
        loop_counter[++p1]++;
        if(loop_counter[p1]!=MAX[p1])
          p1=0;
      }
    }

    return pow(-1.0,k)*sum;   // DO NOT FORGET THE NEGATIVE SIGN

}

我已经检查了代码，它完美地运行。如果你想知道如何实现可变数量的嵌套循环，请访问可变嵌套循环并查看BugMeNot2013的答案。

- Titas Chanda