PTA 1002 A+B for Polynomials
题目翻译
现在,你需要求出a,b两个多项式的相加结果。
输入要求
每一个输入文件包含一个测试样例。每一个样例占两行并且每行包含多项式的信息:
\(k\space n_1 \space a_{n_1}\space n_2 \space a_{n_2} \space ...\space n_k \space a_{n_k}\)
这里k代表多项式中非零项的数量,\(n_i\)和\(a_{n_i}\)(\(i\)=1,2,...,k)分别是指数(exponents)和系数(coefficients)。\(1\leq k\leq 10\),\(0\leq n_k<...< n_2<n_1\leq1000\).
输出要求
对于一个测试样例,你需要在一行以相同格式输出a和b的和。注意行尾没有多余的空格。请精确到小数点后一位。
样例输入
2 1 2.4 0 3.2 2 2 1.5 1 0.5
样例输出
3 2 1.5 1 2.9 0 3.2
分析:因为题上没有说是按照从大到小的顺序输入的,并且在我经过测试后也发现输入时指数的顺序是混乱的。 所以我一开始的想法是建两个链表,链表里每个节点都是都存储系数和指数,然后把链表排序后再相加。但一想到要写链表的排序算法我就放弃了,而且代码出错的概率太高了。
之后在看过大佬的们的题解后,发现可以用类似桶排序的方法做。就是先开一个比指数的上限还要大的数组,里面全都初始化成0,然后读取一对指数和系数,就把指数对应的项加上读取系数的值。之后先从小到大数一遍非0项的个数,再从大到小输出即可。时间复杂度是\(o_{(n)}\)。
废话不多说,直接上代码。
#include <stdio.h> #define kmax 1001 float cof[kmax]; int main() { int k; scanf("%d", &k); int e; //e和c分别用来临时存储读取的指数和系数 float c; for (int i = 0; i < k; i++) { scanf("%d%f", &e, &c); cof[e] = c; } scanf("%d", &k); for (int i = 0; i < k; i++) { scanf("%d%f", &e, &c); cof[e] += c; //注意这里要用+=,因为a,b有相同的指数时,要加在一起 } int cot = 0; for (int i = 0; i < kmax; i++) //先正序遍历一遍,计算项的个数 if (cof[i] != 0) cot++; printf("%d", cot); for (int i = kmax - 1; i >= 0; i--) //最后倒序输出 if (cof[i] != 0) printf(" %d %.1f", i, cof[i]); return 0; }
上一篇: C++基础 学习笔记五:重载之运算符重载
下一篇: 漫画图片:男孩和女孩之间有纯洁的友谊吗?
推荐阅读
-
【PAT】A1002 A+B for Polynomials
-
【PAT甲级】【1002】 A+B for Polynomials (25分)
-
算法笔记第三章练习题_A+B for polynomials,product of polynomials,考试座位号
-
PTA 1002 A+B for Polynomials
-
PAT甲级——1002. A+B for Polynomials (25)(C++)
-
1002. A+B for Polynomials(25)—PAT 甲级
-
PTA甲级考试真题练习9——1009 Product of Polynomials
-
PTA刷题Advanced甲级——1002.A+B for Ploynomials——Day(1)
-
【PAT】A1002 A+B for Polynomials
-
[code] PTA 1001 A+B Format DAY001