PAT 1002 A+B for Polynomials (25分)

题目

This time, you are supposed to find A+B where A and B are two polynomials.

Input Specification:

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≤N

K <⋯<N2 <N1 ≤1000.

Output Specification:

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

题目解读

给出两个多项式，每个输入格式是非零项个数指数1 系数1 指数2 系数2

让计算两多项式的和，并按照指定格式输出 非零项个数指数1 系数1 指数2 系数2

要求顺序是指数从高到低。

思路解析

可以用一个结构体来保存每一项的指数和系数，然后在第二次输入时根据去找到相应的那一项，对其系数进行修改。
这样做既浪费存储空间也浪费时间，但一般都能想到，更好的做法是，用一个数组来取代整个结构体，每一项的指数作为数组的索引，系数作为值，这样在读入时，直接找到对应位置进行修改，对数组的访问是很快的。
之后一次遍历，统计出数组不为0的个数，就是非零项的个数；然后对数组从后往前输出每个非零项对应的下标和值，就是结果。

代码

#include <iostream>

using namespace std;

int main() {

    // 指数作为下标，系数作为值，题目给出指数最多为1000

    float pols[1001] = {0};

    int k, exp;

    float coe;

    int cnt = 0;

    // 每一个样例是两行

    for (int i = 0; i < 2; ++i) {

    	// 第一个整数是说明后面有几个非0项

        cin >> k;

        for (; k > 0; --k) {

        	// 指数 系数 指数 系数

            cin >> exp >> coe;

            pols[exp] += coe;

        }

    }

    // 统计非零项

    for (int i = 0; i < 1001; ++i) {

        if (pols[i] != 0) cnt++;

    }

    // 输出非零项个数

    cout << cnt;

    // 按 指数 系数，从高到底输出，空格分隔

    for (int i = 1000; i >= 0; --i) {

        if (pols[i] != 0) {

            printf(" %d %.1f", i, pols[i]);

        }

    }

    return 0;

}

巴特西

PAT 1002 A+B for Polynomials (25分)

题目

题目解读

思路解析

代码

最新文章

热门文章