pta 天梯赛 L2-018 多项式A除以B (25 分)(多项式除法)
L2-018 多项式A除以B (25 分)
【题意】给出多项式A和B的指数和系数;其中指数是非负整数,系数是非零整数;求出A÷B(按输入格式给出);非零多项式不输出零系数(包括舍入后为0的项);
【分析】( 其实看了这个题之后才知道多项式除法是怎么除的...
- 原理如下图,其实和整数的除法差不多
- 定义两个数组,c1,c2,分别表示多项式A和多项式B;其中数组下标代表指数,数组值代表系数;并求出两个多项式中最大指数max1和max2;
- 在进行每一轮除法之后,商的最高次幂是(max1-max2),最高次幂的系数是(c1[max1]/c2[max2]);
- 循环,并更新c1,直至被除数的最高次幂小于除数;
【代码】(参考)
#include<bits/stdc++.h>
using namespace std;
const int maxn=3e3+10;
double c1[maxn],c2[maxn],c3[maxn];
int nonNegativeNum(double c[],int st)//统计非负项个数
{
int cnt=0;
for(int i=st;i>=0;--i)
if(abs(c[i])+0.05>=0.1)cnt++;
return cnt;
}
void printPoly(double c[],int st)
{
printf("%d",nonNegativeNum(c,st));
if(nonNegativeNum(c,st)==0)printf(" 0 0.0");
for(int i=st;i>=0;--i)
if(abs(c[i])+0.05>=0.1)printf(" %d %.1lf",i,c[i]);
}
int main()
{
int max1=-1,max2=-1;
int m;scanf("%d",&m);
for(int i=0;i<m;++i)
{
int t;scanf("%d",&t);
max1=max(max1,t);
scanf("%lf",&c1[t]);
}
int n;scanf("%d",&n);
for(int i=0;i<n;++i)
{
int t;scanf("%d",&t);
max2=max(max2,t);
scanf("%lf",&c2[t]);
}
int t1=max1,t2=max2;
while(t1>=t2)
{
double x=c1[t1]/c2[t2];//最高次幂的商的系数
c3[t1-t2]=x;
for(int i=t1,j=t2;j>=0;--j,--i)
c1[i]-=c2[j]*x;
while(abs(c1[t1])<1e-6)t1--;//如果该项是0,那么最高次幂降1;
}
printPoly(c3,max1-max2);
puts("");
printPoly(c1,t1);
return 0;
}