Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

AC finally,时间很奇怪,第一次0ms,第二次16ms

Posted by absolute at 2009-03-24 19:56:05 on Problem 1001
#include <string>
#include <memory.h>
using namespace std;
void computeExp();
void ComputePowResult(char* a,int b,char*);
#define MAX 200
#define BASEBITS 6
int main()
{
	computeExp();
	return 0;
}
void computeExp()
{
	char base[BASEBITS];
	int power;
	memset(base,0,sizeof(base));
	while(scanf("%s%d",base,&power)==2)
	{
		if(power==0)
		{
			printf("1\n");
		}
		else
		{
			char result[MAX];
			ComputePowResult(base,power,result);
		}
	}
}
void ComputePowResult(char* base,int power,char *result)
{
	string mytemp(base);
	int dotPos = mytemp.find('.');
	int i,j;
	//如果有小数点
	if(dotPos!=-1)
	{
		i = mytemp.length()-1;
		for(;i>0;i--)
		{
			//取出低位尾部0
			if(mytemp[i]=='0')
			{
				mytemp.erase(i,1);
			}
			else
			{
				break;
			}
		}
		//remove the dot
		if(mytemp[i]=='.')
		{
			mytemp.erase(i,1);
			//没有小数
			dotPos = 0;
		}
		else
		{
			mytemp.erase(dotPos,1);
			dotPos = i-dotPos;
		}
	}
	else
	{
		dotPos = 0;
	}
	int strLen = mytemp.length();
	for(i=0;i<strLen;++i)
	{
		//去除高位前导0
		if(mytemp[i]=='0')
		{
			mytemp.erase(i,1);
			--i;
		}
		else
		{
			break;
		}
	}
	//base==0
	if(mytemp=="")
	{
		printf("0\n");
		return;
	}
	char tempmul[MAX];
	memset(result,0,MAX);
	memset(tempmul,0,sizeof(tempmul));
	//反转,是数字从低位到高位排列,100->001,最后结果也是如此排列
	for(i=mytemp.length()-1,j=0;i>=0;i--)
	{
		base[j] = result[j]=mytemp[i]-'0';
		j++;
	}
	//转换后的幂底的总位数
	int bits = mytemp.length();
	//记录第i次乘法后的结果的位数
	int totalbits = bits;
	for(i=0;i<power-1;i++)
	{
		//第i次乘法
		memset(tempmul,0,sizeof(tempmul));
		//幂底(即每次乘法的乘数)的位数
		int kbit;
		for(kbit=0;kbit<bits;++kbit)
		{
			//乘数的每位都要乘以被乘数的所有位,然后将结果对应相加
			j=0;
			while(j<totalbits)
			{
				int mul = base[kbit]*result[j]+tempmul[j+kbit];
				tempmul[j+kbit+1] += mul/10;
				tempmul[j+kbit]=mul%10;
				j++;
			}
		}
		//此次乘法结果位数
		totalbits=totalbits+bits;
		memcpy(result,tempmul,totalbits);
		//判断是否有进位,没有则总位数减1
		if(result[totalbits-1]==0)
			totalbits --;
	}
	//统计低位的0,由于计算前已经将前后0去除,因此高位不会再有0
	int low=0;
	//00000lowXXXX
	for(low=0;low<totalbits;low++)
	{
		if(result[low]!=0)
		{
			break;
		}
	}
	int high=totalbits-1;
	dotPos = dotPos*power-1;
	//输出整数,没有整数则不会输出
	for(i=high;i>dotPos;i--)
	{	printf("%d",result[i]);
	}
	//判断是否有小数,输出小数点
	if(dotPos>=low)
	{
		printf(".");
	}
	//输出小数,没有则不会输出
	for(i=dotPos;i>=low;i--)
	{
		printf("%d",result[i]);
	}

	printf("\n");
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator