题目简述
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分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
基本思路
以数组结构的方式构造多项式，并设计以下函数：
- 两个多项式相加：逐项比对，指数较大者放置项；指数相等时系数相加；一个多项式所有项放置完后直接放置另一个多项式的剩余项；
- 多项式乘单项式：每一项指数相加，系数相乘即可；
- 多项式乘多项式：逐项进行多项式乘单项式；
- 特殊情形：存在零多项式时，乘积结果为0；
代码
#include <iostream>
using namespace std;
/**
多项式每一项的数据结构
*/
typedef struct{
int coef;
int expo;
} poly;
/**
读取多项式
@param length 多项式长度
@param p 多项式数组地址
@return 多项式数组地址
*/
poly* ScanfPoly(int length,poly *p){
for (int i=0; i<length; i++) {
cin>>p[i].coef>>p[i].expo;
}
return p;
}
/**
输出多项式
@param length 要输出的多项式长度
@param p 要输出的多项式数组地址
*/
void PrintPoly(int length,poly *p){
bool flag=false;
/*输出第一项*/
if(p->coef!=0){//只输出非零项
printf("%d %d",p->coef,p->expo);
flag=true;
}
/*依次输出后面的每一项*/
poly *pol=p+1;
while (pol<(p+length)) {
if(pol->coef!=0) {
printf(" %d %d",pol->coef,pol->expo);
flag=true;
}
pol++;
}
/*如果没输出过任何项，输出0 0*/
if(flag==false)printf("0 0");
}
/**
多项式的加法运算
@param p1 多项式1
@param l1 多项式1的项数
@param p2 多项式2
@param l2 多项式2的项数
@param is 接收和多项式项数的值
@return 和多项式的地址
*/
poly* PlusPoly(poly *p1,int l1,poly *p2,int l2,int &is){
poly *sum=(poly*)malloc((l1+l2)*sizeof(poly));
int i1,i2;
for (i1=0,i2=0,is=0; i1<l1 || i2<l2; is++) {
if(i2>=l2 || p1[i1].expo>p2[i2].expo){
sum[is]=p1[i1];
i1++;
}
else if(i1>=l1 || p1[i1].expo<p2[i2].expo){
sum[is]=p2[i2];
i2++;
}
else if(p1[i1].expo==p2[i2].expo){
sum[is].expo=p1[i1].expo;
sum[is].coef=p1[i1].coef+p2[i2].coef;
i1++;
i2++;
}
}
return sum;
}
bool polyComplare(poly p1,poly p2){
return (p1.expo>p2.expo);
}
/**
单项式乘多项式
@param p1 单项式
@param p2 多项式
@param l2 多项式的项数
@return 多项式的地址
*/
poly* multiOnePoly(poly p1,poly *p2,int l2){
poly *proPoly=(poly*)malloc(l2*sizeof(poly));
for (int i=0; i<l2; i++) {
proPoly[i].coef = p2[i].coef*p1.coef;
proPoly[i].expo = p2[i].expo+p1.expo;
}
return proPoly;
}
/**
多项式乘多项式（！！不能有零多项式）
@param p1 多项式1
@param l1 多项式1的长度
@param p2 多项式2
@param l2 多项式2的长度
@param lpro 要接收的积多项式的长度
@return 积多项式
*/
poly* MultiplyPoly(poly *p1,int l1,poly *p2,int l2,int &lpro){
poly *AllProductPoly;
lpro=0;
int lengthPro=0;
for (int i=0; i<l1; i++) {
poly* SingleProductPoly;
SingleProductPoly=multiOnePoly(p1[i], p2, l2);//求出p2与p1的每一项相乘的积多项式
/*总积多项式必须放后面*/
AllProductPoly=PlusPoly(SingleProductPoly, l2, AllProductPoly, lpro, lengthPro);
free(SingleProductPoly);//手动释放内存空间，后同
lpro=lengthPro;
}
return AllProductPoly;
}
int main(int argc, const char * argv[]) {
/*读取多项式1和多项式2*/
int K1,K2;
cin>>K1;
poly *p1=(poly*)malloc(K1*sizeof(poly));
ScanfPoly(K1,p1);
cin>>K2;
poly *p2=(poly*)malloc(K2*sizeof(poly));
ScanfPoly(K2,p2);
/*求积*/
if(K1!=0 && K2!=0){
poly *productPoly;
int lpro=0;
productPoly=MultiplyPoly(p1, K1, p2, K2, lpro);
PrintPoly(lpro, productPoly);
free(productPoly);
cout<<'\n';
}else printf("0 0\n");
/*求和*/
poly *sumPoly;
int lsum;
sumPoly=PlusPoly(p1, K1, p2, K2, lsum);
PrintPoly(lsum, sumPoly);
free(sumPoly);
}
