1002.A + B for Polynomials

2017-08-12

英文描述

A + B for Polynomials(25)
This time, you are supposed to find A + B where A and B are tow polynomials.
Input Specification:
Each input file contains one test case. Each case occupies lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2……NK aNK, where K is 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 sum of A and B in one line, with the same format as the input. Notice must be NO extra space at the end of each line.Please be accurate to 1 decimal palce.
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

中文描述

多项式A + B

已知多项式A和B，求A+B
输入规格：
每一个输入文件包含一个测试用例。每一个用例占据了一些行，每一行包含了一个多项式的信息：K N1 aN1 N2 aN2…NK aNK，在多项式里K是一个非零项，Ni和aNi(i=1, 2, … ,K)是指数和系数。设1 <= K <= 10，0 <= NK < … < N2 < N1 <=1000。
输出规格：
对于每一个测试用例在一行内输出，输出格式同输入格式相同。输出的最后一个字符不能是空格。小数点精确都后1位。
样例输入:
73 10
23 2
23 10
-2
样例输出:
Yes
Yes
No

分析与解题

根据样例输入和输出初步得到，输入第一行为多项式A，输入第二行为多项式B，输出结果是合并同类项相关操作：指数相同系数相加减。隐含条件，如果系数为0则不用输出此项。例如：A = 3^2 + 0 ^3；B = 4^2，则结果A+B = 7^2。输入。根据条件Ni and aNi(i=1, 2, …, K)，用一个整形数字来接受输入数据K。定义结构体数组，来接受输入数据Ni和aNi。计算。结构体数组A代替多项式A，结构体数组B代替多项式B。求A + B，如果A中指数同B中指数相同，则将A + B的系数存放在B中，否则，将A中指数和系数插入到B中。遍历数组A，查找A中每一个指数是否在B中出现，如果出现就更新B数组中系数的值，否则就将A数组中指数和系数插入到B数组。因此，定义三个辅助函数。Search（）：查找结构体数组A是否包含指数x；Update（）：根据指定下标更新系数值；Insert（）：将指定指数和系数插入到结构体数组中。考虑隐含条件，将B中系数不等于0的提取出，存放在C中。输出。将结构体数组C输出。

C语言实现

/* A + B for Polnomials 
*  Input() 输入多项式

*  Output() 输出多项式

*  Search() 查找指数值，成功返回下标，失败返回-1

*  Update() 根据下标更新数组中系数

*  Insert() 向数组中插入指数和系数（有序表中插入元素使之依然有序）

*  Calc() 计算多项式A + B，并将结果存在多项式B中

*  DeleteForCore() 将Calc()计算结果多项式B中系数为0的数剔除，返回最终结果多项式C
*/
#include<stdio.h>
typedef struct
{
	int exp[30];
	double coe[30];
	int size;
}FA;
void Input(FA *a)
{
	int k = 0;
	scanf("%d", &k);
	int i = 0;
	while(i < k)
	{
		scanf("%d%lf", &a->exp[i], &a->coe[i]);
		i++;
	}
	a->size = k;
}
void Output(FA *a)
{
	if(a->size != 0)
	{
		int i = 0;
		printf("%d", a->size);
		while(i < a->size)
		{
			printf(" %d %.1f", a->exp[i], a->coe[i]);
			i++;
		}
		puts("");
	}
}
int Search(FA *a, int exp)
{
	int i = 0;
	while(i < a->size)
	{
		if(a->exp[i] == exp)
			return i;
		i++;
	}
	return -1;
}
void Update(FA *a, int subscript, double coe)
{
	a->coe[subscript] += coe;
}
void Insert(FA *a, int exp, double coe)
{
	int i = a->size - 1;
	a->size += 1;
	while(i >= 0)
	{
		a->exp[i + 1] = a->exp[i];
		a->coe[i + 1] = a->coe[i];
		if(a->exp[i] > exp)
		{
			a->exp[i + 1] = exp;
			a->coe[i + 1] = coe;
			return ;
		}
		i--;
	}
	a->exp[0] = exp;
	a->coe[0] = coe;
}
FA DeleteForCoe(FA *a)
{
	int i = 0;
	int size = a->size;
	FA c;
	c.size = 0;
	while(i < a->size)
	{
		if(a->coe[i] != 0)
		{
			c.exp[c.size] = a->exp[i];
			c.coe[c.size] = a->coe[i];
			c.size++;
		}
		i++;
	}
	return c;
}
void Calc(FA *a, FA *b)
{
	int i = 0;
	int t = 0;
	while(i < a->size)
	{
		t = Search(b, a->exp[i]);
		if(t != -1)
			Update(b, t, a->coe[i]);
		else
			Insert(b, a->exp[i], a->coe[i]);
		i++;
	}
}
int main()
{
	FA a;
	FA b;
	Input(&a);
	Input(&b);
	Calc(&a, &b);
	FA c = DeleteForCoe(&b);
	Output(&c);
	return 0;
}

测试链接

click me