多項式の係数をその根から効率的に見つける方法は？

Question

先導係数が1の多項式のnルーツがあります。 どうすれば効率的にこの多項式の係数を調べることができますか？数学的に

、 私は最初の係数が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系）

これはによって誘導実装することができます繰り返し線形因子

（[0] + [1]・X + ... + [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） + [M-1]・X^M、これはこれはn²/ 2の乗算の合計および乗算のための減算のような数を与える

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個の線形因子のうちの1つ。

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'th係数を計算する場合は、kネストループが必要であるという主な問題があります（1は第1係数で、第1係数ではないと仮定しています）。したがって、変数noを実装する必要があります。あなたのコードの入れ子のforループの私はあなたの問題の解決策を掲示しています。私は変数noを実装する方法を使用しました。ループの入れ子になっています。これがあなたの問題を解決することを願っています。

#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 

} 

私はコードをチェックしており、完全に動作しています。ネストされたforループの変数no.ofを実装する方法を知りたい場合は、variable nested for loopsにアクセスし、BugMeNot2013の答えを参照してください。