用小数数组计算E值(对ZOJ第1113题的解答)

简介: 这道题目:http://acm.zju.edu.cn/show_problem.php?pid=1113 的大意如下:根据公式 e=1/0!+1/1!+1/2!+1/3!+...+1/n! 计算e。
这道题目: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的结果,所以这时我们无需对结果进行规整处理。
一个小数除以一个整数
#define DISLEN 9    /*最多小数位数*/
#define TOTLEN 13    /*总长度,即显示小数位数+冗余的小数位数*/
/*计算一个0.--的小数除以一个整数后的小数。*/
void Devide(int a[],int n)
{
    
int i,temp;/*余数*/
    
for(i=1; i<=a[0&& i<(TOTLEN-1); i++)
    {
        temp
=a[i]%n;    /*先保存余数!!!不能先改变a[i],切记!*/
        a[i]
=a[i]/n;
        a[i
+1]+=temp*10;
        
if(i==a[0&& temp!=0)
            a[
0]=i+1;
    }
    
/*对最后一位进行除法运算*/
    a[TOTLEN
-1]/=n;
}
由于结果需要四舍五入,所以实际上我给出了一些冗余位,以保持四舍五入时候的结果正确。
下面是两个小数相加的运算代码,即a=a+b,结果是a被改变为两者的和,b不发生变化。在a的基础上改动,可以使我们节省空间。相对而言,大数相加减的代码是最为简单直观的。
两个小数相加
/*注意两个正小数相加,他们的最大位数只可能减少,不可能增加!*/
void Add(int a[],int b[])
{
    
int i;
    a[
0]=MAX(a[0],b[0]);
    
for(i=1;i<=a[0];i++)
    {
        a[i]
+=b[i];
    }
    
/*规整小数*/
    formular(a);
}
/*加法后的规整小数*/
void formular(int a[])
{
    
int i;
    
for(i=a[0];i>1;i--)
    {
        a[i
-1]+=a[i]/10;
        a[i]
=a[i]%10;
    }
    a[
1]=a[1]%10;

    
/*当最后一位为0时,位数递减(缩减位数)*/
    
while(!a[a[0]] && a[0])
    {
        a[
0]--;
    }
}
注意,两个小数相加以后,可能产生结果在某些位大于10,因此这时需要一次规整运算。
最后,我们还需要对数组进行一次扫描,输出四舍五入后的结果:由于我们的目的是计算e,因此整数部分是确定的“2.”。
输出四舍五入后的结果值
/*输出e的小数表示,用2.开始,e[]中是小数部分*/
void OutputE(int a[])
{
    
/*len表示四舍五入后的小数长度,flag表示是否进位!*/
    
int i,len,flag;
    printf(
"2.");
    
/*对最后一位进行四舍五入!如果位数不大于DISLEN说明无需四舍五入*/


    len
=DISLEN+1;
    
if(a[len]>4)
    {
        flag
=1;
        
while(a[--len]==9);
    }
    
else
    {
        flag
=0;
        
while(a[--len]==0);
    }
    
    
/*打印前几个字符*/
    
for(i=1;i<len;i++)
        printf(
"%d",a[i]);
    
/*根据是否进位,打印最后一个数字*/
    
if(len>0)
        printf(
"%d",flag? (a[len]+1):a[len]);
    
for(i=len+1;i<=DISLEN;i++)
        printf(
"0");
    printf(
"\n");
}
最后我们给出迭代部分的代码,由于使用迭代式,因此下一步的计算建立在前一步的计算结果的基础上,这样就避免了冗余计算。
迭代E的结果
int e[TOTLEN],a[TOTLEN];
/* e2=2.5, a2=0.5 */
e[
0]=a[0]=1;
e[
1]=a[1]=5;

for(j=3;j<=9;j++)
{
    Devide(a,j);    
/*a[n+1]=a[n]/(n+1);*/
    Add(e,a);        
/*e[n+1]=e[n]+a[n+1];*/
    printf(
"%d ",j);
    OutputE(e);
}

当我们想要输出80位小数时,结果如下(显然可以直接运算的内部数据类型是无法达到这样精度的):
2.71828182845904523536028747135266249775724709369995957496696762772407663035354759
目录
相关文章
|
2月前
两个整数相加
【10月更文挑战第12天】两个整数相加
19 5
|
4月前
|
C语言
用栈实现将一个十进制数值转换成八进制数值。即用该十进制数值除以8,并保留其余数;重复此操作,直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的八进制数值
这篇文章展示了如何使用栈(包括顺序栈和链栈)实现将十进制数值转换成八进制数值的方法,通过C语言编程演示了两种栈的实现方式和使用场景。
用栈实现将一个十进制数值转换成八进制数值。即用该十进制数值除以8,并保留其余数;重复此操作,直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的八进制数值
|
7月前
|
人工智能
PTA-求整数的位数及各位数字之和
求整数的位数及各位数字之和
63 4
|
7月前
|
Java
如何判断科学计数法3.14E+308 在区间3.14E+38和 3.14E+1308内
对于非常大的科学计数法表示的数值,直接将其转换为 `double` 类型可能会导致溢出。Java 中的 `double` 类型表示的最大值约为 `1.7976931348623157E+308`,因此 `3.14E+308` 已经超出了其表示范围。如果需要处理超出 `double` 类型表示范围的数值,可以使用 `BigDecimal` 类来处理。 以下是一个示例,展示如何使用 `BigDecimal` 类来比较科学计数法表示的数值是否在指定区间内: ```java import java.math.BigDecimal; public class ScientificNotationC
【剑指offer】-数值的整数次方-12/67
【剑指offer】-数值的整数次方-12/67
剑指offer 15. 数值的整数次方
剑指offer 15. 数值的整数次方
53 0
35.数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方
52 0
35.数值的整数次方
|
前端开发 JavaScript 程序员
数值的整数次方
数值的整数次方
数值的整数次方
输出最小的数位和等于x并且各个数位都不一样的值
输出最小的数位和等于x并且各个数位都不一样的值
47 0
AcWing 720. 连续整数相加
AcWing 720. 连续整数相加
86 0
AcWing 720. 连续整数相加