算法分析

题目给定多项式中每一项的指数和系数，对多项式进行相乘，例如$(3x^2 + 2x^3) * (x^2 + x) = 3x^3 + 5x^4 + 2x^5$

• 1、开一个c[]数组，c[i]存储的是指数是i的系数是c[i]
• 2、将A多项式的指数和系数存在a[]数组中，B多项式的指数和系数存在b[]数组中
• 3、将A多项式与B多项式的每一项进行相乘，系数相乘，指数相加，即将a[]数组中每个元素与b[]数组中的每个元素进行相乘，结果存在c[]中，即c[i + j] += a[i] * b[j]
• 4、将c[]数组中存的指数和系数从大到小输出

时间复杂度 $O(n * m)$

参考文献

pat

C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1010;
double a[N], b[N], c[N * 2];

int main()
{
    int n,m;
    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        int x;//指数
        double y;//系数
        cin >> x >> y;
        a[x] += y;
    }
    cin >> m;
    for(int i = 0;i < m;i ++)
    {
        int x;
        double y;
        cin >> x >> y;
        b[x] += y;
    }
    for(int i = 0;i <= 1000;i ++)
        for(int j = 0;j <= 1000;j ++)
            c[i + j] += a[i] * b[j];

    int k = 0;
    for(int i = 0;i <= 2000;i ++)
        if(c[i] != 0)
            k ++;

    cout << k ;
    for(int i = 2000;i >= 0;i --)
        if(c[i] != 0)
        {
            printf(" %d %.1lf", i, c[i]);
        }

    return 0;
}