1002. A+B for Polynomials

xiaoxiao2021-02-28  1

A+B for Polynomials

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

Input

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

Sample Output

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

#include <stdio.h> #define maxSize 1001 struct poly_arr { double poly[maxSize]; int max_index; // 系数非零项的最大指数 int count; // 非零项个数 }; void init_poly(poly_arr &X) { int i; X.max_index = 0; X.count = 0; for (i=0; i < maxSize; ++i) X.poly[i] = 0; } void insert_poly(poly_arr &X) { int expo; double coef; scanf("%d %lf", &expo, &coef); X.poly[expo] = coef; ++X.count; if (X.max_index < expo) // 更新多项式最大指数 X.max_index = expo; } void add_poly(poly_arr A, poly_arr B, poly_arr &C) { int i; int max; max = A.max_index > B.max_index ? A.max_index : B.max_index; for (i = 0; i <= max; ++i) if (A.poly[i] != 0.0 || B.poly[i] != 0.0) { C.poly[i] = A.poly[i] + B.poly[i]; if (C.poly[i] != 0.0) // 规范应该为fabs(x - 0.0) > 1e-8 { ++C.count; C.max_index = i; // 系数非零时才更新最大指数 } } } void print_poly(poly_arr X) { int i; printf("%d", X.count); for (i = X.max_index; i >= 0; --i) if (X.poly[i] != 0.0) printf(" %d %.1lf", i, X.poly[i]); } int main(void) { poly_arr A, B, C; int k; int i; init_poly(A); init_poly(B); init_poly(C); scanf("%d", &k); for (i = 0; i < k; ++i) insert_poly(A); scanf("%d", &k); for (i = 0; i < k; ++i) insert_poly(B); add_poly(A, B, C); print_poly(C); }

#include <stdio.h> #define maxSize 1001 struct poly { double arr[maxSize]; int count; int max_index; }; void init_poly(poly &X) { X.count = 0; X.max_index = 0; for (int i = 0;i < maxSize; ++i) X.arr[i] = 0; } void add_poly(poly &X) { double coef; int expo; scanf("%d %lf", &expo, &coef); if (X.arr[expo] == 0.0) // 原系数为零时项数+1 ++X.count; X.arr[expo] = X.arr[expo] + coef; if (X.arr[expo] == 0.0) // 相加后系数为零时项数-1 --X.count; if (X.max_index < expo) // 更新最大指数 X.max_index = expo; } void print_poly(poly X) { printf("%d", X. count); for (int i = X.max_index; i >= 0; --i) if (X.arr[i] != 0.0) printf(" %d %.1lf", i, X.arr[i]); } int main(void) { int i, j, K; poly C; init_poly(C); for (i = 0; i < 2; ++i) { scanf("%d", &K); for (j=0; j<K; ++j) add_poly(C); } print_poly(C); }