目錄

• [PAT Advanced Level] 1009 Product of Polynomials
• • 題目
  • 題解
  • 參考

[PAT Advanced Level] 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 K N_1 a_{N1} N_2 a_{N2}...N_K a_{NK} KN1​aN1​N2​aN2​...NK​aNK​,where K is the number of nonzero terms in the polynomial, N i N_i Ni​ and a N i a_{N_i} aNi​​ ( i = 1 , 2 , ⋯ , K ) (i=1,2,⋯,K) (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10, 0≤ N K N_K NK​ <⋯< N 2 N_2 N2​ < N 1 N_1 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.

輸入給出兩組多項式A、B，求A*B。輸入每一行，第一位為非零項的個數，後續分别為指數、系數、指數、系數。

示例

輸入：
2 1 2.4 0 3.2
2 2 1.5 1 0.5

輸出：
3 3 3.6 2 6.0 1 1.6
           

題解

先以結構體形式儲存一組多項式的系數，指數由序号表示，然後輸入第二組系數與第一組進行循環相乘，并加到對應指數的系數上，最後輸出所有非零系數的項。

答案ans的系數數組至少要開到2001，因為兩個最高次幂為1000的多項式相乘，最高幂次可以達到2000。

#include <cstdio>
struct Poly
{
    int exp;    //指數
    double cof;     //系數
} poly[1001];       //第一個多項式

double ans[2001];       //結果
int main()
{
    int n,m,number=0;
    scanf("%d",&n);     //第一個多項式中非零系數的項數
    for(int i=0;i<n;i++)
    {
        scanf("%d %lf",&poly[i].exp,&poly[i].cof);
    }
    scanf("%d",&m);     //第二個多項式中非零系數的項數
    for(int i=0;i<m;i++)
    {
        int exp;
        double cof;
        scanf("%d %lf",&exp,&cof);      //第二個多項式的指數和系數
        for(int j=0;j<n;j++)
        {
        ans[exp+poly[j].exp]+=(cof*poly[j].cof);
        }
    }
    for(int i=0;i<=2000;i++)
    {
        if(ans[i]!=0.0) number++;       //累計非零系數的項數
    }
    printf("%d",number);
    for(int i=2000;i>=0;i--)
    {
        if(ans[i]!=0.0)     printf(" %d %.1f",i,ans[i]);    //保留1位小數輸出
    }
return 0;
}
           

參考

[算法筆記-上機訓練實戰指南-胡凡]