POJ - 1001 Exponentiation(浮点数高精度乘法)

布满荆棘的人生 2022-06-02 02:05 235阅读 0赞

今天信息学院的一个老师跟我讨论这个题，很遗憾我不会用Java的bigInteger类，只能手动用数组来模拟这个题了。

[点我看题][Link 1]

题意：求r^n,其中0<r<99.99,0<n<=25.可以肯定的是，long double都存不下99.99^25，所以高精度了，这个题带有小数，那么我们首先要想起小学乘法里面的小数相乘问题，两个小数相乘，最后得到的结果中小数点位数等于乘数与被乘数的小数点位数之和。那这个题我们可以先记录下底数的小数点位数，然后将小数化为整数，最后就变成了整数相乘的高精度问题了，假设我们用数组a来保存乘数，数组b来保存被乘数(ab的高位保存的数的高位,所有下标从1开始)，数组ans来存答案，那么我们根据所列的竖式可得:ans\[i+j-1\]+=a\[i\]\*b\[j\]+add(add为进位)，add=ans\[i+j-1\]/10,a\[i+j-1\]%=10；然后搞一搞答案就出来了。

参考代码：

#include<cstdio>
    #include<cmath>
    #include<cctype>
    #include<cstdlib>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<stack>
    #include<queue>
    #include<map>
    #include<set>
    #include<list>
    #include<vector>
    #include<iostream>
    
    using namespace std;
    char s[10];//底数
    int r[10];//用整型数组来保存底数,且去掉小数点
    int n;//指数
    int tmp[1000];//临时变量，存储中间计算过程
    int ans[1000];//用于保存最终结果
    int point;//表示小数点位数
    
    /*两个浮点数相乘，最终得到的浮点数的小数点位数是可以确定的，也就是乘数与被乘数小数点位数之和*/
    int main()
    {
        while( ~scanf("%s%d",s,&n))
        {
            //将输入的底数用整型数组来保存，且去掉小数点然后倒序，如12.34就存为4321，同时求出小数点位数
            int lens = strlen(s);
            int lenr = 1;
            bool flag = false;
            point = 0;
            for( int i = lens-1; i >= 0; i--)
            {
                if( s[i] != '.')
                    r[lenr++] = s[i]-'0';
                else
                    flag = true;
                //用于求小数点位数
                if( flag)
                {
                    point = lens-i-1;
                    flag = false;
                }
            }
            lenr--;
    
            //高精度乘法
            int lena = 1;
            memset(tmp,0,sizeof(tmp));
            memset(ans,0,sizeof(ans));
            tmp[1] = 1;
            for( int cnt = 0; cnt < n; cnt++)
            {
                for( int i = 1; i <= lena; i++)
                {
                    int add = 0;
                    for( int j = 1; j <= lenr; j++)
                    {
                        ans[i+j-1] += tmp[i]*r[j]+add;
                        add = ans[i+j-1]/10;
                        ans[i+j-1] %= 10;
                    }
                    ans[i+lenr] = add;
                }
    
                lena += lenr;//计算答案的长度
                while( ans[lena] == 0 && lena > 1)//删除前导0
                    lena--;
                if( cnt != n-1)
                    for( int i = 1; i <= lena; i++)
                        tmp[i] = ans[i], ans[i] = 0;
            }
    
    
            //对结果的输出格式进行处理
            point *= n;//r^n共有point位小数
            if( lena <= point)//结果为纯小数
            {
                printf(".");
                for( int i = 1; i <= point-lena; i++)
                    printf("0");
                int p = 0;
                while( ans[p] == 0 && p <= lena)//删除多余的0
                    p++;
                for( int i = lena; i >= p; i--)
                    printf("%d",ans[i]);
                puts("");
            }
            else//结果不为小数
            {
                int i;
                for( i = lena; i > point; i--)//输出整数部分
                    printf("%d",ans[i]);
                int p = 0;
                while( ans[p] == 0 && p <= i)//删除后面多余的0
                    p++;
                if( i >= p)
                    printf(".");
                for( ; i >= p; i--)
                    printf("%d",ans[i]);
                puts("");
            }
        }
    
        return 0;
    }

[Link 1]: http://poj.org/problem?id=1001