다항 연산

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() 기능에는 off-by-one 버그가 있습니다. 먼저, 계수 및 지수의 목록을 변환 최대 지수를 찾으려면 size()-1

---

를 반환해야합니다; 당신이 그랬던 것처럼, 그리고

coefficients.assign(degree + 1, 0); 

을 설정 한 각 계수 : (위 참조, 플러스 일)

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

그런 다음, 제로의 수의 계수를 초기화 :이 다항식의 정도 될 것입니다 .

---

그러나 힘/지수의 오름차순을 사용하는 것이 훨씬 좋습니다! 이렇게하면 항상 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); 
    ... 
} 

나머지는 쉽게해야한다.

---

추가를 수행 한 후에는 최고 계수가 0 인 지 확인하십시오. 당신이 2x^2+x+1 및 -2x^2+x+1 추가 할 때 예를 들어, 당신은 당신이 2x+2로 변환 할 수 있습니다 0x^2+2x+2를 얻을 : 당신이 operator+ 및 operator* 권리를 일단 파생

---

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

은 쉽게해야합니다.