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

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

·
#c++#算法#pat考试#需求分析#数据结构

Table of Contents

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);
    1. 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<iostream>
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;
}
 
「PAT甲级真题解析」Advanced Level 1009 Product of Polynomials | 生活糖果