

DS线性表—多项式相加

时间限制: 1 Sec 内存限制: 128 MB

题目描述

对于一元多项式 $p(x) = p_{0} + p_{1}x + p_{2}x^{2} + … + p_{n}x^{n}$ ，每个项都有系数和指数两部分，例如 $p_{2}x^{2}$ 的系数为 $p_{2}$ ,指数为 $2$ 。

编程实现两个多项式的相加。

例如 $5 + x + 2x^{2} + 3x^{3}$ ， $-5 - x + 6x^{2} + 4x^{4}$ ，两者相加结果： $8x^{2} + 3x^{3} + 4x^{4}$

其中系数5和-5都是x的0次方的系数，相加后为0，所以不显示。x的1次方同理不显示。

可用顺序表或单链表实现。

输入

第1行：输入t表示有t组测试数据

第2行：输入n表示有第1组的第1个多项式包含n个项

第3行：输入第一项的系数和指数，以此类推输入n行

接着输入m表示第1组的第2个多项式包含m项

同理输入第2个多项式的m个项的系数和指数

参考上面输入第2组数据，以此类推输入t组

假设所有数据都是整数

输出

对于每1组数据，先用两行输出两个原来的多项式，再用一行输出运算结果，不必考虑结果全为0的情况

输出格式参考样本数据，格式要求包括：

1.如果指数或系数是负数，用小括号括起来。

2.如果系数为0，则该项不用输出。

3.如果指数不为0，则用符号^表示，例如x的3次方，表示为x^3。

4.多项式的每个项之间用符号+连接，每个+两边加1个空格隔开。

样例输入

样例输出

5 + 1x^1 + 2x^2 + 3x^3
(-5) + (-1)x^1 + 6x^2 + 4x^4
8x^2 + 3x^3 + 4x^4
(-3) + (-5)x^1 + 2x^2
9x^(-1) + 2 + 3x^1 + (-2)x^2
9x^(-1) + (-1) + (-2)x^1

提示

解决方案

#include <iostream>
#include <vector>
#include <algorithm>

class Poly {
public:
    struct Node {
        int coefficient, exponent;

        Node() = default;

        Node(int coefficient, int exponent) : coefficient(coefficient), exponent(exponent) {}

        Node operator+(const Node &rhs) {
            return {this->coefficient + rhs.coefficient, this->exponent};
        }

        bool operator<(const Node &rhs) const {
            return this->exponent < rhs.exponent;
        }

        friend std::ostream &operator<<(std::ostream &os, const Node &rhs) {
            if (rhs.coefficient < 0) {
                os << '(' << rhs.coefficient << ')';
            } else {
                os << rhs.coefficient;
            }
            if (rhs.exponent == 0) {
                return os;
            }
            os << "x^";
            if (rhs.exponent < 0) {
                return os << '(' << rhs.exponent << ')';
            } else {
                return os << rhs.exponent;
            }
        }
    };

    explicit Poly(int size) : poly(size) {}

    explicit Poly(std::vector<Node> &poly) : poly(poly) {}

    void setFromCin() {
        for (auto &item : this->poly) {
            std::cin >> item.coefficient >> item.exponent;
        }
    }

    Poly operator+(const Poly &rhs) {
        std::vector<Node> polyToReturn;
        size_t i1 = 0, i2 = 0;
        while (true) {
            const Node &node1 = this->poly[i1], &node2 = rhs.poly[i2];
            if (i1 == this->poly.size() && i2 == rhs.poly.size()) {
                break;
            }
            if (i1 == this->poly.size()) {
                polyToReturn.emplace_back(node2);
                i2 += 1;
                continue;
            }
            if (i2 == rhs.poly.size()) {
                polyToReturn.emplace_back(node1);
                i1 += 1;
                continue;
            }
            if (node1.exponent < node2.exponent) {
                polyToReturn.emplace_back(node1);
                i1 += 1;
            } else if (node1.exponent == node2.exponent) {
                polyToReturn.emplace_back(Node(node1.coefficient + node2.coefficient, node1.exponent));
                i1 += 1;
                i2 += 1;
            } else {
                polyToReturn.emplace_back(node2);
                i2 += 1;
            }
        }
        polyToReturn.erase(std::remove_if(polyToReturn.begin(), polyToReturn.end(),
                                          [](Node &node) { return node.coefficient == 0; }), polyToReturn.end());
        return Poly(polyToReturn);
    }

    friend std::ostream &operator<<(std::ostream &os, const Poly &rhs) {
        auto &polyToPrint = rhs.poly;
        os << polyToPrint.front();
        for (size_t i = 1; i < polyToPrint.size(); ++i) {
            os << " + " << polyToPrint[i];
        }
        return os;
    }

private:
    std::vector<Node> poly;
};

int main() {
    int T;
    std::cin >> T;

    while (T--) {
        int size;
        std::cin >> size;
        Poly lhs(size);
        lhs.setFromCin();
        std::cout << lhs << std::endl;
        std::cin >> size;
        Poly rhs(size);
        rhs.setFromCin();
        std::cout << rhs << std::endl;
        std::cout << lhs + rhs << std::endl;
    }

    return 0;
}

DS线性表—多项式相加

题目描述

输入

输出

样例输入

样例输出

提示

解决方案

评论