Question

北大ACM1001 exponentiation 用C语言怎么写呢？对高精度数应该怎么处理？

Description

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

现在要你解决的问题是：对一个实数R( 0.0 < R < 99.999 )，要求写程序精确计算 R 的 n 次方(Rn)，其中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

Answer 1

昨天刚做的这个题，现在把大概思路和代码（c++）给你吧
这个题很明显不能直接乘，因为没有那个类型能到达如此之精度，因为有好多次方吗，于是我把每次相乘的结果结果保存在int r[151]数组里面，数组中每个元素保存结果中的一位，如例子中最后一组1.01 的12次方的结果为1.126825030131969720661201，那么最后，r中元素为：r[1]=1、r[2]=1、r[3]=2、r[4]=6........

计算时乘数忽略了小数点和无效0，如1.0100计算时使用101，而r初始值为乘数即，r[1]=1,r[2]=0、r[3]=1；然后与乘数101相乘12-1=11次，每次相乘都是r中每个元素与乘数相乘，相乘后r中每个元素不在是保存一位数，于是需要进位，使r中元素仍只有一位数。这样计算的话，r数组中每个元素都不会超出精度，因为每次相乘都是一位数和乘数相乘。由于忽略了小数点，所以计算前需要确定是否有小数点，如果有的话小数点后有几位有效数字也要确定，然后就可以得出计算完成后小数点后有几位有效数字，输出就能将小数点加进去了。
这就是大概过程 代码如下：

#include <stdio.h>
#include <iostream>
#include <string>

using namespace std;

int main()
{
string mlp; //乘数
int power; //乘数的幂
int r[151]; //保存结果
int hdot;
while(cin>>mlp>>power)
{
hdot=0;
for(int t=0;t<150;t++)
{
r[t]=-1;
}
if(mlp.find(".")!=string::npos)
hdot=mlp.length()-mlp.find(".")-1;
string::iterator itr=mlp.end()-1;
while(hdot>0&&itr>=mlp.begin())
{
if(*itr!='0')
{break;}
hdot--;
itr--;
}
int cn=0;
while(itr>=mlp.begin())
{
if(*itr!='.')
{
r[cn]=*itr-'0';
cn++;
}
itr--;
}
int k=cn-1;
int m=0; //保存临时数；
while(k>-1)
{
m=m*10+r[k];
k--;
}
for(int i=1;i<power;i++)
{
int j=0;
while(r[j]>-1)
{
r[j]=r[j]*m;
j++;
}
j=0;
while(r[j]>-1)
{
if(r[j+1]==-1&&r[j]>=10)
r[j+1]=r[j]/10;
else
r[j+1]+=r[j]/10;
r[j]=r[j]%10;
j++;
}
}
hdot=hdot*power;
int cnt=0;
while(r[cnt]>-1)
{
cnt++;
}
if(hdot>=cnt)
{
cout<<".";
while(hdot>cnt)
{
cout<<"0";
hdot--;
}
hdot=0;
}
for(k=cnt-1;k>=0;k--)
{
if((k+1)==hdot&&hdot!=0)
cout<<".";
cout<<r[k];
}
cout<<endl;
}
return 0;
}

Answer 2

给你个我的程序，注释应该还算详尽，希望对你有帮助

#include <iostream>
#include <algorithm>
#include<cstdlib>
#include<string>
#include<cstring>
using namespace std;
inline int max(int a,int b){
return a>b?a:b;
}
class LONG{
public:
static const int size=1000,base=10;
int len,num[size];//len存储位长，num[i]存储第i位的值
bool flag;//true=+,false=-
friend int cmp(LONG &a,LONG &b);//必须加friend，否则编译器以为cmp为内部函数
LONG(){len=1;flag=true; memset(num,0,sizeof(num));}
inline LONG(long x){//整数转为base进制的LONG
if(x<0){
flag=false;
x=0-x;
}
else flag=true;
memset(num,0,sizeof(num));
for(len=0; x>0; len++){
num[len]=x%base;
x/=base;
}
if(len==0) len=1;
}
inline bool iszero(){
return len==1&&num[0]==0;
}
inline LONG(char *s){//以char类表示的数值转换为 LONG类；注意基都是base,
//并且s必须以'\0'结尾，因为要用到strlen（）函数
memset(num,0,sizeof(num));
int i;
len=strlen(s);
for(i=0; i<len; i++)
num[i]=s[len-i-1]-'0';
while(len>0&&num[len-1]==0) len--;
if(len==0)len++;
if(len>1&&(s[0]=='-'||s[0]=='+')){
len--;
num[len]=0;
}
if(s[0]=='-')
flag=false;
else flag=true;
}
inline LONG(string s){//以char类表示的数值转换为 LONG类；注意基都是base,
//并且s必须以'\0'结尾，因为要用到strlen（）函数
memset(num,0,sizeof(num));
int i;
len=s.length();
for(i=0; i<len; i++)
num[i]=s[len-i-1]-'0';
while(len>0&&num[len-1]==0) len--;
if(len==0)len++;
if(len>1&&(s[0]=='-'||s[0]=='+')){
len--;
num[len]=0;
}
if(s[0]=='-')
flag=false;
else flag=true;
}
inline void print(int k=0){//输出
int i;
if(k!=0&&flag)
printf("+");
if(!flag)
printf("-");
printf("%d",num[len-1]);
for(i=len-2; i>=0; i--) printf("%d",num[i]);
}

inline LONG operator+(LONG &b){
LONG operator-(LONG &b);
if((flag^b.flag)==true){
if(b.flag==false){
LONG c(b);
c.flag=true;
c=*this-c;
return c;
}
else {
LONG c(*this);
c.flag=true;
c=b-c;
return c;
}
}
LONG c;
int i,t;
if(len>b.len) c.len=len; else c.len=b.len;
for(i=t=0; i<c.len; i++){
t+=num[i]+b.num[i];
c.num[i]=t%base;
t/=base;
}
if(t>0){c.num[c.len]=t; c.len++;}
c.flag=flag;
return c;
}
inline LONG operator-(LONG &b){
if(b.iszero())
return *this;
if(this->iszero()){
LONG c=b;
c.flag=1^b.flag;
return c;
}
if((flag^b.flag)==true){
if(b.flag==false){
LONG c(b);
c.flag=true;
return c+*this;
}
else {
LONG c(b);
c.flag=false;
return c+*this;
}
}
LONG c;
int i,t;
int key=cmp(*this,b);
if(key==0)
return LONG(long(0));
c.len=max(len,b.len);
if(key<0){
c.flag=false;
if(b.flag==false){
for(i=t=0; i<c.len; i++){
t=num[i]-b.num[i]-t;
if(t>=0) c.num[i]=t,t=0;
else c.num[i]=t+base,t=1;
}
}
else{
for(i=t=0; i<c.len; i++){
t=b.num[i]-num[i]-t;
if(t>=0) c.num[i]=t,t=0;
else c.num[i]=t+base,t=1;
}
}
}
else {
c.flag=true;
if(flag==false){
for(i=t=0; i<c.len; i++){
t=b.num[i]-num[i]-t;
if(t>=0) c.num[i]=t,t=0;
else c.num[i]=t+base,t=1;
}
}
else{
for(i=t=0; i<c.len; i++){
t=num[i]-b.num[i]-t;
if(t>=0) c.num[i]=t,t=0;
else c.num[i]=t+base,t=1;
}
}
}
while(c.len>1&&c.num[c.len-1]==0)
c.len--;
return c;
}
inline LONG operator*(LONG &b){
LONG c;
int i,j,t;
if(iszero()||b.iszero())
return LONG(long(0));
c.flag=1^(flag^b.flag);
for(i=0; i<b.len; i++)
for(j=t=0; j<len||t!=0; j++){
t+=b.num[i]*num[j]+c.num[i+j];
c.num[i+j]=t%base;
t/=base;
}
for(c.len=len+b.len; c.len>1&&c.num[c.len-1]==0; c.len--);
return c;
}
void chx(){//规格化
while(len>1&&num[len-1]==0)
len--;
}
inline LONG operator/(LONG &b){ //pku2539
LONG r=*this,c;
int i,j,t,q;
b.chx();
if(b.iszero())
exit(-1) ;
if(this->iszero())
return LONG(long(0));
c.flag=1^(flag^b.flag);
for(i=len-b.len; i>=0; i--){
if(b.len==1) q=(r.num[i+1]*base+r.num[i])/b.num[0]; else{
j=i+b.len;
q=r.num[j]*base*base+r.num[j-1]*base+r.num[j-2];
q/=b.num[b.len-1]*base+b.num[b.len-2];
}
for(j=t=0; j<=b.len; j++){
t+=r.num[i+j]-b.num[j]*q;
if(t>=0) r.num[i+j]=t%base,t=0;
else if(t%base==0) r.num[i+j]=0,t/=base;
else r.num[i+j]=t%base+base,t=t/base-1;
}
if(t<0){
q--;
for(j=t=0; j<=b.len; j++){
t+=r.num[i+j]+b.num[j];
r.num[i+j]=t%base;
t/=base;
}
}
c.num[i]=q;
}
for(; r.len>1&&r.num[r.len-1]==0; r.len--);
for(c.len=len-b.len+1; c.len>1&&c.num[c.len-1]==0; c.len--);
if(c.iszero())
return LONG(long(0));
return c;//这里改成return r即为取模运算
}
inline LONG operator%(LONG &b){ //pku2539
if(iszero())
return LONG(long(0));
b.chx();
if(b.iszero()||flag==false||b.flag==false)
exit(-1);
LONG r=*this,c;
int i,j,t,q;
for(i=len-b.len; i>=0; i--){
if(b.len==1) q=(r.num[i+1]*base+r.num[i])/b.num[0]; else{
j=i+b.len;
q=r.num[j]*base*base+r.num[j-1]*base+r.num[j-2];
q/=b.num[b.len-1]*base+b.num[b.len-2];
}
for(j=t=0; j<=b.len; j++){
t+=r.num[i+j]-b.num[j]*q;
if(t>=0) r.num[i+j]=t%base,t=0;
else if(t%base==0) r.num[i+j]=0,t/=base;
else r.num[i+j]=t%base+base,t=t/base-1;
}
if(t<0){
q--;
for(j=t=0; j<=b.len; j++){
t+=r.num[i+j]+b.num[j];
r.num[i+j]=t%base;
t/=base;
}
}
c.num[i]=q;
}
for(; r.len>1&&r.num[r.len-1]==0; r.len--);
for(c.len=len-b.len+1; c.len>1&&c.num[c.len-1]==0; c.len--);
r.flag=true;
return r;
}
void right_move(int n=1){
//void left_move(int n=1);//这句一定不能要，否则编译器以为left_move是外函数
if(n==0)return;
if(n<0){
left_move(0-n);
return;
}
for(int i=n;i<=len;i++)
num[i-n]=num[i];
len-=n;
}
void left_move(int n=1){
if(n==0)return;
if(n<0){
right_move(0-n);
return;
}
for(int i=len;i>=0;i--)
num[i+n]=num[i];
for(int i=0;i<n;i++)
num[i]=0;
len+=n;
}
};
inline int cmp(LONG &a,LONG &b){
if((a.flag^b.flag)==true){
if(a.flag==true)
return 1;
return -1;
}
if(a.flag==true){
if(b.len>a.len)
return -1;
if(b.len<a.len)
return 1;
for(int i=a.len-1;i>=0;i--){
if(b.num[i]>a.num[i])
return -1;
if(b.num[i]<a.num[i])
return 1;
}
}
if(a.flag==false){
if(b.len>a.len)
return 1;
if(b.len<a.len)
return -1;
for(int i=a.len-1;i>=0;i--){
if(b.num[i]>a.num[i])
return 1;
if(b.num[i]<a.num[i])
return -1;
}
}
return 0;
}
class FLOAT{
protected:
static const int precision=36;//精度控制
int pos;//小数点位置
LONG Float;
public:
friend int cmp(FLOAT &a ,FLOAT &b);
friend void chx(FLOAT &a,FLOAT &b);
bool iszero(){
FLOAT c(*this);
for(int i=0,j=c.Float.len;i<j;i++){
if(c.Float.num[0]==0)
c.right_move();
else return false;
}
return true;
}
FLOAT(long a){
Float=LONG(a);
pos=-1;
}
FLOAT(){
FLOAT(long(0));
}
FLOAT(string a){
string b(a);
pos=b.find('.');
if(pos!=-1)
b.erase(b.begin()+pos);
Float=LONG(b);
if(pos!=-1)
pos=b.size()-pos-1;
if(Float.len<pos)
Float.len=pos+1;
for(int i=0,j=Float.len;;i++){//去除末尾多余的0
if(Float.num[i]!=0||i>pos){
right_move(i);
j-=i;
Float.len=j;
pos-=i;
break;
}
}
}
FLOAT(char * a){
string b(a);
pos=b.find('.');
if(pos!=-1)
b.erase(b.begin()+pos);
Float=LONG(b);
if(pos!=-1)
pos=b.size()-pos-1;
if(Float.len<pos)
Float.len=pos+1;
for(int i=0,j=Float.len;;i++){//去除末尾多余的0
if(Float.num[i]!=0||i>pos){
right_move(i);
j-=i;
Float.len=j;
pos-=i;
break;
}
}
}
FLOAT(double a){
char s[40];
sprintf(s,"%lf\0",a);
string b(s);
pos=b.find('.');
if(pos!=-1)
b.erase(b.begin()+pos);
Float=LONG(b);
if(pos!=-1)
pos=b.size()-pos-1;
if(Float.len<pos)
Float.len=pos+1;
for(int i=0,j=Float.len;;i++){//去除末尾多余的0
if(Float.num[i]!=0||i>pos){
right_move(i);
j-=i;
Float.len=j;
pos-=i;
break;
}
}
}
void left_move(int n=1){
if(n==0)
return ;
if(n<0){
right_move(0-n);
return ;
}
this->Float.left_move(n);
while(Float.len>1&&Float.len>pos&&Float.num[Float.len-1]==0)
Float.len--;
}
void right_move(int n=1){
if(n==0)
return ;
if(n<0){
left_move(0-n);
return ;
}
this->Float.right_move(n);
if(this->Float.len<pos)
this->Float.len=pos;
if(this->Float.len<1)
this->Float.len=1;
}
FLOAT operator-(FLOAT &b){
if(iszero()){
FLOAT c(b);
c.Float.flag=(1^b.Float.flag);
return c;
}
if(b.iszero())
return *this;
FLOAT c=*this,d=b;
chx(c,d);
c.Float=c.Float-d.Float;
if(c.pos+1<precision){
c.left_move(precision-c.pos-1);
c.pos=precision-1;
}
return c;
}
FLOAT operator+(FLOAT &b){
if(iszero())
return b;
if(b.iszero())
return *this;
FLOAT c=*this,d=b;
chx(c,d);
c.Float=c.Float+d.Float;
if(c.pos+1<precision){
c.left_move(precision-c.pos-1);
c.pos=precision-1;
}
return c;
}
FLOAT operator*(FLOAT &b){
if(iszero()||b.iszero())
return FLOAT(long(0));
FLOAT c;
c.Float=this->Float*b.Float;
c.pos=this->pos+b.pos+1;
/*
if(c.pos+1<precision){
c.left_move(precision-c.pos-1);//保证结果至少具有precision位有效数字
c.pos=precision-1;
}
*/
for(int i=0,j=c.Float.len;;i++){//去除末尾多余的0
if(c.Float.num[i]!=0||i>c.pos){
c.right_move(i);
j-=i;
c.Float.len=j;
c.pos-=i;
break;
}
}
if(c.Float.len<=c.pos)
c.Float.len=c.pos+1;
return c;
}
FLOAT operator/(FLOAT &b){
if(iszero())
return FLOAT(long(0));
if(b.iszero())
exit(-1);
FLOAT c=*this,d=b;
int key=precision-(c.Float.len-c.pos-d.Float.len+d.pos-1);
if(key>0)
c.left_move(key);
chx(c,d);
c.Float=c.Float/b.Float;
c.pos=key-1;
if(c.pos<0)
c.pos=-1;
if(c.pos>=c.Float.len)
c.Float.len=c.pos+1;
if(c.Float.len<1)
c.Float.len=1;
return c;
}
void print(int k=precision){//输出,k=-1,输出‘＋;其他，k=小数点后位数（暂时没有完成）
int i;
if(k==-1&&this->Float.flag)
printf("+");
if(!this->Float.flag)
printf("-");
if(pos==this->Float.len-1)
printf(".");
printf("%d",this->Float.num[this->Float.len-1]);
if(pos==this->Float.len-2&&pos>-1)
printf(".");
for(i=this->Float.len-2; i>=0; i--) {
printf("%d",this->Float.num[i]);
if(i==pos+1&&i!=0)
printf(".");
}
}

};
inline void chx(FLOAT &a,FLOAT &b){//对阶
if(a.pos==b.pos)
return ;
if(a.pos<b.pos){
a.Float.left_move(b.pos-a.pos);
a.pos=b.pos;
}
if(a.pos>b.pos){
b.Float.left_move(a.pos-b.pos);
b.pos=a.pos;
}
}
inline int cmp(FLOAT &a,FLOAT &b){
chx(a,b);
return cmp(a.Float,b.Float);
}
void Cin(){
string s;
int n;
FLOAT a,b;
while(cin>>s>>n){
if(n<0)
break;
a=FLOAT(s),b=FLOAT(s);
if(n==0){
cout<<1<<endl;
continue;
}
if(a.iszero()){
printf("0\n");
continue;
}
for(int i=1;i<n;i++)
b=a*b;
b.print();
cout<<endl;
}
}
int main(){
Cin();
return 0;
}