1001 poj Exponentiation(高精度乘法)

Memory: 160K

Time: 0MS

解题思路

题意：

给出一个实数R和一个整数n，求R的n次方。输出时去掉前导0和后面没用的0。

思路：

   这是高精度问题，用数组存储这些大数。

输入时用字符串，同时记下小数点的位置mark。Newmark=len-mark ，是底数的小数位数。字符串转化成整数放在另一个整型数组里面mnew[]，同时是按着逆序存放的。然后是循环n-1次求大数乘积，结果倒着放在mnew[]里面。每循环一次，Newmark更新为自己的两倍。最后的值是结果的小数位数。

   然后把从前往后找到mnew中第一个不是0的数的位置formark，从最后一个数到第formark个输出结果，如果前面是0的话不要输出，如果是第newmark-1 个就输小数点。

   最后看formark-1 是不是大于newmark，是的话输出newmark-formark个0。

求大数相乘的方法是： 逐位相乘，把结果加到对应位，最后处理进位。

假设A=a1a2a3…an;  B=b1b2b3…bn;  C(i+j) += ai * bj;

 即：

 

然后处理C中大于10的数。

源程序

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 300
int mnew[N], inew[5];

/*大数相乘*/
int multiply(int lenm, int leni)
{
    int i, j, k;
    int c[N];

    memset(c, 0, sizeof(c));
    for(i=0; i<lenm; i++)
    {
        for(j=0; j<leni; j++)
        {
            c[i+j] += mnew[i] * inew[j]; //逐位相乘，结果加到对应位

        }
    }
    k = lenm + leni - 1;
    
    //处理进位

    for(i=0; i<k; i++)
    {
        if(c[i] >= 10)
        {
            c[i+1] += c[i] / 10;
            c[i] = c[i] % 10;
        }
        mnew[i] = c[i];
    }
    mnew[i] = c[i];
    if(c[k] != 0)
        k++;

    return k;
}

int main()
{
    int i, j;
    int n, len, mark,leni, lenm, newmark,formark, t, ok;
    char r[N];

    freopen("in.txt", "r", stdin);
    while(scanf("%s", r) != EOF)
    {
        scanf("%d", &n);
        len = (int)strlen(r);
        mark = 0;
        for(i=len-1, j=0; i>=0; i--)
        {
            if(r[i] == '.')
            {
                if(i == len-1)
                    mnew[j] = inew[j++] = r[i] - '0';
                mark = i;
            }
            else
            {
                mnew[j] = inew[j++] = r[i] - '0';
            }
        }
        len--;
        mark = len - mark;
        lenm = len;
        newmark = mark;
        for(i=1; i<n; i++)
        {
            lenm = multiply(lenm, len);
            newmark = newmark + mark;
        }
        formark = i = 0;
        for(; i<lenm; i++)
        {
            if(mnew[i] != 0)
                break;
        }
        formark = i;
        ok = 0;
        for(i=lenm-1; i>=formark; i--)
        {
            if(mnew[i] == 0 && i >= newmark && !ok)
                continue;
            if(i == newmark-1)
                printf(".");
            printf("%d", mnew[i]);
            ok = 1;
        }
        for(formark--; formark >= newmark; formark--)
            printf("0");
        
        printf("\n");
    }
    getch();
    return 0;
}