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来存储计算后的多项式的值(以指数大小为键值),一是为了去重,二是可以自动排序,可以减小代码量。
有两个点没过,暂存以便后日修改
代码:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int num1,num2,flag=0;
scanf("%d",&num1);
int indice1[2][num1];
for(int i=0;i<num1;i++)
scanf("%d %d",&indice1[0][i],&indice1[1][i]);
scanf("%d",&num2);
int indice2[2][num2];
for(int i=0;i<num2;i++)
scanf("%d %d",&indice2[0][i],&indice2[1][i]);
map<int,int> m,m2;
for(int i=0;i<num1;i++){
for(int j=0;j<num2;j++){
m[indice1[1][i]+indice2[1][j]]+=indice1[0][i]*indice2[0][j];
}
}
for(int i=0;i<num1;i++)
m2[indice1[1][i]]+=indice1[0][i];
for(int i=0;i<num2;i++)
m2[indice2[1][i]]+=indice2[0][i];
for(auto it=--m.end();it!=m.begin();it--){
if(it->second!=0){
printf("%d %d ",it->second,it->first);
flag=1;
}
}
if(flag==1&&m.begin()->second==0)
printf("0 0\n");
else
printf("%d %d\n",m.begin()->second,m.begin()->first);
flag=0;
for(auto it=--m2.end();it!=m2.begin();it--){
if(it->second!=0){
printf("%d %d ",it->second,it->first);
flag=1;
}
}
if(flag==1&&m2.begin()->second==0)
printf("0 0\n");
else
printf("%d %d\n",m2.begin()->second,m2.begin()->first);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)