游客 注册 | 登录
中文 | En

1286 - 算法2-23：一元多项式加法

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB
让我们重温小学初中时那些一元多项式的加法吧，不同的是现在使用计算机来帮我们计算了。多年前不想写作业的梦想终于快要实现了！下面就给出书上的算法。 

图：链表实现一元多项式加法

题目输入

输入数据包含多组测试数据，每组数据包含两行一元多项式。每个多项式包含若干对整数，每对整数的第一个是系数，第二个是指数。每个多项式不超过100项，整数间用空格隔开，并且指数是递减的。

题目输出

每组测试数据输出一行结果，每个整数后面空一格。(包括行尾)

输入/输出样例

输入格式

3 2 4 1 7 0
2 4 1 1
2 3
1 4
3 2 4 1 7 0
2 4 -4 1

输出格式

2 4 3 2 5 1 7 0 
1 4 2 3 
2 4 3 2 7 0

C语言解答

#include<stdio.h>
#include<string.h>
typedef struct
{
	int xishu;
	int zhishu;
}elemtype;
int main()
{
	elemtype a[100],b[100],c[200];
	int lena,lenb,lenc;
	char s1[101],s2[101],*t;
	int i,j;
	while(gets(s1) && strlen(s1))
	{
		gets(s2);
		lena=lenb=lenc=0;
		t=strtok(s1," \n\t");
		while(t)
		{
			sscanf(t,"%d",&a[lena].xishu);
			t=strtok(NULL," \n\t");
			sscanf(t,"%d",&a[lena].zhishu);
			t=strtok(NULL," \t\n");
			lena++;
		}
		t=strtok(s2," \n\t");
		while(t)
		{
			sscanf(t,"%d",&b[lenb].xishu);
			t=strtok(NULL," \n\t");
			sscanf(t,"%d",&b[lenb].zhishu);
			t=strtok(NULL," \t\n");
			lenb++;
		}
		i=j=0;
	while(i<lena && j<lenb)
	{
		if(a[i].zhishu>b[j].zhishu)
		{
			c[lenc].zhishu=a[i].zhishu;
			c[lenc].xishu=a[i].xishu;
			++i;++lenc;
		}
		else if(a[i].zhishu<b[j].zhishu)
		{
			c[lenc].zhishu=b[j].zhishu;
			c[lenc].xishu=b[j].xishu;
			++j;++lenc;
		}
		else if(a[i].zhishu==b[j].zhishu)
		{
			if(a[i].xishu+b[j].xishu)
			{
			c[lenc].zhishu=a[i].zhishu;
			c[lenc].xishu=a[i].xishu+b[j].xishu;
			++lenc;
			}
			++i;++j;
		}
	}
	while(i<lena)
	{
		c[lenc].xishu=a[i].xishu;
		c[lenc].zhishu=a[i].zhishu;
		++lenc;
		++i;
	}
	while(j<lenb)
	{
		c[lenc].xishu=b[j].xishu;
		c[lenc].zhishu=b[j].zhishu;
		++lenc;
		++j;
	}
	for(i=0;i<lenc;i++)
	    printf("%d %d ",c[i].xishu,c[i].zhishu);
	printf("\n");
	}
	return 0;
}

C++解答

#include <stdio.h>
#include <string.h>

struct ElemType{		// 定义多项式的每一项类型
	int coef;			// 系数
	int expn;			// 指数
};

int main(){

	ElemType a[110], b[110], r[220];	// 定义两个多项式以及他们的结果
	int lenA, lenB, lenR;				// 定义多项式 a,b,r 的项数
	char strA[1000], strB[1000], *tmp;	// 定义用来读取多项式的字符串，待会分解为整数
	int i, j;
	while(gets(strA) && strlen(strA)){	// 注意判断字符串 strA 的长度，防止有空行
		gets(strB);						// 读入字符串 strB
		lenA = lenB = lenR = 0;			// 首先令各多项式的项数为 0

		// 以下将字符串 a 放置到多项式 a 中
		tmp = strtok(strA, " \t\n");			// 注意这里传入的是字符串 strA
		while(tmp){
			sscanf(tmp, "%d", &a[lenA].coef);	// 从字符串中读取一个系数
			tmp = strtok(NULL, " \t\n");		// 注意这里传入的是 NULL
			sscanf(tmp, "%d", &a[lenA].expn);	// 从字符串中读取一个指数
			tmp = strtok(NULL, " \t\n");
			lenA++;								// 多项式项数加 1
		}

		// 以下将字符串 b 放置到多项式 b 中，操作类似上面的步骤
		tmp = strtok(strB, " \t\n");
		while(tmp){
			sscanf(tmp, "%d", &b[lenB].coef);
			tmp = strtok(NULL, " \t\n");
			sscanf(tmp, "%d", &b[lenB].expn);
			tmp = strtok(NULL, " \t\n");
			lenB++;
		}

		// 下面是进行多项式的加法，算法类同有序序列的有序合并
		i = j = 0;								// 注意这里每次循环时值要赋为0，否则下次循环就值就会有问题
		while(i<lenA && j<lenB){
			if(a[i].expn > b[j].expn){			// 如果 a 的某一项比 b 的某一项指数高，则结果应加入 a 这一项
				r[lenR].coef = a[i].coef;
				r[lenR].expn = a[i].expn;
				i++;
				lenR++;
			}else if(a[i].expn < b[j].expn){	// 如果 a 的某一项比 b 的某一项指数低，则结果应加入 b 这一项
				r[lenR].coef = b[j].coef;
				r[lenR].expn = b[j].expn;
				j++;
				lenR++;
			}else if(a[i].expn == b[j].expn){	// 如果 a 的某一项和 b 的某一项指数相等，
				if(a[i].coef + b[j].coef){		// 如果两项的系数和不为 0，则结果加上它们的和，否则就忽略
					r[lenR].coef = a[i].coef + b[j].coef;
					r[lenR].expn = a[i].expn;
					lenR++;
				}
				i++;
				j++;
			}
		}

		// 结果加入多项式 a 中剩下的部分
		while(i < lenA){
			r[lenR].coef = a[i].coef;
			r[lenR].expn = a[i].expn;
			i++;
			lenR++;
		}
		// 结果加入多项式 b 中剩下的部分
		while(j < lenB){
			r[lenR].coef = b[j].coef;
			r[lenR].expn = b[j].expn;
			j++;
			lenR++;
		}

		// 显示多项式的结果
		for(int i=0;i<lenR;i++){
			printf("%d %d ", r[i].coef, r[i].expn);
		}
		// 换行
		putchar('\n');
	}

	return 0;
}

Java解答

import java.util.*;
class D {
	int a,e;
	D(int i,int j) {a=i;e=j;}
};
public class Main 
{
	public static void main(String[] args)
	{
		Scanner cin = new Scanner(System.in);
		int a,e;
		String t;
		D tD;
		List<D> L=new LinkedList<D>();
		while(cin.hasNext())
		{
			t=cin.nextLine();
			Scanner str=new Scanner(t);
			while(str.hasNext())
			{
				a=str.nextInt();
				e=str.nextInt();
				L.add(new D(a,e));
			}
			t=cin.nextLine();
			str.close();
			str=new Scanner(t);
			while(str.hasNext())
			{
				boolean f=true;
				a=str.nextInt();
				e=str.nextInt();
				ListIterator<D> p=L.listIterator();
				while(p.hasNext())
				{
					tD=p.next();
					if(e>tD.e)
					{
						p.previous();
						p.add(new D(a,e));
						f=false;
						break;
					}
					else if(e==tD.e)
					{
						if(a+tD.a==0)
							p.remove();
						else
							p.set(new D(a+tD.a,e));
						f=false;
						break;
					}
				}
				if(f)
				{
					p.add(new D(a,e));
				}
			}
			ListIterator<D> p=L.listIterator();
			while(p.hasNext())
			{
				tD=p.next();
				System.out.print(tD.a+" "+tD.e+" ");
			}
			L.clear();
			System.out.println();
			str.close();
		}
		cin.close();
	}
}
请先登陆