作者：林子木

大体思路就是

用递归的方法求幂的次数

其中乘法，使用大数乘法的原理，不拘泥本题的六位的输入

其中整型字符串 和 字符串转整型 采用自己写的函数，如果使用系统自带的，速率会跟高些。

AC的时间是16MS 内存是232K

这里的主要问题是有块内存不能释放在，在注释的

//free(s2);

//free(s1); 这里的内存指向是最后的char *Int2Str(int *n,int len)中产生的内存

char *MyPow(char *s,int n)

{

char *s1,*s2,*res;

if(n == 1)

{

return Mutli(s,"1");

}

else if(n == 2)

{

return Mutli(s,s);

}

else if(n > 2)

{

s1 = MyPow(s,n>>1);

if(n%2 != 0)

{

s2 = MyPow(s,n-(n>>1));

res = Mutli(s1,s2);

//free(s2);

}

else

{

res = Mutli(s1,s1);

}

//free(s1);

return res;

}

}

代码如下：

#include

#include

#include

#include

#define LENGTH 6

char *MyPow(char *s,int n);

char *Mutli(char *s1,char *s2);

int *Str2Int(char *s,int lenArr);

char *Int2Str(int *n,int len);

int main()

{

char realNumString[LENGTH];

int n;

int piontLocation;//标记小数位后有几位

char *numPointer;

while(scanf("%s %d",realNumString,&n) != EOF)

{

int len,lenRes;

int i,j;

char tmp[LENGTH];

char *res;

piontLocation = 0;

//处理后面的无用的零

len = strlen(realNumString);

numPointer = realNumString + len - 1;

while(*numPointer == '0')

{

*numPointer = '\0';

numPointer--;

}

//处理前面无用的零

numPointer = realNumString + strspn(realNumString, "0");//只有使用指针才能如此操作

len = strlen(numPointer);

j = 0;

for( i=0; i

{

if( *(numPointer + i) == '.')

piontLocation = len - i - 1;

else

tmp[j++] = *(numPointer + i);

}

tmp[j] = '\0';//末尾加上

strcpy(realNumString,tmp+strspn(tmp, "0"));//再次去除前面没用的零

res = MyPow(realNumString,n);

len = strlen(realNumString);

//如果是整数

if (piontLocation == 0)

{

printf("%s\n",res);

}

//如果只有小数没整数

else if (len <= piontLocation)

{

lenRes = strlen(res);

i = piontLocation*n - lenRes;

if (i == 0)

{

printf(".%s\n",res);

}

else

{

printf(".");

while (i--)

{

printf("0");

}

printf("%s\n",res);

}

}

//其他

else

{

lenRes = strlen(res);

for( i=0; i

{

if(i == lenRes-piontLocation*n)

printf(".");

printf("%c",res[i]);

}

printf("\n");

}

}

}

char *MyPow(char *s,int n)

{

char *s1,*s2,*res;

if(n == 1)

{

return Mutli(s,"1");

}

else if(n == 2)

{

return Mutli(s,s);

}

else if(n > 2)

{

s1 = MyPow(s,n>>1);

if(n%2 != 0)

{

s2 = MyPow(s,n-(n>>1));

res = Mutli(s1,s2);

//free(s2);

}

else

{

res = Mutli(s1,s1);

}

//free(s1);

return res;

}

}

char *Mutli(char *s1,char *s2)

{

int len1,len2;

int lenArr1,lenArr2,lenTotal;

int *n1,*n2,*nRes;

char *res;

int i,j;

int carry;

len1 = strlen(s1);

len2 = strlen(s2);

res = (char *)malloc((len1 + len2 + 1)*sizeof(char));

//判断s2是否为1

if (strncmp(s2, "1", 1) == 0 && len2 == 1)

{

strcpy(res,s1);

return res;

}

lenArr1 = (len1%4==0) ? (len1/4) : (len1/4+1);

lenArr2 = (len2%4==0) ? (len2/4) : (len2/4+1);

lenTotal = lenArr1 + lenArr2;

nRes= (int *)malloc(lenTotal*sizeof(int));

memset(nRes,0,sizeof(int)*(lenTotal));//初始化

n1 = Str2Int(s1,lenArr1);

n2 = Str2Int(s2,lenArr2);

//计算相乘

for( i=lenArr1-1; i>=0; i--)

{

for( j=lenArr2-1; j>=0;j--)

{

nRes[i+j+1] += n1[i] * n2[j] ; //注意要+1 本位

nRes[i+j] += nRes[i+j+1] / 10000;

nRes[i+j+1] %= 10000;

}

}

free(n1);

free(n2);

free (res);//现在res指的内存是这此次mutli创出来的，下面的res指向的是另外的地址

res = Int2Str(nRes,lenTotal);

free(nRes);

return res;

}

int *Str2Int(char *s,int lenArr)

{

int *res;

int i,j;

int lenStr;

res = (int *)malloc(lenArr*sizeof(int));//分配空间

memset(res,0,lenArr*sizeof(int));//初始化

j = lenArr;

lenStr = strlen(s);

for( i=lenStr-1; i>=0; i--)

{

if((lenStr-i-1)%4 != 0) //lenStr-i 从最后开始数

{

res[j] += (int)(s[i]-'0') * pow(10.0,(lenStr-i-1)%4);//lenStr-i-1 第一位是n的0次幂

}

else

{

res[--j] += s[i]-'0';

}

}

return res;

}

char *Int2Str(int *n,int len)

{

//这里我是使用10000进制每个数组单位里有四个字符

int i,j;

char *res;

res = (char *)malloc((len*4+1)*sizeof(char));

memset(res,'0',len*4*sizeof(char));

res[len*4] = '\0';//最后加上'\0'

for( i=0; i

for( j=0; j<4; j++)

{

n[i] %= (int)pow(10.0,4-j);

res[i*4+j] = n[i]/pow(10.0,3-j) + '0';

}

res = res + strspn(res,"0");

return res;

}