PAT 1009 Product of 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≤NK <⋯<N2 <N1 ≤1000.
Output Specification:
For each test case you should output the product 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 up to 1 decimal place.
Sample Input:
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output:
3 3 3.6 2 6.0 1 1.6
题目解析
给出两个多项式,每个输入格式是 非零项个数 指数1 系数1 指数2 系数2
让计算两多项式的 乘积,并按照指定格式输出 非零项个数 指数1 系数1 指数2 系数2
要求顺序是指数从高到低。
思路
前面写过一个多项式求和的题 PAT 1002 A+B for Polynomials (25分),两个思想以及处理方式是一样的,只不过一个是加法,一个是乘法,区别就在于:加法,只有指数相同的项,系数才能相加;对于乘法,指数不同的两项,相乘以后得到一个新指数项(原指数相加,系数相乘)。
- 用一个
数组
来存储多项式,每一项的指数
作为数组的索引
,系数
作为值
,这样在读入时,直接找到对应位置进行修改,对数组的访问是很快的。 - 没必要用两个数组把两个多项式都保存后再进行乘法运算,那样时间复杂度和空间复杂度都比较高,还要进行很多不必要的运算,我们就用
一个数组
:初始化每一项都为0.0
,相当于所有指数项系数都为0,读入第一个多项式时,根据指数
和系数
改变对应位置的值即可;读入第二个多项式时,每读入一个非零项,就用它分别和数组的每一项做运算,得到的结果应该加到下标为两指数相加
的数组元素上。这样读入第二个多项式后,所有运算也做完了。 - 之后一次遍历,统计出数组
不为0
的个数,就是非零项的个数;然后对数组从后往前输出每个非零项对应的下标和值,就是结果。注意精确到小数点后1
位。
代码
#include <iostream>
using namespace std;
int main() {
// a,b是两个多项式,c是他们的乘积,指数作为下标,系数作为值,结果指数最高为2000
float a[1001] = {0.0}, c[2001] = {0.0};
int k; // 几个非零项
int exp; // 指数
float coe; // 系数
// 读入a
cin >> k;
while (k-- > 0) {
cin >> exp >> coe;
a[exp] = coe;
}
// 读入b的同时计算结果
cin >> k;
while (k-- > 0) {
cin >> exp >> coe;
// 这一项系数不为0,题目说了系数不为0
// if (coe != 0)
for (int j = 0; j < 1001; ++j)
// 指数相加,系数相乘
c[j + exp] += a[j] * coe;
}
// 统计结果非零项个数
int cnt = 0;
for (int i = 0; i < 2001; ++i)
if (c[i] != 0)
cnt++;
// 打印,末尾不能有多余空格,按指数从高到低,一位小数
cout << cnt;
for (int i = 2000; i >= 0; --i)
// 系数不为0才需要输出
if (c[i] != 0)
printf(" %d %.1f", i, c[i]);
return 0;
}
最新文章
- Djanog结合jquery实现ajax
- Python底层socket库
- POJ 3041	Asteroids 二分图匹配
- c# gridview数据列表中NamingContainer容器的用法
- codeforces GYM 100114 J. Computer Network 无相图缩点+树的直径
- Android中解析网络请求的URL
- acdream 1431 Sum vs Product
- 亲戚(relative)
- Mybatis:缓存,动态SQL,注解SQL以及动态标签使用
- 整理的Python零基础入门!转载他人的!
- IdentityServer4【Topic】之授权类型
- VS2015快捷键大全
- 基于Angular+WebAPI+OData的增删改查
- Java基类和派生类
- 洛谷 P2527 [SHOI2001]Panda的烦恼 解题报告
- Mahout 协同过滤 itemBase RecommenderJob源码分析
- HDU 1847 Good Luck in CET-4 Everybody! (博弈)
- 用PowerDesigner对现有的数据库反向工程建立E-R图
- oracle根据四位年周取当周周一的日期函数
- 用C++/CLI搭建C++和C#之间的桥梁(二)—— 基本语法
热门文章
- http_response_code()和header()
- 小程序里button边框有黑线解决办法(自定义button样式)
- java零基础自学网站分享
- nginx开启ssl并把http重定向到https的两种方式
- visual stdio 2012快捷键
- 自动驾驶汽车数据不再封闭,Uber 开源新的数据可视化系统
- uniq 只能相邻行去重
- XML--XML作用
- 一个简单的wed服务器SHTTPD(1)————命令行和文件配置解析
- Unity 游戏框架搭建 2019 (四十二、四十三) MonoBehaviour 简化 &; 定时功能