L2-018 多项式A除以B (25 分)

多项式A除以B (25 分)"/>

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

注意点：按照长除法的步骤完成即可，题目要求：其中R(余数)的阶数必须小于B的阶数

解答：

#include <cstdio>
#include <vector>using namespace std;struct Node{float front;int up;
};int main(){int i,N,up;float front;Node temp;//	获得A--被除数scanf("%d",&N);vector<Node> A;;int A_Size = 0;for(i=0; i<N; i++){scanf("%d %f",&up,&front);if(i==0){temp.up = up;temp.front = front;A.push_back(temp);continue;}while(A[A_Size].up - up != 1){temp.up = A[A_Size].up-1;temp.front = 0;A.push_back(temp);A_Size++;}A_Size++;temp.front = front;temp.up = up;A.push_back(temp);}while(A[A_Size].up!=0){temp.up = A[A_Size].up-1;temp.front = 0;A.push_back(temp);A_Size++;}A_Size++;//	获得B--除数scanf("%d",&N);vector<Node> B;int B_Size = 0;for(i=0; i<N; i++){scanf("%d %f",&up,&front);if(i==0){temp.up = up;temp.front = front;B.push_back(temp);continue;}while(B[B_Size].up - up != 1){temp.up = B[B_Size].up-1;temp.front = 0;B.push_back(temp);B_Size++;}B_Size++;temp.front = front;temp.up = up;B.push_back(temp);}while(B[B_Size].up!=0){temp.up = B[B_Size].up-1;temp.front = 0;B.push_back(temp);B_Size++;}B_Size++;//	获得C--商vector<Node> C;int C_Size = 0;while(true){if(A[0].up<B[0].up){break;}temp.front = A[0].front / B[0].front;temp.up = A[0].up - B[0].up;C.push_back(temp);//	获得B*C--除数*商vector<Node> D;int D_Size = 0;for(i=0; i<B_Size; i++){front =  C[C_Size].front * B[i].front;up = C[C_Size].up + B[i].up;if(i==0){temp.front = front;temp.up = up;D.push_back(temp);D_Size++;continue;}while(D[D_Size-1].up-up != 1){temp.up = D[D_Size-1].up - 1;temp.front = 0;D.push_back(temp);D_Size++;}temp.up = up;temp.front = front;D.push_back(temp);D_Size++;}for(i=0; i<D_Size; i++){A[i].front -= D[i].front;}//	获得A--余数while(A_Size>0 && A[0].front==0){A.erase(A.begin());A_Size--;}C_Size++;}//	去除0项式for(i=0; i<C_Size; i++){if((float)(int)(C[i].front*10+0.5)/10 == 0){C.erase(C.begin()+i);C_Size--;i--;}}printf("%d ",C_Size);if(C_Size==0){printf("0 0.0");}for(i=0; i<C_Size; i++){printf("%d %.1f",C[i].up,C[i].front);if(i!=C_Size-1){printf(" ");}}printf("\n");//	去除0项式for(i=0; i<A_Size; i++){if((float)(int)(A[i].front*10+0.5)/10 == 0){A.erase(A.begin()+i);A_Size--;i--;}}printf("%d ",A_Size);if(A_Size==0){printf("0 0.0");}for(i=0; i<A_Size; i++){printf("%d %.1f",A[i].up,A[i].front);if(i!=A_Size-1){printf(" ");}}return 0;
}