L2-018 多项式A除以B

￡神魔★判官ぃ 2022-03-15 09:50 162阅读 0赞

L2-018 多项式A除以B （25 分）

这仍然是一道关于A/B的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R，其中R的阶数必须小于B的阶数。

### 输入格式： ###

输入分两行，每行给出一个非零多项式，先给出A，再给出B。每行的格式如下：

N e[1] c[1] ... e[N] c[N]

其中`N`是该多项式非零项的个数，`e[i]`是第`i`个非零项的指数，`c[i]`是第`i`个非零项的系数。各项按照指数递减的顺序给出，保证所有指数是各不相同的非负整数，所有系数是非零整数，所有整数在整型范围内。

### 输出格式： ###

分两行先后输出商和余，输出格式与输入格式相同，输出的系数保留小数点后1位。同行数字间以1个空格分隔，行首尾不得有多余空格。注意：零多项式是一个特殊多项式，对应输出为`0 0 0.0`。但非零多项式不能输出零系数（包括舍入后为0.0）的项。在样例中，余多项式其实有常数项`-1/27`，但因其舍入后为0.0，故不输出。

### 输入样例： ###

4 4 1 2 -3 1 -1 0 -1
    3 2 3 1 -2 0 1

### 输出样例： ###

3 2 0.3 1 0.2 0 -1.0
    1 1 -3.1

多项式除法可以参考 [https://blog.csdn.net/guoqingshuang/article/details/80565197][https_blog.csdn.net_guoqingshuang_article_details_80565197]

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    double a[10005],b[10005];
    double ans[10005];//存结果 
    int main()
    {
    	int n,m,i,j,x,y,o,p;//o表示分子的最高次 p表示分母的最高次 
    	int sa=0,sb=0;
    	memset(a,0,sizeof a);
    	memset(b,0,sizeof b);
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d %d",&x,&y);
    		a[x]=y;
    		if(!i)o=x;
    	}
    	scanf("%d",&m);
    	for(i=0;i<m;i++)
    	{
    		scanf("%d %d",&x,&y);
    		b[x]=y;
    		if(!i)p=x;
    	}
    	for(i=o;i>=p;i--)
    	{//除法 
    		ans[i-p]=1.0*a[i]/b[p];
    		for(j=p;j>=0;j--)
    		a[i+j-p]-=b[j]*ans[i-p];
    	}
    	for(i=o-p;i>=0;i--)
    	{
    		if(fabs(ans[i])>1e-6)
    		{
    			if(fabs(ans[i])<0.05)
    			ans[i]=0;
    			else
    			sa++;
    		}
    	}
    	for(i=p-1;i>=0;i--)
    	{
    		if(fabs(a[i])>1e-6)
    		{
    			if(fabs(a[i])<0.05)
    			a[i]=0;
    			else
    			sb++;
    		}
    	}
    	//商 
    	if(sa==0)
    	printf("0 0 0.0\n");
    	else
    	{
    		printf("%d",sa);
    		for(i=o-p;i>=0;i--)
    		{
    			if(fabs(ans[i])>1e-6)
    			printf(" %d %.1lf",i,ans[i]);
    		}
    		printf("\n");
    	}
    	//余数 
    	if(sb==0)
    	printf("0 0 0.0\n");
    	else
    	{
    		printf("%d",sb);
    		for(i=p-1;i>=0;i--)
    		{
    			if(fabs(a[i])>1e-6)
    			printf(" %d %.1lf",i,a[i]);
    		}
    		printf("\n");
    	}
    }

[https_blog.csdn.net_guoqingshuang_article_details_80565197]: https://blog.csdn.net/guoqingshuang/article/details/80565197