1002 A+B for Polynomials (25 分) 多项式相加我的解法+别人的解法

我不是女神ヾ 2024-02-19 20:47 54阅读 0赞

1002 A+B for 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 sum 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 to 1 decimal place.

#### 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

多项式相加：一般会想到用链表，我第一次用链表，只得了15分，不知道为什么？后来看了一位博主的代码，他居然用数组，再看看大小64M,好像可以。试了下。真的过了

数组：

#include<stdio.h>
    #define range 1005
    int main()
    {
    	double cnt[range]={0};
    	int i,j,n,m;
    	double r;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		scanf("%d %lf",&j,&r);
    		cnt[j]=r;
    	}
    	scanf("%d",&m);
    	for(i=0;i<m;i++)
    	{
    		scanf("%d %lf",&j,&r);
    		cnt[j]+=r;
    	}
    	m=0;
    	for(i=0;i<1001;i++)
    	{
    		if(cnt[i]!=0)
    		m++;
    	}
    	printf("%d",m);
    	for(i=1001;i>=0;i--)
    	{
    		if(cnt[i]!=0)
    		printf(" %d %.1lf",i,cnt[i]);
    	}
    	return 0;
    }

链表：（只得了15分）

#include<iostream>
    #include<cstdio>
    using namespace std;
    #define NULL 0
     
    typedef struct node{
    	int index;  //指数 
    	double ratio;   // 系数 
    	struct node* next;
    }node,* List;
     
    void CreateList(List &l)
    {
    	l=new node;
    	l->next=NULL;
    }
    void add(int z,double x,List &l)  //采用头插法 
    {
    	List n=new node;
    	n->index=z;
    	n->ratio=x;
    	n->next=l->next;
    	l->next=n;
    }
    int input(List &l)       // 输入 
    {
    	int m=0,a=0;
    	double b;
    	int i=0,j=0;
    	cin>>m;
    	for(i=0;i<m;i++)
    	{
    		scanf("%d %lf",&a,&b);
    		add(a,b,l);
    	}
    	return 1;
     } 
     int compute_length(List l)   //计算链表的长度 
    {
    	int i=0;
    	l=l->next;
    	while(l)
    	{
    		i++;
    		l=l->next;
    	}
    	return i;
    }
    int collect(List a,List b,List &c)  // 合并链表 
    {
    	List Pa=a->next;
    	List Pb=b->next;
    	List Pc=c;
    	while((Pa)&&(Pb))
    	{
    		if((Pa->index)<(Pb->index))
    		{
    			
    			Pc->next=Pa;
    			
    			Pc=Pa;
    			
    			Pa=Pa->next;
    		}
    		else
    		if((Pa->index)==(Pb->index))
    		{
    			
    			Pa->ratio=Pa->ratio+Pb->ratio;
    			
    			Pc->next=Pa;
    		    
    			Pc=Pa;
    			Pa=Pa->next;
    			Pb=Pb->next;
    			
    		}
    		else
    		if((Pa->index)>(Pb->index))
    		{
    			
    			Pc->next=Pb;
    			
    			Pc=Pb;
    			Pb=Pb->next;	
    		}
    	}
    	if(Pa!=NULL)
    	Pc->next=Pa;
    	if(Pb!=NULL)
    	Pc->next=Pb;
    
    	delete Pa,Pb,Pc;
    	return 1;
    }
    void Traversal(List l)   //  遍历链表 
    {
    	int len=compute_length(l);
    	printf("%d ",len);
    	l=l->next;   //跳过头结点 
    	while(l)
    	{
    	    if(l->ratio!=0) 
    		printf("%d %.1lf",l->index,l->ratio);
    		if(l->next!=NULL)
    		printf(" ");
    		
    		l=l->next;
    	}
    	cout<<endl;
    }
    int  mysort(List *l)            //  因为链表是用头插法 ，所以需要排序 
    {
    	node *p,*q;
    	double t_ratio;
    	int t_index;
    	for(p=(*l)->next;p!=NULL;p=p->next)
    	{
    		for(q=p->next;q!=NULL;q=q->next)
    		{
    			if(p->index<q->index)
    			{
    				t_ratio=q->ratio;
    				t_index=q->index;
    				q->ratio=p->ratio;
    				q->index=p->index;
    				p->ratio=t_ratio;
    				p->index=t_index;
    			}
    		}
    	}
    	return 0;
    }
    
    int main()
    {
    	List a,b,c;
    
    	CreateList(a);
    	CreateList(b);
    	CreateList(c);
    	input(a);
    	input(b);
    //	Traversal(a);
    //	Traversal(b);
    	collect(a,b,c);
    	mysort(&c);
    	Traversal(c);
    
    	return 0;
    }

### 别人的代码： ###

#include<cstdio>
    #include<map>
    using namespace::std;
    map<int,double> s;
    int main()
    {
    	int i1,t1;
    	double t2;
    	for(int z=0;z<2;z++)
    	{
    		scanf("%d",&i1);
    		for(int i=0;i<i1;i++)
    		{
    			scanf("%d%lf",&t1,&t2);
    			if(s.count(t1)==0)
    				s[t1]=t2;
    			else
    				s[t1]+=t2;
    		}
    	}
    	i1=0;
    	for(map<int,double>::const_iterator m_it=s.begin();m_it!=s.end();m_it++)
    	{
    		if(m_it->second!=0.0&&m_it->second!=-0.0)
    			i1++;
    	}
    	printf("%d",i1);
    	for(map<int,double>::reverse_iterator m_it=s.rbegin();m_it!=s.rend();m_it++)
    	{
    		if(m_it->second!=0.0&&m_it->second!=-0.0)
    			printf(" %d %.1lf",m_it->first,m_it->second);
    	}
    	printf("\n");
    	return 0;
    }

巧用map，灵活运用STL