用小数数组计算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
目录
相关文章
|
6天前
|
云安全 人工智能 安全
AI被攻击怎么办?
阿里云提供 AI 全栈安全能力,其中对网络攻击的主动识别、智能阻断与快速响应构成其核心防线,依托原生安全防护为客户筑牢免疫屏障。
|
15天前
|
域名解析 人工智能
【实操攻略】手把手教学,免费领取.CN域名
即日起至2025年12月31日,购买万小智AI建站或云·企业官网,每单可免费领1个.CN域名首年!跟我了解领取攻略吧~
|
10天前
|
安全 Java Android开发
深度解析 Android 崩溃捕获原理及从崩溃到归因的闭环实践
崩溃堆栈全是 a.b.c?Native 错误查不到行号?本文详解 Android 崩溃采集全链路原理,教你如何把“天书”变“说明书”。RUM SDK 已支持一键接入。
616 216
|
存储 人工智能 监控
从代码生成到自主决策:打造一个Coding驱动的“自我编程”Agent
本文介绍了一种基于LLM的“自我编程”Agent系统,通过代码驱动实现复杂逻辑。该Agent以Python为执行引擎,结合Py4j实现Java与Python交互,支持多工具调用、记忆分层与上下文工程,具备感知、认知、表达、自我评估等能力模块,目标是打造可进化的“1.5线”智能助手。
857 61
|
8天前
|
人工智能 移动开发 自然语言处理
2025最新HTML静态网页制作工具推荐:10款免费在线生成器小白也能5分钟上手
晓猛团队精选2025年10款真正免费、无需编程的在线HTML建站工具,涵盖AI生成、拖拽编辑、设计稿转代码等多种类型,均支持浏览器直接使用、快速出图与文件导出,特别适合零基础用户快速搭建个人网站、落地页或企业官网。
1294 157
|
5天前
|
编解码 Linux 数据安全/隐私保护
教程分享免费视频压缩软件,免费视频压缩,视频压缩免费,附压缩方法及学习教程
教程分享免费视频压缩软件,免费视频压缩,视频压缩免费,附压缩方法及学习教程
243 138
|
7天前
|
存储 安全 固态存储
四款WIN PE工具,都可以实现U盘安装教程
Windows PE是基于NT内核的轻量系统,用于系统安装、分区管理及故障修复。本文推荐多款PE制作工具,支持U盘启动,兼容UEFI/Legacy模式,具备备份还原、驱动识别等功能,操作简便,适合新旧电脑维护使用。
535 109