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

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79