ACM必做50题解题-高精度.doc

ACM 必做 50 题的解题- 不要放弃自己! ------- (妈妈曾经这样对我说,转身出门的一刹那,我泪流满面,却不想让任何人看见!) 看到这一句小编也心有感触,想起当初离家前往几千里外的地方的时候,妈妈也说过类似的话,但是身为男儿,必须创出一片天,才能报答父母的养育之恩!! POJ 1001 Exponentiation 高精度数的计算, 以前在网上看到过一个计算大数阶乘比如 10000000 ! 的算法, 总体思想就是将结果用数组保存起来, 然后将结果的每一位与乘数相乘, 当然还有进位... 有了这个算法的思想, 这个题思路就可以是: 先将输入的小数转换成一个整数, 当然这个整数肯定能够用 int 类型的变量保存, 比如 , 通过函数 removeDot ()将它转化成 12345 , 然后利用大数阶乘的思想计算 12345*12345.....*12345, 最后的就是输出了,这个要考虑的情况比较多, 因为这个也 WA了5 次才 AC( 笨的要死), 情况虽多, 但不难. 这道题是高精度计算的,不算很难,但是很繁琐,尤其是对输入输出的要求。被这道题搞了好久,耐心来,一点一点调试,总会成功的。#include<iostream> #include<string> #include<> using namespace std; char ans[10]; char res[2][205]; __int64 ps;// 有几位小数点 int len;// 长度, R 的有效长度// 计算 c=b*a void Multiply(char * b,int bt,char * a,int at,char * c) { int i,j; int up=0; for(i=0;i<at;++i) { up=0; for(j=0;j<bt;j++) { int t; if(c[i+j]==0) c[i+j]='0'; t=(a[i]-48)*(b[j]-48)+c[i+j]-48+up; if(t>=10) { up=t/10; t=t%10; c[i+j]=t+48; if(j==(bt-1) ) c[i+j+1]=(up+48); } else { c[i+j]=t+48; up=0; }}}} int main() { string str; int n; int i,j; int s,t; int pos; while(cin>>str>>n) { i=5; pos=('.',0); if(pos<0)// 没有小数点{ ps=0; //zs=zs*n;// 后面为 0 的总数} else// 有小数点{ ps=(5-pos); ps=ps*n;// 小数位总数} memset(ans,0,sizeof(ans)); memset(res[0],0,sizeof(res[0])); memset(res[1],0,sizeof(res[1])); t=5; s=0; while(str[s]=='0' || str[s]=='.') s++; j=0; for(i=t;i>=s;--i) { if(str[i]=='.') continue; ans[j]=str[i]; j++; } len=j; strcpy(res[0],ans); strcpy(res[1],ans); for(i=2;i<=n;++i) { memset(res[(i+1)%2],0,sizeof(res[0])); Multiply(res[i%2],strlen(res[i%2]),ans,len,res[(i+1)%2]); } int L=strlen(res[(n+1)%2]); int d=(n+1)%2; if(ps>0) { j=0; while(res[d][j]=='0') j++; if(ps>=L) { printf("."); for(i=ps-1;i>=j ;--i) { if(i>=L) printf("0"); else printf("%c",res[(n+1)%2][i]); }} else { if(j>=ps) { for(i=L-1;i>=ps;--i) printf("%c",res[(n+1)%2][i]); } else { for(i=L-1;i>=j ;--i) { if(i==ps) { printf("%c.",res[(n+1)%2][i]); } else printf("%c",res[(n+1)%2][i]); }}}} else { for(i=L-1;i>=0;--i) printf("%c",res[(n+1)%2][i]);