如何从多项式的根有效地找到它的系数？

Question

给定n多项式的根，该多项式的前导系数为1。如何 有效地 找出该多项式的系数？

从数学上讲，我知道如果第一个系数为1，则k一次取乘积根的总和k+1-th就是多项式的系数。

我的代码基于这种方法。

换句话说，如何从一次获取的列表中最佳地找到数字乘积之和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;
}

我曾经考虑过要为是否需要更高的系数而将数字记入产品中，但没有为它写代码，因为如果多项式的次数很大，这实际上是没有用的。

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乘法和相减的次数。