这道题目:http://acm.zju.edu.cn/show_problem.php?pid=1113 的大意如下:根据公式
e=1/0!+1/1!+1/2!+1/3!+...+1/n!
计算e。要求输出需要的小数位数(9位)。
题目很直观,最直观的想法可能是一个计算n!的函数,然后一个从0到n的循环,累加所有的小数。不过这样做显然会有很多冗余计算。为了避免这种情况,显然,
假设a[n]表示1/n!,e[n]表示e,则
a[n+1]=a[n]/(n+1);
e[n+1]=e[n]+a[n+1];
根据这个等式,我们可以写出解答方法。由于题目中要求小数精度,也许随着计算机位数的增长,double能够满足精度。但是在16位的TC下似乎是无法满足的,所以考虑用大数方法处理小数。即使用一个数组a[]表示小数部分。(这里假设小数具有0.********的形式),按照这个处理方法的惯例,我们规定,
a[0]表示小数的数据位数,a[i] (i>0)中存放第i位小数的数字。例如PI 3.1415926,它的小数部分可以用下面的数组表示:
{7,1,4,1,5,9,2,6,0,0,0,........};
那么这个小数就可以表示成
a[1]*10^(-1)+a[2]*10^(-2)+...+a[n]*10^(-n)
由于
a * 10^(-i) + (10*b + c) * 10^(-(i+1)) = (a+b) * 10^(-i) + c * 10 ^(-(i+1))
所以,相邻位之间以此规则进位或者退位以及规整。
根据上面的迭代式子,我们看到至少两种小数运算,一个是小数除以整数,一个是两个小数相加。在这个题目中实际上精度不高,因此对代码执行效率的要求可以降低,但是为了通用,我还是保持该算法的惯用风格。
下面,给出一个小数除以一个整数的代码,由于一个已经规整过的小数这样运算的时候,不可能出现大于10的结果,所以这时我们无需对结果进行规整处理。
下面是两个小数相加的运算代码,即a=a+b,结果是a被改变为两者的和,b不发生变化。在a的基础上改动,可以使我们节省空间。相对而言,大数相加减的代码是最为简单直观的。
最后,我们还需要对数组进行一次扫描,输出四舍五入后的结果:由于我们的目的是计算e,因此整数部分是确定的“2.”。
当我们想要输出80位小数时,结果如下(显然可以直接运算的内部数据类型是无法达到这样精度的):
2.71828182845904523536028747135266249775724709369995957496696762772407663035354759
e=1/0!+1/1!+1/2!+1/3!+...+1/n!
计算e。要求输出需要的小数位数(9位)。
题目很直观,最直观的想法可能是一个计算n!的函数,然后一个从0到n的循环,累加所有的小数。不过这样做显然会有很多冗余计算。为了避免这种情况,显然,
假设a[n]表示1/n!,e[n]表示e,则
a[n+1]=a[n]/(n+1);
e[n+1]=e[n]+a[n+1];
根据这个等式,我们可以写出解答方法。由于题目中要求小数精度,也许随着计算机位数的增长,double能够满足精度。但是在16位的TC下似乎是无法满足的,所以考虑用大数方法处理小数。即使用一个数组a[]表示小数部分。(这里假设小数具有0.********的形式),按照这个处理方法的惯例,我们规定,
a[0]表示小数的数据位数,a[i] (i>0)中存放第i位小数的数字。例如PI 3.1415926,它的小数部分可以用下面的数组表示:
{7,1,4,1,5,9,2,6,0,0,0,........};
那么这个小数就可以表示成
a[1]*10^(-1)+a[2]*10^(-2)+...+a[n]*10^(-n)
由于
a * 10^(-i) + (10*b + c) * 10^(-(i+1)) = (a+b) * 10^(-i) + c * 10 ^(-(i+1))
所以,相邻位之间以此规则进位或者退位以及规整。
根据上面的迭代式子,我们看到至少两种小数运算,一个是小数除以整数,一个是两个小数相加。在这个题目中实际上精度不高,因此对代码执行效率的要求可以降低,但是为了通用,我还是保持该算法的惯用风格。
下面,给出一个小数除以一个整数的代码,由于一个已经规整过的小数这样运算的时候,不可能出现大于10的结果,所以这时我们无需对结果进行规整处理。
一个小数除以一个整数
由于结果需要四舍五入,所以实际上我给出了一些冗余位,以保持四舍五入时候的结果正确。
下面是两个小数相加的运算代码,即a=a+b,结果是a被改变为两者的和,b不发生变化。在a的基础上改动,可以使我们节省空间。相对而言,大数相加减的代码是最为简单直观的。
两个小数相加
注意,两个小数相加以后,可能产生结果在某些位大于10,因此这时需要一次规整运算。
最后,我们还需要对数组进行一次扫描,输出四舍五入后的结果:由于我们的目的是计算e,因此整数部分是确定的“2.”。
输出四舍五入后的结果值
最后我们给出迭代部分的代码,由于使用迭代式,因此下一步的计算建立在前一步的计算结果的基础上,这样就避免了冗余计算。
迭代E的结果
当我们想要输出80位小数时,结果如下(显然可以直接运算的内部数据类型是无法达到这样精度的):
2.71828182845904523536028747135266249775724709369995957496696762772407663035354759