PAT (Advanced Level) Practice 1009 Product of Polynomials

如果对你有帮助，要点个赞让我知道喔~

文章目录

• 问题分析
• 完整步骤描述
• 伪代码描述
• 完整提交代码

问题分析

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);
9. 7. for (int i = 0; i < 2001; i++):
   • if result[i] != 0.0:
     • printf(result[i]);

完整提交代码

/*
# 问题分析
题设要求计算两个多项式的积, 同题目1002一样, 多项式求积是有固定步骤的, 所以这是一道模拟题。
多项式求积的规则为: 将两个多项式中的项两两相乘, 相乘得到的结果项指数为两个项的和, 系数为两个项的乘积。
这意味着我们只需要用一个两重循环就可以覆盖所谓的"两两相乘", 将所有求得的结果项相加就是题设要求的多项式乘积。# 完整步骤描述
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);
9. 7. for (int i = 0; i < 2001; i++):- if result[i] != 0.0:- printf(result[i]);
*/# include
using namespace std;int main(){double result[2001] = {0};double ploy[1001] = {0};int item_amount;cin >> item_amount;int exponent;double coefficient;for (int i = 0; i < item_amount; i++){cin >> exponent >> coefficient;ploy[exponent] = coefficient;}cin >> item_amount;for (int i = 0; i < item_amount; i++){cin >> exponent >> coefficient;for (int j = 0; j < 1001; j++){if (ploy[j] != 0.0){result[j+exponent] += ploy[j] * coefficient;}}}int nonzero_item_count = 0;for (int i = 0; i < 2001; i++){if (result[i] != 0.0)nonzero_item_count++;}cout << nonzero_item_count;for (int i = 2000; i > -1; i--){if (result[i] != 0.0)printf(" %d %.1f", i, result[i]);}return 0;
}