北大 POJ 关于高精度幂的问题
我的程序能够正确输出结果，可是测试反馈“Output Limit Exceeded”。到底哪里出了问题？请大牛指点！/*
Name: 求高精度幂
Copyright:
Author: 巧若拙
Date: 31/10/14 12:42
Description: 求高精度幂
Time Limit: 500MS Memory Limit: 10000K
Total Submissions: 137841 Accepted: 33704
Description
对数值很大、精度很高的数进行高精度计算是一类十分常见的问题。比如，对国债进行计算就是属于这类问题。
现在要你解决的问题是：对一个实数R( 0.0 < R < 99.999 )，要求写程序精确计算 R 的 n 次方(Rn)，其中n 是整数并且 0 < n <= 25。
Input
T输入包括多组 R 和 n。 R 的值占第 1 到第 6 列，n 的值占第 8 和第 9 列。
Output
对于每组输入，要求输出一行，该行包含精确的 R 的 n 次方。输出需要去掉前导的 0 后不要的 0 。如果输出是整数，不要输出小数点。
Sample Input
95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
Sample Output
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201
Source
East Central North America 1988
Translator
北京大学程序设计实习，Xie Di
*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 2000
typedef struct Node{
int val[MAX];//存储数字
int len, fra;//分别表示数字个数和小数部分长度
} Node;
Node CreatNode(char str[]);
Node Pow(Node A, int n);
Node Mul(Node A, Node B);
void PrintNode(Node A);
int main(void)
{
char str[MAX];
Node A, B;
int n;
while (scanf("%s%d", str, &n) != 0)
{
// printf("s= %s, n = %d\n", str, n);
A = CreatNode(str);
B = Pow(A, n);
PrintNode(B);
}
return 0;
}
Node CreatNode(char str[])
{
int i, n, f;
Node A;
i = n = f = 0;
while (str[i] != '.' && str[i] != '\0')//获取整数部分
{
A.val[n++] = str[i++] - '0';
}
if (str[i] == '.')
{
i++;
while (str[i] != '\0')//获取小数部分
{
f++;
A.val[n++] = str[i++] - '0';
}
}
A.len = n;
A.fra = f;
if (A.fra > 0)//消除小数部分多余的后缀0
{
while (A.val[A.len-1] == 0)
{
A.fra--;
A.len--;
}
}
return A;
}
Node Pow(Node A, int n)
{
Node B, C;
if (n == 1)
return A;
if (n == 0)
{
C.val[0] = C.len = 1;
C.fra = 0;
return C;
}
B = Pow(A, n/2);
C = Mul(B, B);
if (n % 2 == 1)
C = Mul(C, A);
return C;
}
Node Mul(Node A, Node B)
{
Node C;
int M[MAX] = {0};
int i, j, k, d, s;
for (d=1,i=A.len-1; i>=0; i--)
{
k = MAX - d;
d++;
for (j=B.len-1; j>=0; j--)
{
s = A.val[i] * B.val[j] + M[k]; //直接在M[k]中取进位
M[k] = s % 10;
M[--k] += s / 10; //把进位存储到M[k-1]
}
while (M[k] >= 10) //分解多位数
{
s = M[k];
M[k] = s % 10;
M[--k] = s / 10;
}
}
while (M[k] == 0)//去除多余的前缀0
k++;
for (i=0; k<MAX; i++)//复制数字到C
C.val[i] = M[k++];
C.len = i;
C.fra = A.fra + B.fra;
if (C.fra > 0)//消除小数部分多余的后缀0
{
while (C.val[C.len-1] == 0)
{
C.fra--;
C.len--;
}
}
return C;
}
void PrintNode(Node A)
{
int z = A.len - A.fra;
int i;
for (i=0; i<z; i++)
printf("%d", A.val[i]);
if (z < A.len)
{
printf(".");
for ( ; i<A.len; i++)
printf("%d", A.val[i]);
}
printf("\n");
}
