[PAT解题报告] A+B for Polynomials
题目输入的是两个多项式，求的是两个多项式的和。
多项式使用非0项的系数和次数来表示的，并且是按降幂输入的。预先给出了非0项的个数（很小，不超过10）。
例如
2 1 2.4 0 3.2 表示2.4x + 3.2, 并且知道次数小于1000，输出也按同样格式输出，注意只输出非0项。
这个题类似于两个有序list的合并，因为多项式的加法无非就是合并同类项而已。
我们做题可以选择最不容易出错的方法，对于本题，因为次数不超过1000，我们用数组表示某个次数项对应的系数再方便不过了，而且数组比链表容易写，出错的可能性低。关键还是数据范围，次数才1000，如果次数达到109，尽管只有10项，我们无法用数组存放了——因为数组下标没法开那么大。
几个注意点：
（1）数组使用全局的——这样没出现的系数都自动是0了，并且全局的数组不在堆栈空间里。
（2）数组开大一点没关系……
（3）注意系数是实数，判断实数是否为0一般不用x == 0 而用fabs(x) <= eps (eps一般是1e-8,
1e-10)，好在本题对精度要求并不高。
代码：
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
const double eps = 1.e-8;
double a[1024],b[1024];
int main() {
int n;
for (scanf("%d",&n);n;--n) {
int x;
scanf("%d",&x);
scanf("%lf",a + x);
}
for (scanf("%d",&n);n;--n) {
int x;
scanf("%d",&x);
scanf("%lf",b + x);
}
int num = 0;
for (int i = 1000; i >= 0; --i) {
a[i] += b[i];
if (fabs(a[i]) >= eps) {
++num;
}
}
printf("%d",num);
for (int i = 1000; i >= 0; --i) {
if (fabs(a[i]) >= eps) {
printf(" %d %.1lf",i,a[i]);
}
}
puts("");
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1002
投递腾讯等公司7个岗位 >
美团开奖333人在聊