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;
}
测试结果:
本文由 BeijingJW 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Jun 2, 2023 at 03:35 pm