c++ 如何有效地从其根部找到多项式的系数？

参见英文答案 > Sum of multiplication of all combination of m element from an array of n elements 3

给定的是主导系数为1的多项式的n根.

如何有效地找出这个多项式的系数？

在数学上,

我知道如果第一个系数是1,那么一次取k产品根的总和将是多项式的第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;
}

我想到的是,为了更高系数的目的,我是否已经把它们加入到产品中,但是没有编写代码,因为如果多项式的程度很大,实际上是没有用的.

你需要计算线性因子的乘积

(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/2乘法和相似数量的减法.