问题：对一个实数R( 0.0 < R < 99.999 )，要求写程序精确计算 R 的 n 次方(Rn)，其中n 是整数并且 0 < n <= 25。

计算结果位数的确定

  • 两数之和的最大为较大的数的位数加1
  • 乘积的位数最大为两个因子的位数之和
  • 阶乘：lgn! = lgn + lg(n-1) + … + lg1 = lnn/ln10 + ln(n-1)/ln10 + … + ln1/ln10 = trunc(1/ln10 * (lnn + ln(n-1) + … + ln1))
  • 乘方：lg(a^b) = trunc(lg(a^b)) + 1 = trunc(b * lga) + 1 = trunc(b * lna/ln10) + 1

高精度加法

1
2
3
4
5
6
7
8

ncarry = 0;
for (i = 0; i <= len; i++)
{
    k = a[i] + b[i] + ncarry;
    a[i+1] += k/N;
    ncarry = k%N;
}
//当最后 ncarry > 0 时，len会变化

高精度减法

1
2
3
4
5
6
7
8
9

//先比较大小，大的为a
ncarry = 0;
for (i = 0; i <= len; i++)
{
    if (a[i] - b[i] - ncarry) >= 0)
        a[i] = a[i] - b[i] - ncarry, ncarry = 0;
    else
        a[i] = a[i] + N - b[i] - ncarry, ncarry = 1;
}

高精度乘法

1
2
3
4
5
6
7
8

for (i = 0; i <= lena; i++)
    for (j = 0; j <= lenb; j++)
        c[i+j] += a[i] * b[j];
for (i = 0; i <= lena + lenb; i++)
{
    c[i+1] += c[i]/N;
    c[i] = c[i]/N;
}

代码

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

/*
POJ-1001
提交状态：
Accepted    244K 0MS   C++    2039B
解题思路：
1、首先要保证两个整数的乘法运算是正确的
2、接受数据之后，先去掉小数点，并且根据幂指数确定小数点的位数，此时要注意的是如果出现1.0000这样有无效零的情况，先将0去掉。
3、多次调用高精度乘法函数得到整数结果
4、补上小数点并输出，因为在2中已经去掉了无效零，于是结果中便不会出现小数点右边末尾出现零的情况。
5、还有就是如果小数点的总位数大于等于结果的长度，应该先输出"."
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 1000

void process(char s[], int *point);
void reverse(char t[], int n);
void check( int tmp[], int n, char result[]);
void mul(char s[], char t[], char result[]);
void show(int point, char result[]);


int main(int argc, char *argv[])
{
    char s[SIZE];
    int n;

    while (scanf("%s%d", s, &n) != EOF) {
        int i, point = 0;
        process(s, &point);
        char result[SIZE * 2];
        char tmp[SIZE];
        strcpy(result, s);
        strcpy(tmp, s);
        for (i = 0; i < n - 1; i++) {
            strcpy(s, tmp);
            mul(s, result, result);
        }
        show(point * n, result);
    }
    return 0;
}


void process(char s[], int *point)
{
    int len = strlen(s);
    int i = 0;
    while (s[i] != '\0')
    {
        if (s[i] == '.') break;
        ++i;
    }

    while (s[len - 1] == '0') --len;
    s[len] = '\0';
    *point = i < len ? (len - i - 1) : 0;
    while (i < len) {
        s[i] = s[i + 1];
        ++i;
    }
}

void reverse(char t[], int n)
{
    int i = 0, j = n - 1;
    char tmp;
    while (i < j)
    {
        tmp = t[i];
        t[i] = t[j];
        t[j] = tmp;
        ++i, --j;
    }
}

void check(int tmp[], int n, char result[])
{
    int i, j, k = 0;
    for (i = 0; i < n; ++i)
    {
        tmp[i + 1] += tmp[i] / 10;
        tmp[i] = tmp[i] % 10;
    }
    while (tmp[i] == 0) --i;
    for (j = i; j >= 0; j--)
        result[k++] = tmp[j] + '0';
    result[k] = 0;
}

void mul(char s[], char t[], char result[])
{
    int ls = strlen(s);
    int lt = strlen(t);
    reverse(s, ls);
    reverse(t, lt);
    int tmp[SIZE * 2] = {0};
    int i, j, k;
    int a = 0;
    for (i = 0; i < ls; i++)
        for (j = 0; j < lt; j++)
            tmp [i + j] += (int)(s[i] - '0')*(int)(t[j] - '0');
    check(tmp, i + j, result);
}

void show(int point, char result[])
{
    int len = strlen(result);
    if (point >= len)
        printf(".");
    while (point > len)
    {
        printf("0");
        point--;
    }
    for (int i = 0; i < len; i++)
    {
        printf("%c", result[i]);
        if (i == len - 1 - point && point != 0)
            printf(".");
    }
    printf("\n");
}