/*考虑大数乘法和大数乘幂.
大数乘法我没有优化,达到了0(n^2)
大数乘幂优化了一下，x^n= x*(x^2)*(x^4)*....  ()内的为临时计算项
另外需要注意底数为0和整数的时候，没有考虑负数。 指数也不考虑0和负数。*/
/*cacluate R^n accurately*/
#include <stdio.h>

#define MAX_DIGITS	180

int NumOut[MAX_DIGITS];
int NumIn1[MAX_DIGITS];
int NumIn2[MAX_DIGITS];

int StringToDecimal(char *pStr,int *pNum,int *pLength);
int LargeIntegerMultiply(int *pNum1,int len1,int *pNum2,int len2,int *pNumOut);
int LargeIntegerPow(int *pNumIn,int lenIn,int exp,int *pNumOut);

int main(void)
{
	char string[6];
	int exponent,length,decimalbits,beginprint;
	int i,j;

	while(scanf("%s %d",string,&exponent)!=EOF){
		//convert the string to integer
		decimalbits = StringToDecimal(string,NumIn1,&length);
		//process 0
		if((length==1) &&(NumIn1[0]==0)){
			printf("0\r\n");			
			continue;
		}

		length=LargeIntegerPow(NumIn1,length,exponent,NumOut);			
		decimalbits *= exponent;
		
		//output the interger part
		i=length-1;
		if(length>decimalbits){
			beginprint=0;
			while(i>=decimalbits){
				if((NumOut[i]!=0)||(beginprint==1)){	//omit the prefix 0s
					beginprint=1;
					printf("%d",NumOut[i]);
				}
				--i;		
			}
		}
		//output the decimal part
		if(decimalbits!=0){
			printf(".");
			//we need to remove the trailing 0s
			//find trailing 0's num
			j=0;
			while(NumOut[j]==0){
				++j;
			}	
			while(i>=j){
				printf("%d",NumOut[i]);
				--i;
			}
		}
		printf("\r\n");
	}
	return 0;
}

int StringToDecimal(char *pStr,int *pNum,int *pLength)
{
	int decimalbits,beginexp,isZero,isInteger;
	int k,tmp;
	int bits=0;

	beginexp = 0;
	decimalbits = 0;
	while(*pStr){
		if(*pStr=='.'){
			beginexp=1;	
		}else{
			pNum[bits]=*pStr-'0';	//convert to digit
			++bits;
			if(beginexp){
				++decimalbits;
			}
		}
		++pStr;
	}
	
	//reverse the num bits order
	k=0;	
	while(k<(bits>>1)){
		tmp = pNum[k];
		pNum[k]=pNum[bits-1-k];
		pNum[bits-1-k]=tmp;
		++k;
	}
	
	//check whether the decimal part is needed???
	isZero=1;
	isInteger=1;
	for(k=0;k<decimalbits;++k){
		if(pNum[k]!=0){
			isInteger=0;
			isZero=0;
			break;
		}
	}
	if(isInteger==1){
		for(k=decimalbits;k<bits;++k){
			if(pNum[k]!=0){
				isZero=0;
				break;
			}
		}
	}

	if(isZero==1){
		*pLength=1;	//only one value 0
		pNum[0]=0;
		decimalbits=0;	//no decimal part
	}else if(isInteger==1){
		*pLength=bits-decimalbits;
		for(k=decimalbits;k<bits;++k){
			pNum[k-decimalbits]=pNum[k];
		}
		decimalbits=0;
	}else{
		*pLength=bits;
	}
	return decimalbits;
}

int LargeIntegerMultiply(int *pNum1,int len1,int *pNum2,int len2,int *pNumOut)
{
	int i,j;
	for(i=0;i<len1+len2;++i){	//clear the output num
		pNumOut[i]=0;
	}
	for(i=0;i<len1;++i){
		for(j=0;j<len2;++j){
			pNumOut[i+j] += pNum1[i]*pNum2[j];
		}
	}
	for(i=0;i<len1+len2-1;++i){
		if(pNumOut[i]>=10){
			pNumOut[i+1] += pNumOut[i]/10;
			pNumOut[i] %= 10;
		}
	}
	if(pNumOut[len1+len2-1]!=0)
		return len1+len2;
	else
		return len1+len2-1;
}

//Notice: all the numbers should be non-negative
int LargeIntegerPow(int *pNumIn,int lenIn,int exp,int *pNumOut)
{
	int i,j;
	int lenOut;
	int *pNumIn2 = NumIn2;

	lenOut=1;
	pNumOut[0]=1;
	while(exp!=0){
		if(exp & 0x01){
			lenOut=LargeIntegerMultiply(pNumOut,lenOut,pNumIn,lenIn,pNumIn2);
			for(i=0;i<lenOut;++i){
				pNumOut[i]=pNumIn2[i];
			}
		}
		if(exp!=1){
			lenIn=LargeIntegerMultiply(pNumIn,lenIn,pNumIn,lenIn,pNumIn2);
			for(i=0;i<lenIn;++i){
				pNumIn[i]=pNumIn2[i];
			}
		}
		exp >>=1;
	}
	return lenOut;
}

• Congratulations! (3939) yygy 2013-10-31 14:44:00