大数乘方 求高精度幂 NOYJ155

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

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

输入

输入有多行，每行有两个数R和n，空格分开。R的数字位数不超过10位。

输出

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

样例输入

95.123 12
0.4321 20
5.1234 15
6.7592  9
98.999 10
1.0100 12

样例输出

548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201

来源

POJ

上传者

iphxer

思路：这道题思路很简单，我的思路是先不看小数点，用大数相乘模板，记录小数位数以后加上小数点。有一点要注意的是，去除前导零的时候要注意100.00这种数，不然输出结果会是1.

代码：

#include<stdio.h>//不能连续复合运算，要保存结果
#include<stdlib.h>//所以一个技巧就是用strcpy来代替等号
#include<string.h>//c=a+b改写为strcpy(c,BigAdd(a,b))
#include<iostream>
using namespace std;
#define BASE 10    //确定进制
#define N 90001    //确定 最大位数+1int l = 0;                      //每次记录缓存区用了多长，还原时节省时间
char res[N] = { '\0' };  //保存结果void ini(char * x , int l);   //初始化x数组
int BigCmp(char * a, char * b);  //  大数a < 大数b 返回1 ，相等返回0 ，a>b返回-1
void Clean(char * x, int l);//清除尾部的‘0’
void rev(char * x);//倒置字符串 ，与Clean联用，清除前导0char * BigAdd(char * a, char * b);//加法
char * BigSub(char * a,char * b);//减法
char * BigMul(char * a,char * b);//乘法char * BigPow(char * num , int n);//大数幂
char * BigMod(char * num , int mod);//大数求余
char * BigFuc(int num);//阶乘
char dot[N]={'\0'};
char s[N]={'\0'};
int main()
{int k;while(scanf("%s %d",&dot,&k)!=EOF){int flag=0;int len=strlen(dot),q=0;memset(res,'\0',sizeof(res));for(int i=0;i<len;i++){//	if(flag==0&&dot[i]=='0') continue;if(dot[i]=='.'){flag=1;q=len-i-1;for(int j=i;j<len;j++)dot[j]=dot[j+1];break;}}/*len=strlen(dot);for(int i=len-1;i>=0;i--){if(dot[i]=='0')dot[i]='\0';else break;}*/len=strlen(dot);for(int i=0;i<len;i++){if(dot[i]=='0')	for(int j=i;j<len;j++)dot[j]=dot[j+1];else break;}//cout<<dot<<endl;//cout<<q<<endl;q=q*k;//cout<<q<<endl;strcpy(s,BigPow(dot,k));int m=strlen(s);if(m==q&&flag){for(int i=m-1;i>=0;i--)if(s[i]=='0') s[i]='\0';else break;cout<<".";for(int i=0;i<m;i++)cout<<s[i];cout<<endl;}else if(m<q&&flag){for(int i=m-1;i>=0;i--)if(s[i]=='0') s[i]='\0';else break;cout<<".";int l=q-m;while(l--)cout<<"0";for(int i=0;i<m;i++)cout<<s[i];cout<<endl;}else if(m>q&&flag){//cout<<s<<endl;int count=0;for(int i=m-1;i>=0;i--){if(s[i]=='0'){count++;}else break;}if(q<=count){for(int i=m-1;m-i-1<q;i--){if(s[i]=='0')s[i]='\0';else break;}cout<<s<<endl;}//	cout<<s<<endl;else{	count=0;	for(int i=m-1;m-i-1<q;i--){if(s[i]=='0'){s[i]='\0';count++;}else break;}m=strlen(s);for(int i=0;i<m;i++){if(m-i-1==q-count)cout<<s[i]<<".";elsecout<<s[i];					}cout<<endl;}}else	cout<<s<<endl;memset(dot,'\0',sizeof(dot));memset(s,'\0',sizeof(s));}return 0;
}
int BigCmp(char * a, char * b)  //  大数a < 大数b 返回1 ，相等返回0 ，a>b返回-1
{int i,j,k;int la = strlen(a),lb = strlen(b);char * temp;if(la < lb)return 1;if(la > lb)return -1;if(la == lb){for(i = 0 ; i < la ; i++){if(a[i] < b[i])return 1;else if(a[i] > b[i])return -1;}}return 0;
}void ini(char * x ,int l)
{int i;if(l < N)l++;for(i = 0 ; i < l ;i++)x[i] = '\0';
}void Clean(char * x,int l)
{for(l--; x[l] == '0';l--)x[l] = '\0';
}void rev(char * x)
{int right = strlen(x)-1;int left = 0;char temp;while(left < right){temp = x[left];x[left++] = x[right];x[right--] = temp;}
}
char *  BigAdd( char * a, char * b)
{int i,j,k;int sum,la,lb,carry,flag,cmp;char *ans,*temp;ini(res,l);carry = 0;flag = 0;ans = &res[1];if(a[0] == '-' && b[0] != '-')         //判断正负return BigSub(b,a+1);else if(a[0] != '-' && b[0] == '-')return BigSub(a,b+1);else if(a[0] == '-' && b[0] == '-'){flag = 1;a++;b++;}la=strlen(a);lb=strlen(b);if(b[0] == '0' && lb == 1)     //判断0{strcpy(ans,a);l = strlen(ans);return ans;}else if(a[0] == '0' && la ==1){strcpy(ans,b);l = strlen(ans);return ans;}rev(a);rev(b);if(BigCmp(a,b) == 1)     //保持大数a>大数b{temp = a;a = b;b =temp;k = la;la = lb;lb = k;}for(i = lb ; i < la ; i++)  //空位补0b[i] = '0';for(i = 0 ; i < la ; i++){sum = (a[i]-48) + (b[i]-48) + carry;if( sum < BASE ){ans[i] = sum + 48;carry = 0;}else{ans[i] = sum  - BASE  + 48;carry = 1;}}if(carry)   //补充最高位{ans[i] = carry + 48;i++;}Clean(ans,i);for(i = lb ; i < la ; i++)//删除后补上的0b[i] = '\0';rev(ans);rev(a);rev(b);if(flag){res[0] = '-';ans = res;}l = strlen(ans);return ans;
}
char * BigSub(char * a,char * b)
{char *ans,*temp;int i,j,k;int borrow,flag,la,lb,sub,cmp;ini(res,l);ans = &res[1];flag = 0;  //结果没有负号borrow = 0;if(a[0]=='-' && b[0]!='-')  //被减数为负，减数为正,结果为负{BigAdd(b,a+1);res[0] = '-';return  res;}else if(a[0]!='-' && b[0]=='-') //被减数为正，减数为负，结果为正return BigAdd(a,b+1);else if(a[0]=='-' && b[0]=='-')   //如果a，b为同时负，交换他们并都改为正，保证为“a-b”的形式{temp=a;a=b;b=temp;a++;b++;}la = strlen(a);lb = strlen(b);if(b[0] == '0' && lb == 1)     //判断0{l = strlen(strcpy(ans,a));return ans;}else if(a[0] == '0' && la == 1){if(b[0] == '-'){l = strlen(strcpy(ans,b+1));return ans;}else{res[0] = '-';l = strlen(strcpy(ans,b));return res;}}cmp = BigCmp(a,b);if(cmp == 0){l = 1;res[0] = '0';res[1] = '\0';return res;}else if(cmp == 1)  //保持大数a>=大数b{temp=a;a=b;b=temp;flag=1;  //结果有负号k = la;la = lb;lb = k;}rev(a);rev(b);for(i=0; i<lb ; i++){sub = a[i] - borrow - b[i];//borrow借位if( sub >= 0){ans[i] = sub + 48;borrow = 0 ;}else    // 溢出时的计算方法{ans[i]   = sub + BASE + 48;borrow = 1;}}while(i < la)   // 计算剩余位{sub = a[i] - borrow ;if(a[i] >= borrow){ans[i]   = sub ;borrow = 0;}else        // 溢出时的计算方法{ans[i]  = sub +BASE ;borrow = 1;}i++;}Clean(ans,i);rev(ans);rev(a);rev(b);if(flag){res[0] = '-';ans = res;}l = strlen(ans);return ans;
}
char * BigMul(char * a,char * b)
{char *temp,*ans;char mul[N] = {'\0'},cal[N] = {'\0'},num[N] = {'\0'};int i,j,k;int carry,flag,la,lb,product,lmul;int sign,sign_a,sign_b;ini(res,l);ans = &res[1];carry = 0;flag = 0;sign = sign_a = sign_b = 0;if(a == b)   //重复拷贝b = strcpy(num,a);if(a[0] == '-' ){flag = 1;sign_a = 1;a++;}if(b[0] == '-' ){flag = 1;sign_b = 1;b++;}if(sign_a && sign_b)flag = 0;la = strlen(a);lb = strlen(b);if((a[0] == '0' && la == 1) || (b[0] == '0' && lb == 1))  //任何一个大数为0，结果为0{l = 1;res[0] = '0';res[1] = '\0';return res;}if(BigCmp(a,b) == 1)   //保证大数a >= 大数b{temp = a;a = b ;b = temp;k = la;la = lb;lb =k;}rev(a);rev(b);Clean(a,la);//清除自带的前导0Clean(b,lb);la = strlen(a);//重新计算长度lb = strlen(b);lmul = 0;for(i = 0 ; i < lb ; i++){ini(mul,lmul);for( j = 0 ; j < la ; j++){product = (a[j] - 48) * (b[i] - 48) + carry ;mul[j] = product % BASE + 48 ;carry = product / BASE ;}if(carry){mul[j] = carry + 48;j++;carry = 0;}lmul = j;  //计算缓冲区长度if(i == 0){strcpy(cal,mul);rev(cal);}else{//清除前导0Clean(mul,lmul);//翻转字符串rev(mul);//以0补位，每次相当于乘10for(k = 0 ; k < i ;k++)//错位相加mul[lmul++] = '0';//保存ans = BigAdd(cal,mul);ini(cal,strlen(cal));strcpy(cal,ans);}}strcpy(ans,cal);rev(a);rev(b);if(flag){res[0] = '-';ans = res;}l = strlen(ans);return ans;
}
char * BigPow(char * num, int n)//快速求幂
{char  * ans;char cal[N] = {'\0'},pow[N] = {'\0'};int  flag;if(n == 0){l = 1;res[0] = '1';res[1] = '\0';return res;}if(strlen(num) == 1 && num[0] == '0'){l = 1;res[0] = '0';res[1] = '\0';return res;}ini(res,l);ans = &res[1];flag = 0;strcpy(pow,num); //备份cal[0] = '1';if(pow[0] == '-' && n&1)flag = 1;while(n){if(n&1){ans = BigMul(cal,num);ini(cal,strlen(cal));strcpy(cal,ans);}ans = BigMul(num,num);ini(num,strlen(num));strcpy(num,ans);n >>= 1;}strcpy(num,pow); //还原strcpy(ans,cal);if(flag){res[0] = '-';ans = res;}l = strlen(ans);return ans;
}