多項式運算

Question

我正在嘗試編寫一個從輸入文件構造多項式的程序。它讀入多項式並將值存儲到類屬性「係數」和「指數」中。例如。係數= 2，指數= 3將導致2x^3。讀取多項式和輸出時必須處理許多煩人的角落案例。 （operator<<和operator>>函數）我的主要功能徹底測試我的polynomial.cpp。我相信我的一個問題是來自構造多項式，正如你可能會注意到的，我也無法爲我的派生函數編寫代碼。這裏是我的：

#ifndef _POLYNOMIAL_H 
#define _POLYNOMIAL_H 

#include <iostream> 
#include <vector> 
#include <sstream> 

using namespace std; 

class Polynomial { 

public: 

    Polynomial(); 
    Polynomial(vector<double> iCoefficients, vector<int> iExponents); 

    int Degree() const; 
    double Evaluate(double x) const; 
    Polynomial Derivative() const; 

    friend Polynomial operator+(const Polynomial & p, const Polynomial & p2); 
    friend Polynomial operator*(const Polynomial & p, const Polynomial & p2); 
    friend ostream& operator<<(ostream& out, const Polynomial & p); 
    friend istream& operator>>(istream& in, Polynomial & p); 

private: 

    vector<double> coefficients; 

}; 
#endif 

#include "polynomial.h" 
#include <stdexcept> 
#include <vector> 
#include <cmath> 

using namespace std; 

// Default Constructor 
Polynomial::Polynomial() { 
    coefficients.push_back(0); 
} 

// Constructor for a Polynomial 
Polynomial::Polynomial(vector<double> iCoefficients, vector<int> iExponents) { 

    for (int i = 0; i < iExponents[0]; i++) { 
    coefficients.push_back(0); 
    } 

    for (size_t i = 0; i < iExponents.size(); i++) { 
    coefficients[(Degree() - iExponents[i])] = iCoefficients[i]; 
    } 
} 

// Returns highest exponent of the polynomial 
int Polynomial::Degree() const { 

    return coefficients.size(); 
} 

// Evaluates the polynomial at a particular point 
double Polynomial::Evaluate(double x) const { 

    double result; 

    for(int i = 0; i <= Degree(); i++) { 
    result += pow(x, Degree() - i) * coefficients[i]; 
    } 
    return result; 
} 

// Returns first derivative of the polynomial 
Polynomial Polynomial::Derivative() const { //----------------------??? 

// Polynomial result; 

// for(int i = 0; i <= Degree(); i++) { 
//  result.coefficients[i] = coefficients[i] * (Degree() - i); 
// } 
// return result; 
}   


// Returns polynomial object that is the sum of parameters 
Polynomial operator+(const Polynomial & p, const Polynomial & p2) { 

    int d = p.Degree(); 
    int d2 = p2.Degree(); 
    Polynomial sum; 

    for (int j = 0; j < d; j++) { 
    for (int i = 0; i < d2; i ++) { 
     sum.coefficients.push_back(p.coefficients[j] + p2.coefficients[i]); 
    } 
    } 
    return sum; 
} 

// Returns polynomial object that is the product of parameters 
Polynomial operator*(const Polynomial & p, const Polynomial & p2) { 

    int d = p.Degree(); 
    int d2 = p2.Degree(); 
    Polynomial product; 

    for (int j = 0; j < d; j++) { 
    for (int i = 0; i < d2; i ++) { 
     product.coefficients.push_back(p.coefficients[j] * p2.coefficients[i]); 
    } 
    } 
    return product; 
} 

// Output operator 
ostream& operator<<(ostream& out, const Polynomial & p) { 

    for (int i = 0; i <= p.Degree(); i++) { 

    if(i == 0 && p.Degree() <= 1) { 
     out << 0; 
    } 

    if (p.coefficients[i] != 0 && i != 0) { 
     out << '+'; 
    } 

    if (p.coefficients[i] != 0) { 
     out << p.coefficients[i]; 
     if(i < (p.Degree() - 1)) { 
    out << "x^"; 
    out << (i - p.Degree()) * (-1); 
     } 
    } 
    } 
    return out; 
} 

// Input operator 
istream& operator>>(istream& in, Polynomial & p) { 

    char ch; 
    int exponent; 
    double coefficient; 
    vector<double> coefficients; 
    vector<int> exponents; 

    while(isspace(ch) == false) { 

    ch = in.peek(); 
    if(ch == '+') { 
     in.ignore(); 
     in >> coefficient; 
    } 
    else if(ch == '-') { 
     in.ignore(); 
     in >> coefficient; 
     coefficient = coefficient * (-1); 
    } 
    else { 
     in >> coefficient; 
    } 
     ch = in.peek(); 
     if((ch <= 'z') && (ch >= 'a')) { 
    in >> ch; 
    ch = in.peek(); 
     if(ch == '^') { 
     in.ignore(); 
     in >> exponent; 
     } 
     else 
     exponent = 1; 
     } 
     else 
    exponent = 0; 

     coefficients.push_back(coefficient); 
     exponents.push_back(exponent); 
    } 

    p = Polynomial(coefficients, exponents); 

    return in; 
} 

#include <iostream> 
#include <sstream> 
#include <string> 
#include <cmath> 
#include "polynomial.h" 

using namespace std; 

bool testPolynomial(const Polynomial& p, string expected); 
bool testOperations(const Polynomial& p, int degree, double expected); 
bool testInput(string s); 


int main() { 
    int errors = 0; 

    cerr << "Note: Nearly all of the tests expect a working output operator. If a test fails, check that first" << endl; 
    cerr << "Testing default constructor" << endl; 
    Polynomial p1; // test default constructor 
    errors += testPolynomial(p1, "0"); 

    cerr << "Testing explicit value constructor" << endl; 
    double c_arr[] = {1.1, 2, 4, 7}; 
    int e_arr[] = {6, 3, 2, 0}; 
    vector<double> c(c_arr, c_arr+4); 
    vector<int> e(e_arr, e_arr+4); 
    Polynomial p2(c, e); 
    errors += testPolynomial(p2, "1.1x^6+2x^3+4x^2+7"); 
    c.clear(); e.clear(); 
    cout << '1' << endl; 
    Polynomial p3(c, e); 
    errors += testPolynomial(p3, "0"); 
    cout << '2' << endl; 

    cerr << "Testing operations" << endl; 
    double c2_arr[] = {-1.1, 2, -4, 7}; 
    int e2_arr[] = {4, 3, 2, 0}; 
    vector<double> c2(c2_arr, c2_arr+4); 
    vector<int> e2(e2_arr, e2_arr+4); 
    Polynomial p4(c2,e2); 
    errors += testOperations(p1, 0, 0); 
    errors += testOperations(p2, 6, 109.4); 
    errors += testOperations(p4, 4, -10.6); 

    errors += testPolynomial(p1.Derivative(), "0"); 
    errors += testPolynomial(p2.Derivative(), "6.6x^5+6x^2+8x"); 
    errors += testPolynomial(p4.Derivative(), "-4.4x^3+6x^2-8x"); 

    errors += testPolynomial(p1+p2, "1.1x^6+2x^3+4x^2+7"); 
    errors += testPolynomial(p2+p4, "1.1x^6-1.1x^4+4x^3+14"); 

    errors += testPolynomial(p1*p2, "0"); 
    errors += testPolynomial(p2*p2, "1.21x^12+4.4x^9+8.8x^8+19.4x^6+16x^5+16x^4+28x^3+56x^2+49"); 
    double c_arr3[] = {-1}; 
    int e_arr3[] = {0}; 
    vector<double> c3 = vector<double>(c_arr3, c_arr3+1); 
    vector<int> e3 = vector<int>(e_arr3, e_arr3+1); 
    Polynomial p5(c3, e3); 

    errors += testPolynomial(p2 * p5 + p2, "0"); 
    errors += testPolynomial(p5, "-1"); 

    cerr << "Testing input operator." << endl; 
    testInput("0"); 
    testInput("51"); 
    testInput("-1.1"); 
    testInput("3x^2"); 
    testInput("-5x^3-5"); 
    testInput("x^5+x-1"); 
    testInput("-x^4+2"); 

    return errors; 
} 

bool testPolynomial(const Polynomial& p, string expected) { 
    ostringstream out; 
    out << p; 
    if (out.str() != expected) { 
    cerr << "Test failed: expected " << expected << " got " << out.str() << endl; 
    return true; 
    } else { 
    return false; 
    } 
} 

bool testOperations(const Polynomial& p, int degree, double expected) { 
    if(p.Degree() != degree) { 
    cerr << "Failed Degree operation" << endl; 
    return true; 
    } 
    double result = p.Evaluate(2.0); 
    if (fabs(result - expected) > 1e-5) { 
    cerr << "Failed Evaluation operation" << endl; 
    } 
    return false; 
} 

bool testInput(string s) { 
    Polynomial p; 
    istringstream in(s+" "); 
    in >> p; 
    ostringstream out; 
    out << p; 
    if (out.str() != s) { 
    cerr << "Failed input test. Expected: " << s << " got " << out.str() << endl; 
    return true; 
    } 
    return false; 
} 

Answer 1

Polynomial::Degree()函數有一個錯誤的錯誤;它應該返回size()-1

---

爲了係數和指數的列表轉換，先找到最大的指數;這將是多項式的次數：

int degree = *std::max_element(iExponents.begin(), iExponents.end()); 

然後，初始化與此數量的零係數（加一，見上文）：

coefficients.assign(degree + 1, 0); 

然後，設置每個係數，就像你一樣。

---

但是，使用功率/指數的升序更好！這樣，你不需要一直計算Degree()-i，你可以用i來代替。

for (size_t i = 0; i < iExponents.size(); i++) { 
    coefficients[iExponents[i]] += iCoefficients[i]; 
} 

注意+=在上面的代碼;它處理像3x+4x+5x這樣的多項式，相當於12x。

---

你的加法和乘法算法是完全錯誤的。你應該首先設置輸出多項式的程度，就像你在構造函數中所做的：

Polynomial operator+(const Polynomial & p, const Polynomial & p2) 
{ 
    int d = p.Degree(); 
    int d2 = p2.Degree(); 
    Polynomial sum; 

    sum.coefficients.assign(std::max(d, d2) + 1, 0); 
    ... 
} 

其餘的應該更容易，一旦你嘗試去想它。

---

執行加法後，您可能需要檢查零度最高的係數;例如，當您添加2x^2+x+1和-2x^2+x+1，你會得到0x^2+2x+2，您可能要轉換爲2x+2：

while (coefficients.back() == 0) 
    coefficients.resize(coefficients.size() - 1); 
if (coefficients.empty()) 
    coefficients.push_back(0); 

---

衍生應該很容易，一旦你operator+和operator*權。