数据结构 02-线性结构2 一元多项式的乘法与加法运算 (20 分)

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。

输出格式:

输出分2行,分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。零多项式应输出0 0

输入样例:

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

输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

 

 

需要注意的地方

核心部分是使用map来存取对应次幂的系数, map<int ,int > 左key为次幂, 右value为系数

1.计算结果的时候要对每一项进行系数判定, 如果结果的某项系数为0要删除这个key-value对, 用map.erase( iterator );的方法

2.两项和或积的结果 赋值的时候要使用累加形式, 便于判断计算后的新结果是否为 0 需不需要删除关键字key的次幂

 

这道题和Advanced  1002 基本上一样 , 只是cin 取值的时候 先取的是系数 后取的是次幂

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
void getPolynomialNumber(map<int,int> &po,int n){
    po.clear();
    int e;
    int num;
    for(int i=0;i<n;i++){
        cin >> num >> e;
        po[e]=num;
    }
}
void addPoly(map<int,int> &p1,map<int,int> &result){
    map<int,int>::iterator it;
    for(it=p1.begin();it!=p1.end();it++){
        result[it->first]+=it->second;
        if(result[it->first]==0){
            map<int,int>::iterator searchIt;
            searchIt=result.find(it->first);
            result.erase(searchIt);
        }
    }
}
void multiplyPoly(map<int,int> &p1,map<int,int> &p2,map<int,int> &result){
    
    map<int,int>::iterator it1;
    map<int,int>::iterator it2;
    for(it1=p1.begin();it1!=p1.end();it1++){
        for(it2=p2.begin();it2!=p2.end();it2++){
            result[it1->first+it2->first]+=it1->second*it2->second;
            if(result[it1->first+it2->first]==0){
                map<int,int>::iterator searchIt;
                searchIt=result.find(it1->first+it2->first);
                result.erase(searchIt);
            }
        }
    }
//    return result;
}
void printPoly(map<int,int> &p){
    vector<int> e;
    vector<int> n;
    map<int,int>::iterator it;
    for(it=p.begin();it!=p.end();it++){
        e.push_back(it->first);
        n.push_back(it->second);
    }
    if(e.size()==0){
        cout << "0 0"<<endl;
    }else{
        cout <<n[n.size()-1] <<" "<<e[e.size()-1] ;
        for(int i=e.size()-2;i>=0;i--){
            cout <<" "<<n[i] <<" "<<e[i];
        }
        cout <<endl;
    }
}
int main(){
    map<int,int> p1;
    map<int,int> p2;
    map<int,int> result1;
    map<int,int> result2;
    int n,m;
    cin >> n;
    getPolynomialNumber(p1, n);
    cin >> m;
    getPolynomialNumber(p2, m);
    addPoly(p1, result1);
    addPoly(p2, result1);
    multiplyPoly(p1, p2,result2);
    printPoly(result2);
    printPoly(result1);
    return 0;
}

 

上一篇:通过MySQL存储原理来深度分析排序和锁


下一篇:珂朵莉树学习笔记