求高精度幂

in 知识共享 with 0 comment

acm的题目,要求计算高精度幂,即一个数的n次幂。 代码中的大数用STL中的string表示

#include <string>
#include <stdio.h>
// 求两个大数相乘的结果 ( left, right 表示的数这里均为正整数 )
std::string mul( std::string left, std::string right )
{
    std::string sRet = "";
    std::string sCurr = "";
    short src = 0;
    short dst = 0;
    short ret = 0;
 
    // 余数
    short remainder1 = 0;
    // 商
    short quotient1 = 0;
 
    int counter = 0;
    for (int i = left.size()-1; i >= 0; i--)
    {
        src = left[i] - '0';
        short lastQuotient = 0;
        short remainder = 0;
        sCurr = "";
        for (int j = right.size()-1; j >= 0; j--)
        {
            dst = right[j] - '0';
            ret = src * dst;
            remainder = ret % 10;
 
            remainder1 = (remainder + lastQuotient) % 10;
            quotient1 = (remainder + lastQuotient) / 10;
 
            sCurr.insert( sCurr.begin(), '0' + remainder1 );
            lastQuotient = ret / 10 + quotient1;
 
            if ( j == 0 && lastQuotient > 0 )
            {
                if ( lastQuotient / 10 )
                {
                    sCurr.insert( sCurr.begin(), '0' + lastQuotient%10 );
                    sCurr.insert( sCurr.begin(), '0' + lastQuotient/10 );
                }
                else
                {
                    sCurr.insert( sCurr.begin(), '0' + lastQuotient );
                }
            }
        }
 
        int tmp = counter;
        while( tmp-- )
            sCurr.push_back( '0' );
 
        int ndiff = sCurr.size() - sRet.size();
        for( int m = 0; m < ndiff; m++ )
            sRet.insert( sRet.begin(), '0' );
 
        lastQuotient = 0;
        remainder = 0;
        for (int n = sRet.size()-1; n >= 0; n--)
        {
            src = sRet[n] - '0';
            dst = sCurr[n] - '0';
 
            ret = src + dst;
            remainder = ret % 10;
 
            remainder1 = (remainder + lastQuotient) % 10;
            quotient1 = (remainder + lastQuotient) / 10;
 
            sRet[n] = '0' + remainder1;
            lastQuotient = ret / 10 + quotient1;
 
            if ( n == 0 && lastQuotient > 0 )
            {
                if ( lastQuotient / 10 )
                {
                    sRet.insert( sRet.begin(), '0' + lastQuotient%10 );
                    sRet.insert( sRet.begin(), '0' + lastQuotient/10 );
                }
                else
                {
                    sRet.insert( sRet.begin(), '0' + lastQuotient );
                }    
            }
        }
 
        counter++;
    }
 
    return sRet;
}
// 计算大数sinput的exp次幂 (sinput表示的数和exp均大于等于0)
std::string caclExpo( std::string sinput, int exp )
{
    // 0次幂返回1
    if ( exp == 0 )
        return "1";
    
    // 移除小数点便于计算
    std::string sOutput = sinput;
    int ndot = 0;
    for ( int i = sinput.size()-1; i >= 0; i-- )
    {
        if ( sinput[i] == '.' )
        {
            ndot = sinput.size()-1-i;
            sinput.erase( i, 1 );
            break;
        }
    }
    sOutput = sinput;
 
    int nTotalDot = ndot;
    while( --exp )
    {
        // 顺便计算下结果中小数点后的位数
        nTotalDot += ndot;
        // 乘吧
        sOutput = mul( sOutput, sinput );
    }
 
    // 把小数点放到正确的位置上
    if ( nTotalDot != 0 )
        sOutput.insert( sOutput.begin() + sOutput.size()-nTotalDot, '.' );
 
    // 移除整数部分无效的0
    if ( sOutput.size() > 1 )
    {
        for (int i = 0; i < sOutput.size(); i++)
        {
            if ( sOutput[i] == '0' )
            {
                sOutput.erase( i, 1 );
                i--;
            }
            else
                break;
        }
    }
 
    // 移除小数部分无效的0
    if ( nTotalDot != 0 )
    {
        for (int i = sOutput.size()-1; i >= 0 ; i--)
        {
            if ( sOutput[i] == '0' )
            {
                sOutput.erase( i, 1 );
            }
            else
                break;
        }
    }
 
    return sOutput;
}
测试: 测试数据来自ACM
/* 测试数据
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
*/
// 测试
void Test( std::string src, int exp, std::string expected )
{
    std::string sret = caclExpo( src, exp );
    if ( sret.compare( expected ) != 0 )
        printf( "test not passed, [the result is (%s)\n, but (%s) is expected\n", sret.data(), expected.data() );
    else
        printf( "test passed\n" );
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    Test( "95.123", 12, "548815620517731830194541.899025343415715973535967221869852721"  );
    Test( "0.4321", 20, ".00000005148554641076956121994511276767154838481760200726351203835429763013462401"  );
    Test( "5.1234", 15, "43992025569.928573701266488041146654993318703707511666295476720493953024"  );
    Test( "6.7592", 9, "29448126.764121021618164430206909037173276672"  );
    Test( "98.999", 10, "90429072743629540498.107596019456651774561044010001"  );
    Test( "1.0100", 12, "1.126825030131969720661201"  );
 
    return 0;
}

测试结果:
test.jpeg

Responses