「PAT甲级真题解析」Advanced Level 1009 Product of Polynomials

Table of Contents

问题分析

  1. 题设要求计算两个多项式的积, 同题目1002一样, 多项式求积是有固定步骤的, 所以这是一道模拟题。
  2. 多项式求积的规则为: 将两个多项式中的项两两相乘, 相乘得到的结果项指数为两个项的和, 系数为两个项的乘积。
  3. 这意味着我们只需要用一个两重循环就可以覆盖所谓的"两两相乘", 将所有求得的结果项相加就是题设要求的多项式乘积。

完整步骤描述

  1. 根据指数的取值范围[0, 1000], 设置长度为2001的乘积结果数组并初始化各个值为0, 数组索引表示指数的值
  2. 设置长度为1001的数组并初始化各个值为0, 用来存储输入的多项式;
  3. 获取输入多项式A: 项数, 每项的指数和系数
    • 读取的指数作为索引, 数组对应索引位置的值加上系数的值
  4. 获取输入多项式B: 项数, 每项的指数和系数
    • 对于每一项:
      • 遍历存储的多项式A, 将当前项乘以多项式A的非零项, 结果存到结果数组中
  5. 统计结果数据中的非零项个数
  6. 输出非零项个数, 输出每一个非零项的指数和系数

伪代码描述

  1. init recorders:
    • result[2001] = {0};
    • ploy[1001] = {0}
  2. get input: item_amount (of Polynomial A)
  3. for (int i = 0; i < item_amount; i++):
    • get input: item_exponent, item_coefficient
    • ploy[item_exponent] = item_coefficient;
  4. get input: item_amount (of Polynomial B)
  5. for (int i = 0; i < item_amount; i++):
    • get input: item_exponent, item_coefficient
    • for (int j = 0; j < 1001; j++):
      • result[j+item_exponent] += ploy[j] * item_coefficient;
  6. init recorder:
    • nonzero_item_count = 0;
  7. for (int i = 0; i < 2001; i++):
    • if result[i] != 0.0:
      • nonzero_item_count++;
  8. print(nonzero_item_count);
    1. for (int i = 0; i < 2001; i++):
    • if result[i] != 0.0:
      • printf(result[i]);

完整提交代码

1/*
2# 问题分析
3题设要求计算两个多项式的积, 同题目1002一样, 多项式求积是有固定步骤的, 所以这是一道模拟题。
4多项式求积的规则为: 将两个多项式中的项两两相乘, 相乘得到的结果项指数为两个项的和, 系数为两个项的乘积。
5这意味着我们只需要用一个两重循环就可以覆盖所谓的"两两相乘", 将所有求得的结果项相加就是题设要求的多项式乘积。
6
7# 完整步骤描述
81. 根据指数的取值范围[0, 1000], 设置长度为2001的乘积结果数组并初始化各个值为0, 数组索引表示指数的值
92. 设置长度为1001的数组并初始化各个值为0, 用来存储输入的多项式;
103. 获取输入多项式A: 项数, 每项的指数和系数
11    - 读取的指数作为索引, 数组对应索引位置的值加上系数的值
124. 获取输入多项式B: 项数, 每项的指数和系数
13    - 对于每一项:
14        - 遍历存储的多项式A, 将当前项乘以多项式A的非零项, 结果存到结果数组中
155. 统计结果数据中的非零项个数
166. 输出非零项个数, 输出每一个非零项的指数和系数
17
18# 伪代码描述
191. init recorders:
20    - result[2001] = {0};
21    - ploy[1001] = {0}
222. get input: item_amount (of Polynomial A)
233. for (int i = 0; i < item_amount; i++):
24    - get input: item_exponent, item_coefficient
25    - ploy[item_exponent] = item_coefficient;
264. get input: item_amount (of Polynomial B)
275. for (int i = 0; i < item_amount; i++):
28    - get input: item_exponent, item_coefficient
29    - for (int j = 0; j < 1001; j++):
30        - result[j+item_exponent] += ploy[j] * item_coefficient;
316. init recorder:
32    - nonzero_item_count = 0;
337. for (int i = 0; i < 2001; i++):
34    - if result[i] != 0.0:
35        - nonzero_item_count++;
368. print(nonzero_item_count);
379. 7. for (int i = 0; i < 2001; i++):
38    - if result[i] != 0.0:
39        - printf(result[i]);
40*/
41
42# include<iostream>
43using namespace std;
44
45int main(){
46    double result[2001] = {0};
47    double ploy[1001] = {0};
48    int item_amount;
49    cin >> item_amount;
50    int exponent;
51    double coefficient;
52    for (int i = 0; i < item_amount; i++){
53        cin >> exponent >> coefficient;
54        ploy[exponent] = coefficient;
55    }
56    cin >> item_amount;
57    for (int i = 0; i < item_amount; i++){
58        cin >> exponent >> coefficient;
59        for (int j = 0; j < 1001; j++){
60            if (ploy[j] != 0.0){
61                result[j+exponent] += ploy[j] * coefficient;
62            }
63        }
64    }
65    
66    int nonzero_item_count = 0;
67    for (int i = 0; i < 2001; i++){
68        if (result[i] != 0.0)
69            nonzero_item_count++;
70    }
71    
72    cout << nonzero_item_count;
73    for (int i = 2000; i > -1; i--){
74        if (result[i] != 0.0)
75            printf(" %d %.1f", i, result[i]);
76    }
77    return 0;
78}
79
Mastodon