1009.Product of Polynomials

2017-11-02

英文描述

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

中文描述

多项式乘积
此时，你应当在多项式A和B中求得A乘B
输入规格：
每个文件包含一个测试用例。每个用例占据2行，并且每一行包含一个多项式的信息：K N1 aN1 N2 aN2 … NK aNK，在多项式中K是一个非零的数字，Ni 和 aNi (i=1, 2, …, K)是指数和系数。给定1 <= K <= 10, 0 <= NK < … < N2 < N1 <=1000.
输出规格：
对于每个测试用例你应该在一行内输出A和B的乘积，输出格式和输入格式相同。注意行末没有空格。小数点精确到一位。
样例输入:
2 1 2.4 0 3.2
2 2 1.5 1 0.5
样例输出:
3 3 3.6 2 6.0 1 1.6

分析与解题

起初我一直在纠结这种运算是否和真正上的数学运算是相同的，所以总是有些迷惑。当通过后，我发现这种多项式乘积的运算和数学上的乘积运算完全是两回事。但是在这个题中你有得揣摩这个作者自定义的运算，又得去结合实际数学上的运算而考虑到作者没有说的事情，比如在这个题中，作者变没有说不输出系数为零的项。所以这个题在算法上没太多难度，时间全花费在了去揣摩题意。
昨天晚上看到凌晨三点钟，终于把自己的代码修改成通过了的。期间也查阅了很多其他人的代码，最简单的方法是打表的方法，速度也最快，当然耗费了额外多的存储空间，我的思路是比较简单的插入和更新策略，但相比打表方法稍微复杂一些。

C语言实现

/*	A*B,指数相加，系数相乘，系数为0不输出
*	calc() 如果指数相同就就更新系数的值
*	否则就将指数和系数插入，在更新后判断
*	系数是否为0，为0就删除，这样的策略是
*	存在一个bug的，但题中却通过了，bug
*	描述，如果输入：1 1 0和1 2 0这个算法
*	会输出：1 3 0.0，此处系数为0，却输出

*	关于这点题中也没有明确给出，就如实例
*	中所举出的，只有1项，而对于k是输出0
*	还是不输出，显然，就这测试结果来讲
*	你想怎样就怎样

*	sort() 计算出来的结果不一定是按照系数
*	递减进行输出的，故排个序。
*/
#include<stdio.h>
int ex1[11];     //指数
int ex2[11];     //指数
double coe1[11]; //系数
double coe2[11]; //系数
int k1, k2;
int exr[101];
double coer[101];
int c = 1;   //最终输出的k，也就是有几项
void calc()
{
	int i = 1;
	while(i <= k1)
	{
		int j = 1;
		while(j <= k2)
		{
			int te;
			double tc;
			te = ex1[i] + ex2[j];	
			tc = coe1[i] * coe2[j];
			int k = 1;
			int f = 0;
			while(k <= c)
			{
				if(te == exr[k])
				{
					f = 1;
					coer[k] += tc;
					if(coer[k] == 0)
					{
						c--;
					}
					break;
				}
				k++;
			}
			if(f == 0)
			{
				exr[c] = te;
				coer[c] = tc;
				c++;
			}
			j++;
		}
		i++;
	}
}
void input()
{
	scanf("%d", &k1);
	int i = 1;
	while(i <= k1)
	{
		scanf("%d", &ex1[i]);
		scanf("%lf", &coe1[i]);
		i++;;
	}
	scanf("%d", &k2);
	i = 1;
	while(i <= k2)
	{
		scanf("%d%lf", &ex2[i], &coe2[i]);
		i++;
	}
}
void output()
{
	int i = 1;
	printf("%d", c - 1);
	while(i <= c - 1)
	{
		printf(" %d %.1lf", exr[i], coer[i]);
		i++;
	}
}
void sort()
{
	int i = 1;
	while(i <= c - 1)
	{
		int j = i + 1;
		while(j <= c - 1)
		{
			if(exr[i] < exr[j])
			{
				int t = exr[i];
				exr[i] = exr[j];
				exr[j] = t;
				double d = coer[i];
				coer[i] = coer[j];
				coer[j] = d;
			}
			j++;
		}
		i++;
	}
}
int main()
{
	input();
	calc();
	sort();
	output();
	return 0;
}

测试链接

click me