अपनी जड़ों से बहुपद के गुणांक को कुशलता से कैसे ढूंढें?

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

आप रैखिक कारकों

के उत्पाद की गणना करने की जरूरत है

(एक्स z1) · (एक्स z2) · ... · (एक्स Zn)

इस उपपादन द्वारा लागू किया जा सकता बार-बार एक रेखीय कारक

साथ एक बहुपद गुणा (क [0] ने एक [1] · x + ... एक [एम-1] · x^(एम-1)) · (एक्स ZM)

= (-a [0] · जेएम) + (एक [0]-ए [1] · जेएम) · एक्स + ... + (एक [एम -2] -ए [एम -1] · जेएम) · एक्स^(एम -1) एक [एम-1] · x^मीटर

जगह में इस पाश

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 गुणा की कुल और गुणा के लिए subtractions की तरह संख्या देता है के रूप में लागू किया जा सकता सभी एन रैखिक कारकों के।

Answer 2

सी ++ a[n] में सबसे पहले एक स्थिर सरणी है, इसलिए कंपाइलर को संकलन समय के दौरान n जानने की आवश्यकता है, जो यहां नहीं है। तो कोड सी ++ में "सही नहीं है"। मुझे पता है कि यह जीसीसी या अन्य कंपाइलर्स में संकलित होगा, लेकिन यह सी ++ मानक के खिलाफ है। C++ declare an array based on a non-constant variable? देखें, आपको new और delete कमांड का उपयोग करके एक गतिशील सरणी है, या आप STL से अधिक सुरक्षित std::vector कक्षा का उपयोग कर सकते हैं।

अब, मुख्य समस्या यह है कि यहाँ आप k नेस्टेड छोरों की जरूरत है, अगर आप k'th गुणांक गणना करना चाहते हैं, (मैं यह सोचते हैं हूँ 1 0 गुणांक, नहीं 1, बस सम्मेलन है)। तो, आपको परिवर्तनीय संख्या लागू करने की आवश्यकता है। अपने कोड में loops के लिए घोंसला। मैं आपकी समस्या का समाधान पोस्ट कर रहा हूं, जिसमें मैंने परिवर्तनीय संख्या लागू करने के लिए एक विधि का उपयोग किया था। लूप के लिए घोंसला उम्मीद है कि यह आपकी समस्या का समाधान करेगा।

#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 

} 

मैंने कोड की जांच की है, और यह पूरी तरह से काम कर रहा है। यदि आप जानना चाहते हैं कि loops के लिए नेस्टेड परिवर्तनीय संख्या को कैसे कार्यान्वित किया जाए, तो बस variable nested for loops पर जाएं और BugMeNot2013 का उत्तर देखें।