1002 A+B for Polynomials（多项式的A+B）

曾经终败给现在 2022-04-15 06:11 260阅读 0赞

### problem description ###

This time, you are supposed to find A+B where A and B are two polynomials.

### 题目描述 ###

这一次，你应该找到A，B，其中A和B是两个多项式。

#### 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.

#### 输入格式： ####

每个输入文件包含一个测试用例。每一种情况占 2 行，每行包含多项式信息：K N1 aN1 N2 aN2 … NK aNK，其中 K 是多项式中的非零项数， Ni 和 aNi ( i=1，2，⋯，K)分别是指数和系数。给出了 1 ≤ K ≤ 10 ， 0 ≤ NK < ⋯ < N2 < N1 ≤ 1000 。

#### Output Specification: ####

For each test case you should output the sum 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 to 1 decimal place.

#### 输出格式： ####

对于每个测试用例，您应该在一行中输出A和B的和，其格式与输入相同。请注意，每一行的末尾必须没有多余的空格。请精确到小数点1位。

#### Sample Input: ####

2 1 2.4 0 3.2
    2 2 1.5 1 0.5

#### 输入样例： ####

2 1 2.4 0 3.2
    2 2 1.5 1 0.5

#### Sample Output: ####

3 2 1.5 1 2.9 0 3.2

#### 输出样例： ####

3 2 1.5 1 2.9 0 3.2

*思路*  
  步骤1：令 double 型数组 p\[max\_n\] 表示多项式，其中 p\[n\] 表示幂次为 n 的项的系数，初值为 0 。令 int 型变量 count 表示系数非零项的个数，初值为 0 。  
  步骤2：先按输入格式读入第一个多项式，再读入第二个多项式，并把对应系数直接加到第一个多项式上。  
  步骤3：计算非零系数项的个数 count 并输出，然后按格式输出该多项式。

*注意*  
  ① 输出要按照幂次从大到小的顺序，格式上需要保留一位小数。  
  ② 题目的输入和输出都是系数非零项。  
  ③ 有些人会选择在读入的过程中就使用 count 计数，这里要注意正负抵消的问题：两个多项式的某一个相同幂次的项刚好为相反数，相加之后就为 0 了。因此采用下面这个写法的要注意 count 必须在两项相加之后再判断是否自减。

scanf("%d", &k);
    count += k;
    for(i=0; i<k; i++) { 
    	scanf("%d%lf", &n, &a);
    	p[n] += a;
    }
    scanf("%d", &k);
    count += k;
    for(i=0; i<k; i++) { 
    	scanf("%d%lf", &n, &a);
    	p[n] += a;
    	if(p[n] != 0) count--;
    }

这里不妨试试下面这组数据，结果应该是 3 4 0.5 3 -2.1 0 3.6

4 4 0.5 2 5.6 1 -2 .7 0 3.6
    3 3 -2.1 2 -5.6 1 2.7

④ count 初值为 0 然后在第二个多项式累加时进行 count 自增的做法是不可取的，因为第一个多项式的系数非零项在第二个多项式中该项系数为零，这样无法被处理到。  
  ⑤ 在输出每一个非零系数项时，必须注意幂次为 1000 是可以去得到的，所以循环的最大值至少要取 1000 而不是 999，并且 p 数组的大小至少是 1001 ，循环中不能出现 i < 1000 这种。  
  ⑥ 出现 “ 格式错误 ” 是因为在输出的末尾多加了一个空格，只需注意空格的输出即可。  
代码：

#include <stdio.h>
    const int maxn = 1111;
    double p[maxn] = { }; // 多项式
    int main() { 
        int k, n, count = 0; // k 多项式中非零项的个数 n 多项式中项的指数 count 系数非零项的个数 
        double a; // 多项式中项的系数
        scanf("%d", &k);
        for(int i = 0; i < k; i++) { 
            scanf("%d %lf", &n, &a);
            p[n] += a;
        }
        scanf("%d", &k);
        for(int i = 0; i < k; i++) { 
            scanf("%d %lf", &n, &a);
            p[n] += a; // 第二个多项式与第一个多项式相加
        }
        for(int i = 0; i < maxn; i++) { 
            if(p[i] != 0) { 
                count++; // 计算加后的非零项
            }
        }
        printf("%d", count);
        for(int i = maxn; i >= 0; i--) { 
            if(p[i] != 0) { 
                printf(" %d %.1f", i, p[i]);
            }
        }
        return 0;
    }

结果：  
![在这里插入图片描述][20181122173555848.png]

[20181122173555848.png]: /images/20220415/d32fb16393544f45ae429561fc113876.png