北京大学ACM1001题详细解答

《北京大学ACM1001题详细解答》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、高精度00748067张姣DescriptionProblemsinvolvingthecomputationofexactvaluesofverylargemagnitudeandprecisionarecommon.Forexample,thecomputationofthenationaldebtisataxingexperienceformanycomputersystems.ThisproblemrequiresthatyouwriteaprogramtocomputetheexactvalueofRnwhereRisarealnumber(

2、0.0

3、utput.Insignificanttrailingzerosmustnotbeprinted.Don'tprintthedecimalpointiftheresultisaninteger.Poj1001题目描述：涉及到大数据的要求精确计算的问题是很常见的。比如要求计算国家借款对于许多电脑系统是一个非常繁重的任务。本题中要求计算一个在零到一百以内的实数的n次方（0

4、实型能表示的范围，肯定不能直接用一个数的形式来表示。能表示多个数的数据类型有两种：数组和字符串。（1）数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多少个数组元素；优点：每一位都是数的形式，可以直接加减；运算时非常方便缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；（2）字符串：字符串的最大长度是255，可以表示255位。优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运算时非常不方便

5、（注意‘0’的问题）。优化:一个数组元素存放四位数注意：是加减法时可以用interger，但是当是乘法的时候，就要用int64，否则会出现越界的情况。还有就是：输出时对非最高位的补零处理。另一个问题：存储顺序正序？？逆序？？还有就是一定不要忘了初始化！！计算结果位数的确定两数之和的位数最大为较大的数的位数加1。乘积的位数最大为两个因子的位数之和。阶乘：lgn!=lgn+lg(n-1)+lg(n-2)...................+lg3+lg2+lg1=lnn/ln10+ln(n-1)/ln10+ln(n-2)/ln10+.............

6、...+ln3/ln10+ln2/ln10+ln1/ln10=trunc(1/ln10*   (lnn+ln(n-1)+ln(n-2)+...........+ln3+ln2+ln1)乘方：lg(a^b)=trunc(lg(a^b))+1                        =trunc(b*lga )+1                        =trunc(b*lna / ln10)+1高精度的加法ncarry=0;for(i=0;i<=len;i++){k=a[i]+b[i]+ncarry;a[i+1]+=k/N;ncarry=k

7、%N;}当最后ncarry>0时，len会变化！！高精度的减法先比较大小，大的为a，用一个变量记录符号。ncarry=0;for(i=0;i<=len;i++){if(a[i]-b[i]-ncarry>=0)a[i]=a[i]-b[i]-ncarry,ncarry=0;elsea[i]=a[i]+N-b[i]-ncarry,ncarry=1;}高精度的乘法For(i=0;i<=lena;i++)for(j=0;j<=lenb;j++)c[i+j]+=a[i]*b[j];For(i=0;i<=lena+lenb;i++){c[i+j+1]+=c[i+j]/N

8、;c[i+j]=c[i+j]/N;}这道题：1.处理小数点问题，以