PAT (Advanced Level)-1002. A+B for Polynomials (25)

PAT (Advanced Level)-1002. A+B for Polynomials (25)

1002. A+B for Polynomials (25)

时间限制
400 ms
内存限制
65536 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue


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.
每次输入包含两行内容。每一行都包含一个多项式的信息:
K N1 aN1 N2 aN2 … NK aNK

K是多项式共包含几项。K满足[1, 10]
Nk是多项式项的指数。Nk满足0 <= NK < … < N2 < N1 <=1000
aNk是多项式中Nk次项的系数

程序输入默认严格按照从高次幂项到低次幂项依次输入。

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 Input

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

解读

这个过程,用数组实现最简单。
数组的第i位刚好存第i次方幂项的系数。

所以我们创建一个1001位的double型数组(初始化为0)

  • (从第0次方项(常数项)到第1000次方项,一共1001项)
  • (系数要保留一位小数)

然后我们进行输入

  1. 第一次输入,先用一个量存输入有多少项。(比如第1次就是k1项)
  2. 然后进行对多项式信息输入的存储,一个量存指数,一个量存系数。
  3. 输入完一组指数和系数之后,向数组对应的位置存好系数就好。
  4. 待输入完后,进行第二次输入。同样的先用一个量存输入有多少项(k2)。
  5. 重复第2,3步。
  6. 需要注意的是,由于我们数组初始就全部为0,所以我们在向对应位置存入的时候,可以直接进行对应的加和(见代码)

然后输出

  1. 输出时候,先要计算一下加和之后还有多少项。
    • 这个时候我们就需要统计数组里面存入的数据有多少项不为零。计数,然后输出计数的数量。
  2. 然后我们输出多项式信息,即输出数组。
    • 由于高次项在前,而数组是升序排列的,所以我们对数组需要反着来一个个输出。
    • 输出所有不为0的项(即多项式的aNk),同时输出当前项所在数组的位数(即多项式的Nk)

完整代码

#include<iostream>  
#include<iomanip>  
using namespace std;

int main()
{
  double array[1001];// 创建数组
  //数组初始化为0
  for (int i = 0; i < 1001; i++)
  {
    array[i] = 0;
  }// 完成初始化
  
  int count = 0;// 计数变量
  
  //第一次输入开始
  int k1;
  cin >> k1;
  for (int i = 0; i < k1; i++)// 只进行k1次输入,因为只有k1项
  {
    int exponents;// 指数
    cin >> exponents;
    double coefficients;// 系数
    cin >> coefficients;

    array[exponents] += coefficients;// 等同于array[exponents] = array[exponents] + coefficients;
  }// 第一次输入结束

  // 第二次输入开始
  int k2;
  cin >> k2;
  for (int i = 0; i < k2; i++)
  {
    int exponents;
    cin >> exponents;
    double coefficients;
    cin >> coefficients;

    array[exponents] += coefficients;// 注意,这个时候就进行的两行的加和。
  }// 第二次输入结束

  //开始计算有多少项
  for(int i=0;i<1001;i++)
  {
    if (array[i] != 0)
    {
      count += 1;
    }
  }
  cout << count;//输出总项数 K
  
  //输出数组
  for (int i = 1000; i >= 0; i--)// 反序
  {
    if (array[i] != 0)
      cout <<fixed << setprecision(1) << " " << i << " " << array[i];
  }

  return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注