Как эффективно найти коэффициенты полинома от его корней?

Ответ 1

Вам нужно вычислить произведение линейных коэффициентов

(х-г1) · (х-z 2) ·... · (х-гп)

Это может быть реализовано индуктивно путем многократного умножения многочлена с линейным коэффициентом

(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

На месте это может быть реализовано как loop

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²/2 и такое же количество вычитаний для умножения всех n линейных факторов.

Ответ 2

Прежде всего, в С++ a[n] есть статический массив, поэтому компилятор должен знать n во время компиляции, что здесь не так. Таким образом, код "не правильный" в С++. Я знаю, что он будет компилироваться в gcc или других компиляторах, но это противоречит стандарту С++. См. С++ объявляет массив на основе непостоянной переменной? Здесь вам нужен динамический массив, используя команды new и delete, или вы можете использовать более безопасный класс std::vector от STL.

Теперь основная проблема заключается в том, что вам нужны k вложенные циклы, если вы хотите вычислить коэффициенты k'th (я принимаю 1, 0-й коэффициент, а не 1-й, только условный). Итак, вам нужно реализовать переменную no. вложенных для циклов в вашем коде. Я отправляю решение вашей проблемы, в котором я использовал метод для реализации переменной 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 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

}

Я проверил код, и он работает отлично. Если вы хотите знать, как реализовать переменную no.of вложенных для циклов, просто перейдите в переменную, вложенную для циклов, и посмотрите ответ BugMeNot2013.