[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