1001.cpp

北大ACM题库中的部分已AC题目源码（1001

#include<iostream>
using namespace std;

typedef struct node
{
	int n;
	struct node *lnext;
	struct node *rnext;
}Node,*List;

int main()
{
	float R;
	int i,j,n;
	char chR[10];
	int decimal;
	List resultList;
	List dataList;
	Node * p;
	Node* resultnode;
	Node* datanode;
	Node* p1;
	List tempList;
	int flag=0;
	int m=0;
	int t=0;
	int num=0;
	int num1;
	int num2;



	//读数据
	while(cin>>R>>n)
	{
		flag=0;
		//把R转换成字符串
		memset(chR,'\0',sizeof(chR));
		sprintf(chR,"%f",R);
		chR[6]='\0';
	
		for(i=1;i<6;i++)
		{
			if(chR[i]=='.')
				break;
		}
		decimal=5-i;
		resultList=new Node;
		resultnode=resultList;
		dataList=new Node;
		datanode=dataList;

		resultList->n=0;

		for(i=0;i<6;i++)
		{
			if((flag==0)&&((chR[i]=='0')||(chR[i]=='.')))
				continue;
			flag=1;
			if(chR[i]=='.')
				continue;
			p=new Node;
			p->rnext=resultList;
			resultnode->rnext=p;
			p->lnext=resultnode;
			resultnode=p;
			p->n=chR[i]-48;
			resultList->lnext=p;

			p=new Node;
			p->rnext=dataList;
			datanode->rnext=p;
			p->lnext=datanode;
			datanode=p;
			p->n=chR[i]-48;
			dataList->lnext=p;
		}

		for(i=0;i<n-1;i++)
		{	
			tempList=new Node;
			tempList->n=0;
			tempList->rnext=tempList;
			tempList->lnext=tempList;
			p=tempList;
			num=0;

			datanode=dataList->lnext;
			while(datanode!=dataList)
			{
				resultnode=resultList->lnext;
				num++;
				t=0;
				while(resultnode!=resultList)
				{
					m=(resultnode->n)*(datanode->n);			//数据位相乘
					if(p!=tempList)
					{
						if(m+t>=10)
						{
							p->n=p->n+(m+t)%10;
							t=(m+t)/10;

						}
						else
						{
							p->n=p->n+m+t;
							t=0;
						}
						if(p->n>=10)
						{
							p->lnext->n=p->lnext->n+((p->n)/10);
							p->n=(p->n)%10;
						}
					}
					else
					{
						p=new Node;
						p->rnext=tempList->rnext;
						tempList->rnext->lnext=p;
						tempList->rnext=p;
						p->lnext=tempList;
						if(m+t>=10)
						{
							p->n=p->lnext->n+(m+t)%10;
							t=(m+t)/10;
						}
						else
						{
							p->n=(p->lnext->n)+m+t;
							t=0;
						}
						if(p->n>=10)
						{
							p->lnext->n=(p->n)/10;
							p->n=(p->n)%10;
						}
						else
						{
							p->lnext->n=0;
						}

					}
					p=p->lnext;	
					resultnode=resultnode->lnext;
				}
				m=t+(p->n);
				if(m!=0)
				{
					p=new Node;
					p->rnext=tempList->rnext;
					tempList->rnext->lnext=p;
					tempList->rnext=p;
					p->lnext=tempList;
					p->n=m;

					if(m>=10)
					{
						p->n=m%10;
						t=m/10;
						p=new Node;
						p->rnext=tempList->rnext;
						tempList->rnext->lnext=p;
						tempList->rnext=p;
						p->lnext=tempList;
						p->n=t;						
					}
				}
				//输入中间结果，测试用
			/*	p=tempList->rnext;
				while(p!=tempList)
				{
					cout<<p->n<<" ";
					p=p->rnext;
				}
				cout<<endl;*/

				tempList->n=0;
				t=0;
				p=tempList->lnext;
				for(j=0;j<num;j++)
				{
					p=p->lnext;
				}
				datanode=datanode->lnext;
			}
			//释放掉不必要的内存
			p=resultList->rnext;
			while(p!=resultList)
			{
				p1=p->rnext;
				delete(p);
				p=p1;

			}
			delete(p);
			//重新指定结果链表；
			resultList=tempList;
			
		}
	//打印结果
		num=0;
		flag=0;
		p=resultList->lnext;
		while(p!=resultList)
		{
			num++;
			if((p->n!=0)&&(flag==0))
			{
				p1=p;
				flag=1;
				num1=num;
			}

			p=p->lnext;
		}
		num2=0;
		flag=0;
		if(num>decimal*n)
		{
			p=resultList->rnext;
			while(p!=resultList)
			{
				num2++;
				cout<<p->n;
				if(num2==num-decimal*n)
				{
					if(num2+num1>=num)
						break;
					else
					{
						cout<<".";
						flag=1;
					}
				}
				if((flag==1)&&p==p1)
					break;
				p=p->rnext;
			}
		}
		else if(num==decimal*n)
		{
			cout<<".";
			p=resultList->rnext;
			while(p!=resultList)
			{
				cout<<p->n;
				if(p==p1)
					break;
				p=p->rnext;
			}
		}
		else 
		{
			cout<<'.';
			for(i=0;i<decimal*n-num;i++)
			cout<<'0';
			p=resultList->rnext;
			while(p!=resultList)
			{
				cout<<p->n;
				if(p==p1)
					break;
				p=p->rnext;
			}
		}
		cout<<endl;
	}
}