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

栏目: C++ · 发布时间: 6年前

内容简介:http://stackoverflow.com/questions/33067755/how-to-efficiently-find-coefficients-of-a-polynomial-from-its-roots

参见英文答案 > 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乘法和相似数量的减法.

http://stackoverflow.com/questions/33067755/how-to-efficiently-find-coefficients-of-a-polynomial-from-its-roots


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Is Parallel Programming Hard, And, If So, What Can You Do About

Is Parallel Programming Hard, And, If So, What Can You Do About

Paul E. McKenney

The purpose of this book is to help you understand how to program shared-memory parallel machines without risking your sanity.1 By describing the algorithms and designs that have worked well in the pa......一起来看看 《Is Parallel Programming Hard, And, If So, What Can You Do About 》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换