浙江大学PAT上机题解析之3-04. 一元多项式的乘法与加法运算

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

输入格式说明：

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

输出格式说明：

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

样例输入与输出：

序号	输入	输出
1	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
2	2 1 2 1 0 2 1 2 -1 0	1 4 -1 0 2 2
3	2 -1000 1000 1000 0 2 1000 1000 -1000 0	-1000000 2000 2000000 1000 -1000000 0 0 0
4	0 1 999 1000	0 0 999 1000

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

using namespace std;

typedef struct Term{
	int coe;//系数
	int exp;//指数	
}Term;

bool compare(Term a,Term b)
{
	return a.exp>b.exp;
}

/*
Term Mul(Term a,Term b)
{
	a.coe = a.coe*b.coe;
	a.exp = a.exp+b.exp;
	return a;
}
*/

/*
Term Add(Term a,Term b)
{
	a.coe +=b.coe;
	return a;
}*/
void print(Term a)
{
	cout<<a.coe<<" "<<a.exp<<" ";
}
int main()
{

	vector<Term>    vec1;
	vector<Term>    vec2;
	vector<Term>    vec;
	vector<Term>::iterator  it1,it2;

	int N1,N2;
	int coe,exp;
	bool  flag = false;
	Term t;
	cin>>N1;
	while(N1--)
	{
		cin>>coe>>exp;
		t.coe = coe;
		t.exp = exp;
		vec1.push_back(t);
	}
	//for_each(vec1.begin(),vec1.end(),print);
	//system("pause");

	
	cin>>N2;
	while(N2--)
	{
		cin>>coe>>exp;
		t.coe = coe;
		t.exp = exp;
		vec2.push_back(t);
	}

	//for_each(vec2.begin(),vec2.end(),print);
	//system("pause");

	for (it1=vec1.begin();it1!=vec1.end();it1++)
		for (it2=vec2.begin();it2!=vec2.end();it2++)
		{
            t.coe = it1->coe * it2->coe;
			t.exp = it1->exp + it2->exp;	
			if (t.coe!=0)
            vec.push_back(t);

		}
			
	sort(vec.begin(),vec.end(),compare);

	for (it1 = vec.begin();it1!=vec.end();it1=it2)
	  {  
		  for (it2 = it1+1;it2!=vec.end() &&it1->exp==it2->exp;it2++)	      	
				   it1->coe += it2->coe;
			if (it1->coe!=0)
			{
				if (flag)
				cout<<" ";
				else
				flag = true;
				cout<<it1->coe<<" "<<it1->exp;
			}			       
	  }
	if (vec1.size()==0)
	{
		cout<<"0 0";
	}
	cout<<endl;
	flag = false;

	for (it1=vec1.begin(),it2=vec2.begin();it1!=vec1.end()&&it2!=vec2.end();)
	{
		if (it1->exp >it2->exp)
		{
			if (flag)
				cout<<" ";
			else
				flag = true;
			cout<<it1->coe<<" "<<it1->exp;
			it1++;
		}
		else if (it1->exp < it2->exp)
		{
			if (flag)
				cout<<" ";
			else
				flag = true;
			cout<<it2->coe<<" "<<it2->exp;
			it2++;
		}
		else
		{

			if ((it1->coe+it2->coe))
			{
				if (flag)
					cout<<" ";
				else
					flag = true;
				cout<<it1->coe+it2->coe<<" "<<it1->exp;
			}
			
			it1++;
			it2++;
		}
	}

	if (it1==vec1.end())
	{
		while(it2!=vec2.end())
		{
			if (flag)
				cout<<" ";
			else
				flag = true;
			cout<<it2->coe<<" "<<it2->exp;
			it2++;
		}
	}

	if (it2==vec2.end())
	{
		while(it1!=vec1.end())
		{
			if (flag)
				cout<<" ";
			else
				flag = true;
			cout<<it1->coe<<" "<<it1->exp;
			it1++;
		}
	}

	if (flag==false)
	cout<<"0 0";
	cout<<endl;

	 //for_each(vec.begin(),vec.end(),print);
	

	//system("pause");
	return 0;
}

//题目不难，注意细节即可