POJ 1001:Exponentiation —— 高精度浮点数运算

总时间限制: 500ms 内存限制: 65536kB
描述
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.

This problem requires that you write a program to compute the exact value of Rnwhere R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.

输入
The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.

输出
The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don't print the decimal point if the result is an integer.

样例输入
95.123 12
0.4321 20
5.1234 15
6.7592  9
98.999 10
1.0100 12

样例输出
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201

自己的代码：超时
思路：先将浮点数转化成整数，然后做整数大整数乘法，最后处理小数点

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

string r;
int n;

string multiply(string mynum1, string mynum2)
{
    //i 和 j 相乘的结果是 res 的 (i+j) 位
    int it1 = 0, it2 = 0;
    //预处理，去掉前导 0
    while(mynum1[it1] == '0')
        it1++;
    while(mynum2[it2] == '0')
        it2++;

    string num1 = "", num2 = "";
    while(it1 != mynum1.length())
        num1 += mynum1[it1++];
    while(it2 != mynum2.length())
        num2 += mynum2[it2++];

    string str_res = "";
    int first = 0;
    int res[320] = {};
    int len1 = num1.length(), len2 = num2.length();
    if(len1 < len2)
        return multiply(num2, num1);
    int a[160] = {};
    int b[160] = {};

    for(int i=0;i<len1;i++)
        a[i] = num1[len1-i-1]-'0';
    for(int i=0;i<len2;i++)
        b[i] = num2[len2-i-1]-'0';

    for(int i=0;i<len1;i++)
    {
        for(int j=0;j<len2;j++)
        {
            res[i+j] += a[i]*b[j];
        }
    }

    for(int i=0;i<len1+len2+2;i++)
    {
        if(res[i] >= 10)
        {
            res[i+1] += res[i]/10;
            res[i] %= 10;
        }
    }

    for(int i=315;i>=0;i--)
        if(res[i] != 0)
        {
            first = i; break;
        }
    for(int i=first;i>=0;i--)
    {
        str_res += res[i]+'0';
    }

    return str_res;
}

string multi(string a,string b)     //浮点数乘法
{
    int PointA = 0, PointB = 0;
    int flag_zero = 0;
    string NewA = "", NewB = "";
    string res = "";        //存放最后结果
    int lena = a.length(), lenb = b.length();

    if(a[0]=='0' || b[0]=='0')
        flag_zero = 1;

    for(int i=0;i<lena;i++)
    {
        if(a[i] == '.')
        {
            PointA = i; break;
        }
    }
    for(int i=0;i<lenb;i++)
    {
        if(b[i] == '.')
        {
            PointB = i; break;
        }
    }
    //转换成两个大整数的乘法
    for(int i=0;i<lena;i++)
        if(i != PointA)
            NewA += a[i];
    for(int i=0;i<lenb;i++)
        if(i != PointB)
            NewB += b[i];

    string tmp_res = multiply(NewA, NewB);
    int it = tmp_res.length()-1;
    int ZeroNum = 0;

    //计算结果中后缀 0 的数目
    while(tmp_res[it] == '0')
    {
        ZeroNum++; it--;
    }
    int add_zero_num = 0;
    int ttt = lena+lenb-PointA-PointB-2-ZeroNum;
    while(ttt > 0)
    {
        ttt--;
        if(it >= 0)
            res += tmp_res[it--];
        else        //需要添加零
        {
            ttt++;
            break;
        }

    }
    //补 0
    while(ttt--)
        res += '0';
    //添加小数点
    res += '.';
    if(flag_zero)
        res += '0';
    else
    {
        while(it >= 0)
        {
            res += tmp_res[it--];
        }
    }

    //翻转结果
    reverse(res.begin(), res.end());

    return res;
}

string cal(string r,int n)     //calculate r^n，二分法
{
    if(n == 1)
        return r;
    else
    {
        if(n%2 == 0)
            return multi(cal(r,n/2),cal(r,n/2));
        else
            return multi(r,cal(cal(r,n/2),2));
    }
}

int main()
{
    while(cin>>r>>n)
    {
        cout<<cal(r,n)<<endl;
    }
    return 0;
}

1 ms AC代码：在处理大整数乘法时用数学思想做了优化。

#include <stdio.h>
#include <string.h>

int len; // total length of exponentiation result
int product[126] = {0}; // storing result, at most length 5*25 + 1 = 126

void multiply(int a[], int n)
{
    int i;
    int carry = 0; // a carry number in multiplying
    for (i = 0; i < len; i++)
    {
        int temp = a[i]*n + carry;
        a[i] = temp % 10;
        carry = temp / 10;      
    }
    while (carry)
    {
        a[i++] = carry % 10;
        carry /= 10;
    }
    len = i;
}

int main(int argc, char* argv[])
{
    int n;  // power n
    char s[6]; // real number R, at most the length is 6
    while (scanf("%s %d", s, &n) != EOF)
    {
        int position=0, i=0, num=0, j=0;
        for (i=0; i<strlen(s); i++) 
        {
            if (s[i] == '.')
            {
                position = (strlen(s) - 1 - i) * n; // calculate decimal point position after R^n
            }
            else
            {
                num = num*10 + s[i] - 48; // 将浮点数转化成整数
            }       
        }

        // product calculation 
        product[0]=1;
        len = 1;
        // 获得幂
        for (i = 0; i < n; i++)
        {
            multiply(product, num);
        }

        // format output
        if (len <= position) // product is less than 1
        {
            printf("."); // print decimal point
            for (i=0; i<position-len; i++)
            {
                printf("0"); // print zero between decimal point and decimal
            }

            j = 0;
            //while (product[j] == 0) // trim trailing zeros
            //{
            //    j++;
            //}
            for (i=len-1; i>=j; i--)
            {
                printf("%d", product[i]);
            }
        }   
        else
        {
            j=0;
            while (product[j]==0 && j<position) // trim trailing zeros
            {
                j++;
            }
            for (i=len-1; i>=j; i--)
            {
                if (i+1 == position) // cause index in C language starts from 0
                {
                    printf(".");
                }
                printf("%d", product[i]);
            }
        }
        printf("\n");
    }
}