[PAT解题报告] Product of Polynomials
这个题和1002类似，1002是多项式加法，这个是多项式乘法。输入输出格式完全一样，数据范围也一样。我还是同样的建议：用数组存多项式的系数，而不要用链表——因为链表容易错。不过要注意两个1000次的多项式相乘，结果可能到2000次——注意数组别开小了。还有就是注意0的判断，这一点和1002一样。相乘采取的就是两重循环。
c[i + j] += a[i] * b[j]这样了。
代码：
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
const double eps = 1.e-8;
double a[1024],b[1024],c[2048];
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);
}
for (int i = 0; i <= 1000; ++i) {
for (int j = 0; j <= 1000; ++j) {
c[i + j] += a[i] * b[j];
}
}
int num = 0;
for (int i = 2000; i >= 0; --i) {
if (fabs(c[i]) >= eps) {
++num;
}
}
printf("%d",num);
for (int i = 2000; i >= 0; --i) {
if (fabs(c[i]) >= eps) {
printf(" %d %.1lf",i,c[i]);
}
}
puts("");
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1009
查看10道真题和解析