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
给出两个多项式，每个输入格式是 非零项个数 指数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; }