北大 1001（Exponentiation）
小弟最近学习ACM，做了北大的1001题，使用的算法就是将结果放在一个整型数组里，数组的每个单元存储5位长的大于0的整数，每次都将R于整型数组的各个单元相乘，然后放在一个中间数组里，经过长度和进位的调整之后再放回整型数组，然后逐次计算，以达到求幂的效果，但是不过我咋样优化，就是超时啊，看网上有朋友也是同样算法就过了啊，很纠结，小弟用的C语言，直接上代码了，谢谢各位大虾！知道有种二分求幂的算法，但必须用那种么？
#include "stdio.h"
#include "math.h"
main()
{
int result[32];
double mid[32];
int intInd;
int fraInd;
int n, i, j;
double input;
double max = 1;
for(i=0; i<10; i++)
max *= 10;
while(scanf("%lf%d", &input, &n))
{
double tmp1, tmp2;
int add;
intInd = 11;
fraInd = 12;
for(i=0; i<32; i++)
mid[i] = 0.0;
mid[intInd] = floor(input);
result[intInd] = round(mid[intInd]);
mid[fraInd] = (input-result[intInd]) * max;
result[fraInd] = round(mid[fraInd]);
for(j=1; j<n; j++)
{
for(i=intInd; i<=fraInd; i++)
mid[i] = result[i] * input;
add = 0;
i = fraInd;
if((mid[fraInd]-floor(mid[fraInd])) > 0)
fraInd++;
for(i; i>=intInd; i--)
{
mid[i] += add;
add = 0;
tmp1 = floor(mid[i]);
tmp2 = mid[i] - tmp1;
if(tmp2 > 0)
{
add = round(tmp2 * max);
mid[i] = tmp1;
mid[i+1] += add;
add = 0;
if(mid[i+1] >= max)
{
mid[i+1] -= max;
mid[i] += 1;
}
result[i+1] = round(mid[i+1]);
}
if(mid[i] >= max)
{
tmp1 = floor(mid[i]/max);
mid[i] -= tmp1 * max;
add = round(tmp1);
}
result[i] = round(mid[i]);
}
if(add > 0)
result[--intInd] = add;
}
if(intInd != 11 || result[11] != 0)
{
printf("%d", result[intInd]);
for(i=intInd+1; i<=11; i++)
printf("%05d", result[i]);
}
if(fraInd != 12 || result[12] != '0')
{
printf("%c", '.');
for(i=12; i<fraInd; i++)
printf("%05d", result[i]);
while(result[i]-(result[i]/10)*10 == 0)
result[i] /= 10;
printf("%d", result[i]);
}
printf("%c", '\n');
}
}
int round(double x)
{
double tmp = x - floor(x);
if(tmp > 0.5)
x += 1;
return (int)x;
}
[解决办法]
这题我做的时候就写了个大数乘法，乘的时候需要个大数加法，小数点先去掉，根据位数和幂能算出结果中小数的位数，最后去掉开头和结尾的0，没任何优化就过了，lz还是看看自己算法有没有问题吧~~
