P1729 计算e

admin

题目描述
月落乌啼竟然这么快就回复了圆周率小数点后10000位？！不可能，他肯定求了别人。爱与愁大神再次为难月落乌啼：“帮我算一算e后n（n<=10000）位，速度！！！”月落乌啼想求别人，结果他发现由于刚才跟你通话已经用完了手机的所有电。关键时刻只能靠自己。如果现在你是他，你会怎么编这个程序？
e=1+1/1!+1/2!+***1/n!
输入格式
只有一行：n
输出格式
若干行。

第一行：2.
第二行开始：e的小数部分。10个数一个空格，50个数一次回车。

输入输出样例
输入 #1
100
输出 #1
2.
7182818284 5904523536 0287471352 6624977572 4709369995
9574966967 6277240766 3035354759 4571382178 5251664274

说明/提示
30%数据：n<=1000
100%数据：n<=10000
时限：全部1秒

admin

这里我有步步为营逐步改进的方法来给大家演示这个题的解法，首先，我们不用高精度，做一个基本的程序框架，
假设用s表示最后的结果，a表示每个单项的结果，仔细观察会发现a=a/i，虽然a=1/1!，但是后者不便于计算。

1. #include<iostream>
   
2. using namespace std;
   
3. double s,a;
   
4. int i,n;
   
5. int main()
   
6. {
   
7.         n=10;
   
8.         s=a=1;
   
9.         for (i=1; i<=n; i++)
   
10.         {
    
11.                 a=a/i;
    
12.                 s=s+a;
    
13.         }
    
14.         cout<<s;
    
15.         return 0;
    
16. }

复制代码

运行此程序，答案是2.718，验证思路是正确的。那么现在就是要在这题里面改进高精度的加法和除法。
显然复习前面的单精度除法，

1. #include<iostream>
   
2. using namespace std;
   
3. const int  mm=10010;
   
4. int a[mm],s[mm],i,p,x,n;
   
5. int main()
   
6. {
   
7.         cin>>n;
   
8. 
   
9.         for (p=0; p<=mm-1; p++) a[p]=s[p]=0;
   
10.         s[0]=a[0]=1;
    
11.         for (i=1; i<=10000; i++) ///先计算到100试试看
    
12.         {
    
13.                 ///a=a/i;
    
14.                 x=0;
    
15.                 for (p=0; p<=mm-1; p++)
    
16.                 {
    
17.                         x=10*x+a[p];
    
18.                         a[p]=x/i;
    
19.                         x=x%i;
    
20.                 }
    
21.                 int sa=0;
    
22.                 for (p=0;p<=n+10;p++) sa+=a[p];
    
23.                 if (sa==0)  break;
    
24.                 ///s=s+a;
    
25.                 for (p=0; p<=mm-1; p++) s[p]+=a[p];
    
26.                 ///jinwei
    
27.                 for (p=mm-1; p>0; p--) ///右往左
    
28.                 {
    
29.                         int x=s[p];
    
30.                         s[p]=x%10;
    
31.                         s[p-1]+=x/10;
    
32.                 }
    
33.         }
    
34.         cout<<"2."<<endl;
    
35.         for (p=1; p<=n; p++)
    
36.         {
    
37.                 cout<<s[p];
    
38.                 if (p%10==0)  cout<<' ';
    
39.                 if (p%50==0)  cout<<endl;
    
40.         }
    
41. }

复制代码

admin

此题出的很好。考察点很多，要是都能做出来的话，基本的程序设计就过关了。