PAT 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 \ N_1 \ a_{N_1} \ N_2 \ a_{N_2} \ ... \ N_K \ a_{N_K}$
where K is the number of nonzero terms in the polynomial, $N_i$ and $a_{N_i}$ (i = 1, 2, ..., K) are the exponents and coefficients, respectively. It is given that $1 \leq K \leq 10, 0 \leq N_K \lt ... \lt N_2 \lt N_1 \leq 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

题目大意

参考PAT 1002 A+B for Polynomials，本题要算的是多项式A与B的乘积，输入输出格式均与PAT 1002相同。

题解

PAT 1002中使用的方法是建立一个浮点型数组，用数组下标来表示多项式的指数，下标对应的元素值来表示该项的系数，并一边输入一边完成多项式加法。
本题中，要完成多项式的乘法，采用的方法是先把两个多项式分别用一个整型数组和一个浮点型数组存储起来，再采用类似PAT 1002的方法，用一个浮点型数组存储两多项式元素依次相乘得到结果。

C语言代码如下：

#include<stdio.h>
#include<stdlib.h>

int equal(float a, float b){
    if(a - b < 0.001 && a - b > -0.001) return 1;
    return 0;
}

int main(){
    int m, n;
    scanf("%d", &m);
    float *a1 = malloc(sizeof(float) * m);
    int *s1 = malloc(sizeof(int) * m);
    for(int i = 0;i < m;++i){
        scanf("%d %f", s1 + i, a1 + i);
    }
    scanf("%d", &n);
    float *a2 = malloc(sizeof(float) * n);
    int *s2 = malloc(sizeof(int) * n);
    for(int i = 0;i < n;++i){
        scanf("%d %f", s2 + i, a2 + i);
    }
    float *result = malloc(sizeof(float) * (s1[0] + s2[0] + 1));
    int cnt = 0;
    for(int i = 0;i < m;++i){
        for(int j = 0;j < n;++j){
            if(equal(result[s1[i] + s2[j]], 0)){
                cnt++;
            }
            result[s1[i] + s2[j]] += a1[i] * a2[j];
            if(equal(result[s1[i] + s2[j]], 0))
                cnt--;
        }
    }
    printf("%d", cnt);
    for(int i = s1[0] + s2[0];i >= 0;--i){
        if(!equal(result[i], 0)){
            printf(" %d %.1f", i, result[i]);
        }
    }
    printf("\n");
    return 0;
}