PAT 1009 Product of Polynomials (25分) 指数做数组下标,系数做值

Scroll Down

题目

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≤K≤10, 0≤N​K​​ <⋯<N​2 ​​ <N​1​​ ≤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

题目解析

给出两个多项式,每个输入格式是 非零项个数 指数1 系数1 指数2 系数2
让计算两多项式的 乘积,并按照指定格式输出 非零项个数 指数1 系数1 指数2 系数2
要求顺序是指数从高到低

思路

前面写过一个多项式求和的题 PAT 1002 A+B for Polynomials (25分),两个思想以及处理方式是一样的,只不过一个是加法,一个是乘法,区别就在于:加法,只有指数相同的项,系数才能相加;对于乘法,指数不同的两项,相乘以后得到一个新指数项(原指数相加,系数相乘)

  • 用一个数组来存储多项式,每一项的指数作为数组的索引系数作为,这样在读入时,直接找到对应位置进行修改,对数组的访问是很快的。
  • 没必要用两个数组把两个多项式都保存后再进行乘法运算,那样时间复杂度和空间复杂度都比较高,还要进行很多不必要的运算,我们就用一个数组初始化每一项都为0.0,相当于所有指数项系数都为0,读入第一个多项式时,根据指数系数改变对应位置的值即可读入第二个多项式时,每读入一个非零项,就用它分别和数组的每一项做运算,得到的结果应该加到下标为两指数相加的数组元素上。这样读入第二个多项式后,所有运算也做完了。
  • 之后一次遍历,统计出数组不为0的个数,就是非零项的个数;然后对数组从后往前输出每个非零项对应的下标和值,就是结果。注意精确到小数点后1

代码

#include <iostream>
using namespace std;

int main() {

    // a,b是两个多项式,c是他们的乘积,指数作为下标,系数作为值,结果指数最高为2000
    float a[1001] = {0.0}, c[2001] = {0.0};

    int k;     // 几个非零项
    int exp;   // 指数
    float coe; // 系数

    // 读入a
    cin >> k;
    while (k-- > 0) {
        cin >> exp >> coe;
        a[exp] = coe;
    }
    // 读入b的同时计算结果
    cin >> k;
    while (k-- > 0) {
        cin >> exp >> coe;
        // 这一项系数不为0,题目说了系数不为0
        // if (coe != 0)
        for (int j = 0; j < 1001; ++j)
            // 指数相加,系数相乘
            c[j + exp] += a[j] * coe;
    }
    // 统计结果非零项个数
    int cnt = 0;
    for (int i = 0; i < 2001; ++i)
        if (c[i] != 0)
            cnt++;
    // 打印,末尾不能有多余空格,按指数从高到低,一位小数
    cout << cnt;
    for (int i = 2000; i >= 0; --i)
        // 系数不为0才需要输出
        if (c[i] != 0)
            printf(" %d %.1f", i, c[i]);

    return 0;
}