华师一附中OI组

标题: P1729 计算e [打印本页]
作者: admin    时间: 2020-2-2 16:35
标题: P1729 计算e
题目描述
月落乌啼竟然这么快就回复了圆周率小数点后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    时间: 2020-2-2 16:36
此题出的很好。考察点很多，要是都能做出来的话，基本的程序设计就过关了。
作者: admin    时间: 2020-2-2 16:36
这里我有步步为营逐步改进的方法来给大家演示这个题的解法，首先，我们不用高精度，做一个基本的程序框架，
假设用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;

  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. }
复制代码





欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2