求高精度幂

朴灿烈づ我的快乐病毒、 2022-05-14 10:59 155阅读 0赞

周末闲着没事看了下acm的题目，要求计算高精度幂，即一个数的n次幂。 代码中的大数用STL中的string表示

本文所实现的方法效率不一定达到acm的要求(没有进行性能测试)，但是测试结果的确通过了，下面贴代码，欢迎大家拍砖。。。

源代码：

#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][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;
    }

测试结果：

![1354355052_1914.jpg][]

[ACM]: http://poj.org/problem?id=1001
[1354355052_1914.jpg]: https://img-my.csdn.net/uploads/201212/01/1354355052_1914.jpg