ACM题目：求高精度幂C++解法

92 阅读 0 评论 61 点赞

我是靠谱客的博主谦让黑夜，最近开发中收集的这篇文章主要介绍ACM题目：求高精度幂C++解法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

求高精度幂

Time Limit: 500MS		Memory Limit: 10000K
Total Submissions: 87719		Accepted: 20833

Description

对数值很大、精度很高的数进行高精度计算是一类十分常见的问题。比如，对国债进行计算就是属于这类问题。

现在要你解决的问题是：对一个实数R( 0.0 < R < 99.999 )，要求写程序精确计算 R 的 n 次方(R ⁿ)，其中n 是整数并且 0 < n <= 25。

Input

T输入包括多组 R 和 n。 R 的值占第 1 到第 6 列，n 的值占第 8 和第 9 列。

Output

对于每组输入，要求输出一行，该行包含精确的 R 的 n 次方。输出需要去掉前导的 0 后不要的 0 。如果输出是整数，不要输出小数点。

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

准备找实习了，于是狂刷算法题，在网上找到这个题目，也看了下别人的解法，结果再次证明看别人代码是件痛苦的事情，自己动手，丰衣足食。测试结果良好，在酷睿T9300上运行没有超过500MS

/*
*高精度幂
*
bolg:	http://blog.csdn.net/xidomlove
*
mail:	fufulove2012@gmail.com ganyoufu@hotmail.com
*/
#include<iostream>
#include<string>
#include<deque>
using namespace std;
//vout=vout+v2;
void count_add(deque<int>& vout,deque<int>& v2)
{
int overflow=0;
int tmp;
deque<int> v1=vout;
vout.clear();
deque<int>::reverse_iterator iter1=v1.rbegin();
deque<int>::reverse_iterator iter2=v2.rbegin();
if(v1.size()>v2.size())
{
for(;iter2!=v2.rend();++iter2,++iter1)
{
tmp=*iter1+(*iter2)+overflow;
vout.push_front(tmp%10);
overflow=tmp/10;
}
for(;iter1!=v1.rend();++iter1)
{
tmp=(*iter1)+overflow;
vout.push_front(tmp%10);
overflow=tmp/10;
}
}
else
{
for(;iter1!=v1.rend();++iter2,++iter1)
{
tmp=(*iter1)+(*iter2)+overflow;
vout.push_front(tmp%10);
overflow=tmp/10;
}
for(;iter2!=v2.rend();++iter2)
{
tmp=(*iter2)+overflow;
vout.push_front(tmp%10);
overflow=tmp/10;
}
}
if(overflow)
{
vout.push_front(1);
}
}
void count_multi(deque<int> &v,deque<int> &vout,int factor)
{
int tmp=0;
int overflow=0;
deque<int>::reverse_iterator iter=v.rbegin();
for(;iter!=v.rend();++iter)
{
tmp=*iter*factor+overflow;
vout.push_front(tmp%10);
overflow=tmp/10;
}
if(overflow)
{
vout.push_front(overflow);
}
}
int get_count(deque<int> &v)
{
int count=0;
deque<int>::iterator iter=v.begin();
for(;iter!=v.end();++iter)
{
count*=10;
count+=*iter;
}
return count;
}
//高精度浮点数类
class BigDouble
{
public:
BigDouble():dot_pos(0){};
BigDouble(string &num);
~BigDouble();
friend ostream& operator<<(ostream& out,BigDouble& bd)
{
int pos=bd.integers.size();
if(bd.dot_pos>pos)
{
cout<<".";
while(pos++!=bd.dot_pos)cout<<"0";
pos=-1;
}
deque<int>::iterator iter=bd.integers.begin();
for(;iter!=bd.integers.end();++iter)
{
if(pos--==bd.dot_pos)
{
out<<".";
}
out<<*iter;
}
return out;
}
BigDouble operator*(BigDouble&);
private:
//双向队列，方便插入数字
deque<int> integers;
//小数点位置
int dot_pos;
//去掉无效0
void RemoveZero();
};
BigDouble::BigDouble(string &num):dot_pos(0)
{
//for(int i=0;i<num.length();i++)
//{
//	if(num[i]!='0')
//	{
//
break;
//	}
//	num.erase(0,1);
//}
//for(int i=num.length()-1;i>=0;i--)
//{
//	if(num[i]!='0')
//	{
//
break;
//	}
//	num.erase(i,1);
//}
for(int i=0;i<num.length();i++)
{
if(num[i]=='.')
{
dot_pos=num.length()-i-1;
continue;
}
integers.push_back((int)num[i]-48);
}
RemoveZero();
}
BigDouble::~BigDouble()
{
}
void BigDouble::RemoveZero()
{
//去掉后面的无效0
deque<int>::iterator i;
if(dot_pos>0)
{
i=integers.end()-1;
for(;i!=integers.begin();--i)
{
if(*i!=0||dot_pos==0)break;
dot_pos-=1;
}
integers.erase(i+1,integers.end());
}
//去掉前面的无效0
i=integers.begin();
for(;i!=integers.end();++i)
{
if(*i!=0)break;
}
integers.erase(integers.begin(),i);
}
#include<algorithm>
BigDouble BigDouble::operator*(BigDouble& bd)
{
BigDouble ret;
deque<int>* integers_mult_up=NULL;
deque<int>* integers_mult_down=NULL;
deque<int> tmp;
//int pos=0;
if(integers.size()<=bd.integers.size())
{
integers_mult_up=ℤ
integers_mult_down=&bd.integers;
}
else
{
integers_mult_up=&bd.integers;
integers_mult_down=ℤ
}
deque<int>::reverse_iterator iter=(*integers_mult_up).rbegin();
deque<int>::reverse_iterator iter2;
for(;iter!=(*integers_mult_up).rend();++iter)
{
tmp.clear();
count_multi(*integers_mult_down,tmp,*iter);
for(iter2=(*integers_mult_up).rbegin();iter2!=iter;++iter2)
{
tmp.push_back(0);
}
count_add(ret.integers,tmp);
}
ret.dot_pos=dot_pos+bd.dot_pos;
ret.RemoveZero();
return ret;
}
int main()
{
string num_str;
int pow;
while (cin>>num_str>>pow)
{
BigDouble bd(num_str);
//cout<<bd;
BigDouble bd2=bd;
for(int i=1;i<pow;i++)
{
bd2=bd2*bd;
}
cout<<bd2<<endl;
}
return 0;
}