PAT甲级真题——1009. Product of Polynomials

1009. Product of Polynomials

This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, …, K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10, 0 <= NK < … < N2 < N1 <=1000.

Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output

3 3 3.6 2 6.0 1 1.6

题目大意：

两个多项式相乘

题目解析：

给出的代码是通过三个数组分别存储两个多项式和结果，进行简单模拟。看了别人的代码，发现也可以只用一个数组存储多项式A,另一个多项式在输入的时候直接计算即可。

具体代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define MAXN 2010
#define EPSILON 0.01 //根据精度需要

double A[MAXN],B[MAXN],C[MAXN];//C存放相乘的结果

int main() {
	int k,a;
	double b;;
	scanf("%d",&k);
	while(k--) {
		scanf("%d%lf",&a,&b);
		A[a]=b;
	}
	scanf("%d",&k);
	while(k--) {
		scanf("%d%lf",&a,&b);
		B[a]=b;
	}
	for(int i=0; i<MAXN; i++) {
		if(fabs(A[i])>EPSILON)//如果系数不是0
			for(int j=0; j<MAXN; j++) {
				if(fabs(B[j])>EPSILON) { //如果系数不是0
					C[i+j]+=A[i]*B[j];
				}
			}
	}
	int count=0;
	for(int i=0;i<MAXN;i++)
		if(fabs(C[i])>EPSILON)
			count++;
	printf("%d",count);
	for(int i=MAXN-1;i>=0;i--)
		if(fabs(C[i])>EPSILON)
			printf(" %d %.1f",i,C[i]);
	return 0;
}