题目描述
给定两个多项式 A 和 B,计算 A×B 的结果。
输入格式
共两行,每行包含一个多项式的信息,格式如下:
K N1 aN1 N2 aN2 … NK aNK
其中,K 表示多项式中非零项的数量,Ni 和 aNi 分别表示其中一个非零项的指数和系数。
输出格式
按照与输入相同的格式,输出 A×B 的结果。
结果中的各项的系数均保留一位小数。
数据范围
K 为整数,1≤K≤10。
Ni 为整数,0≤NK<⋯<N2<N1≤1000。
aNi 为浮点数,−100≤aNi≤100。
输入样例:
2 1 2.4 0 3.2
2 2 1.5 1 0.5
输出样例:
3 3 3.6 2 6.0 1 1.6
算法1
代码模拟初中时候的多项式乘法
也就是使用double数组存储多项式
指数就是系数在数组中的下标
2.7 * $x$ 就是 double arrA[1]=2.7
1.2 * $x^2$ 存储方式为 double arrA[2]=1.2
5.3 * $x^9$ 存储方式为 double arrA[9]=5.3
那么两数相乘就是
double arrA[N] double arrB[N] double arrC[N];
arrC[i+j] = arrA[i] * arrB[j];
由于double存储存在误差 所以判断double是否为零 是判断它与零的差是否小于一个极小值。
我这里也写了一个函数 IsZero()
C++ 代码
// 1123555.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <vector>
using namespace std;
const int N = 1010;
double arrA[N], arrB[N], arrC[2*N];
int a, b,t;
bool IsZero(double x)
{
if (x - 0 > 1e-8 || 0 - x > 1e-8) {return false;}
return true;
}
int main()
{
scanf("%d", &a);
for (int i = 0; i < a; i++) {
scanf("%d",&t); scanf("%lf", &arrA[t]);
}
scanf("%d", &b);
for (int i = 0; i < b; i++) {
scanf("%d", &t); scanf("%lf", &arrB[t]);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (IsZero(arrA[i]) == false && IsZero(arrB[j]) == false)
{
arrC[i + j] += arrA[i] * arrB[j];
}
}
}
int count = 0;
for (int i = 0; i < 2 * N; i++) {
if (IsZero(arrC[i]) == false) count++;
}
cout << count;
for (int i = 2*N - 1; i >= 0; i--) {
if (IsZero(arrC[i]) == false) {
printf(" %d %.1lf",i,arrC[i]);
}
}
printf("\n");
return 0;
}