【程序设计训练】多项式加法

r囧r小猫 2022-11-26 01:53 160阅读 0赞

## 【问题描述】 ##

一个多项式可以表示为一组数对，数对中第一个数始终为整数，且唯一，表示多项式的次数，另一数表示为对应的系数且不为0。输入两组数对，每组以0 0作为结束，实现对两个多项式的加法并按降幂输出结果数对

## 【输入形式】 ##

每行输入一个数对，以空格为分隔符，以0 0结束

## 【输出形式】 ##

每行输出一个数对，以空格为分隔符

## 【样例输入】 ##

5 12
    3 8
    1 2
    15 5
    0 10
    0 0
    3 12
    30 1
    15 5
    0 0

## 【样例输出】 ##

30 1
    15 10
    5 12
    3 20
    1 2
    0 10

## 【思路和做法】 ##

1.  使用map，key保存项的次数，value保存项的系数；
2.  map默认按照key升序排列，输出时用反向迭代器从后往前输出就是题目要求的按降幂输出。
3.  提交代码如下（10/10分，C++）：

//43.多项式加法
    #include <iostream>
    #include <map>
    using namespace std;
    
    int main()
    {
        
        int a, b;
        map<int, int> add;
        map<int, int>::reverse_iterator it; //反向迭代器it
        while (cin >> a >> b)
        {
        
            if (a == 0 && b == 0) //a、b均为0时结束
            {
        
                break;
            }
            if (add.count(a) == 0) //次数为a的项没有出现过
            {
        
                add[a] = 0; //次数为a的项系数为0
            }
            add[a] += b; //次数为a的项系数+b
        }
        while (cin >> a >> b)
        {
        
            if (a == 0 && b == 0)
            {
        
                break;
            }
            if (add.count(a) == 0)
            {
        
                add[a] = 0;
            }
            add[a] += b;
        }
        for (it = add.rbegin(); it != add.rend(); it++) //降幂输出（按key降序输出）
        {
        
            if(it->second==0)//系数为0，跳过
            {
        
                continue;
            }
            cout << it->first << ' ' << it->second << endl; //输出key和value（次数和系数）
        }
        return 0;
    }