7-8 一元多项式的加法

分数 20

全屏浏览

切换布局

作者 张志梅

单位 青岛大学

设计程序求两个一元多项式的和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数。数字间以空格分隔。

输出格式:

输出1行，以指数递降方式输出和多项式非零项的系数和指数（保证不超过整数的表示范围）。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

输出样例:

5 20 -4 4 -5 2 9 1 -2 0

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <iostream>
#include <vector>
using namespace std;
// 定义结构体表示多项式的一项
struct PolyTerm {
    int coefficient; // 系数
    int exponent;    // 指数
};

// 比较函数，用于按照指数从大到小排序
bool compare(const PolyTerm& a, const PolyTerm& b) {
    return a.exponent > b.exponent;
}

int main() {
    vector<PolyTerm> poly1;
    vector<PolyTerm> poly2;

    // 读入第一个多项式
    int n1;
    cin >> n1;
    for (int i = 0; i < n1; i++) {
        PolyTerm term;
        cin >> term.coefficient >> term.exponent;
        poly1.push_back(term);
    }

    // 读入第二个多项式
    int n2;
    cin >> n2;
    for (int i = 0; i < n2; i++) {
        PolyTerm term;
        cin >> term.coefficient >> term.exponent;
        poly2.push_back(term);
    }

    // 将两个多项式的项合并到一起
    vector<PolyTerm> result = poly1;
    result.insert(result.end(), poly2.begin(), poly2.end());

    // 按照指数从大到小排序
    sort(result.begin(), result.end(), compare);

    // 合并同类项
    vector<PolyTerm> finalResult;
    for (int i = 0; i < result.size();) {
        PolyTerm combinedTerm;
        combinedTerm.exponent = result[i].exponent;
        combinedTerm.coefficient = result[i].coefficient;
        int j = i + 1;
        while (j < result.size() && result[j].exponent == result[i].exponent) {
            combinedTerm.coefficient += result[j].coefficient;
            j++;
        }
        if (combinedTerm.coefficient!= 0) {
            finalResult.push_back(combinedTerm);
        }
        i = j;
    }

    // 输出结果
    if (finalResult.empty()) {
        cout << "0 0";
    } else {
        for (int i = 0; i < finalResult.size(); i++) {
            cout << finalResult[i].coefficient << " " << finalResult[i].exponent;
            if (i!= finalResult.size() - 1) {
                cout << " ";
            }
        }
    }
    return 0;
}