设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分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
#include <iostream>
using namespace std;
typedef struct
{
int x;
int z;
}Sqlist;
int main ()
{
int n, m;
cin >> n;
Sqlist a[n];
for ( int i = 0; i < n; i ++ )
{
cin >> a[i].x >> a[i].z;
}
cin >> m;
Sqlist b[m];
for ( int i = 0; i < m; i ++ )
{
cin >> b[i].x >> b[i].z;
}
//求积,每一项分别相乘
Sqlist c[m*n];
int k = 0;
for ( int i = 0; i < n; i ++ )
{
if ( a[i].x != 0 )
{
for ( int j = 0; j < m; j ++ )
{
if ( b[j].x != 0 )
{
c[k].x = a[i].x * b[j].x;
c[k].z = a[i].z + b[j].z;
k ++;
}
}
}
}
//按指数从大到小排序
Sqlist t;
for ( int i = 0; i < k - 1; i ++ )
{
for ( int j = i+1; j < k; j ++ )
{
if ( c[i].z <= c[j].z )
{
t = c[i];
c[i] = c[j];
c[j] = t;
}
}
}
//合并指数相同的
for ( int i = 0; i < k - 1; i ++ )
{
if ( c[i].z == c[i+1].z )
{
c[i+1].x = c[i].x + c[i+1].x;
c[i].x = 0;
}
}
//输出积
int flag = 0;
for ( int i = 0; i < k; i ++ )
{
if ( c[i].x != 0 )
{
cout << c[i].x << " " << c[i].z;
if ( i < k-1 )
{
cout << " ";
}
flag ++;
}
}
if ( flag == 0 )
{
cout <<"0 0";
}
cout << endl;
//求和
Sqlist d[m+n];
int g = 0;
//先将两个多项式都放入d[];
for ( int i = 0; i < n; i ++ )
{
d[g].x = a[i].x;
d[g].z = a[i].z;
g ++;
}
for ( int i = 0; i < m; i ++ )
{
d[g].x = b[i].x;
d[g].z = b[i].z;
g ++;
}
//按指数从大到小排序
for ( int i = 0; i < g - 1; i ++ )
{
for ( int j = i+1; j < g; j ++ )
{
if ( d[i].z < d[j].z )
{
t = d[i];
d[i] = d[j];
d[j] = t;
}
}
}
//合并指数相同的
for ( int i = 0; i < g-1; i ++ )
{
if ( d[i].z == d[i+1].z )
{
d[i+1].x = d[i].x + d[i+1].x;
d[i].x = 0;
}
}
//输出和
flag = 0;
for ( int i = 0; i < g; i ++ )
{
if ( d[i].x != 0 )
{
cout << d[i].x << " " << d[i].z;
if ( i < g - 1 )
{
cout << " ";
}
flag ++;
}
}
if ( flag == 0 )
{
cout <<"0 0";
}
return 0;
}