Question

c++一道循环语句题

对于n=2，5，8，11，…，20，23，分别求出E(n) = 1/1! + 1/2! + … + 1/n! 之值并输出它们。要求按如下三种方式来进行求解，并对它们的运行速度及优劣性进行比较。

（1）使用如下轮廓的三重循环来实现：

for(int n=2; n<=23; n+=3) //求出多个不同的E

for (int i=1; i<=n; i++) //共累加n个项

for (int j=1; j<=i; j++) //每个项中用到j的阶乘

…

（2）去掉最内层用来求阶乘的循环，而改为使用二重循环的实现方法：

for(int n=2; n<=23; n+=3) //求出多个不同的E

for (int i=1; i<=n; i++) //共累加n个项

…

（3） 改写成使用一重循环的实现方法：除了去掉用来求阶乘的最内层循环外，还要在求E(5)时接着使用（而不再重新计算）已算出的E(2)值，求E(8)时接着使用已算出的E(5)值，如此等等。

for(int n=1; n<=23; n++) //从第1项开始，一共（最多）累加23项

… //当累加到2，5，8，…，20，23项时，输出当时的累加结果E值

Answer 1

第一种方法：
#include <stdio.h>
#include <time.h>
#include <sys/time.h>

void main()
{
double result[8] = {0};
struct timeval tv_begin, tv_end;

gettimeofday(&tv_begin, NULL);
for(int n = 2; n <= 23; n += 3)
for(int i = 1; i <= n; i++)
{
double temp = 1;
for(int j = 1; j <= i; j++)
temp /= j;
result[n/3] += temp;
}
gettimeofday(&tv_end, NULL);

for(int n = 0; n < 8; n++)
printf("n = %d, result = %.20f\n", n*3+2, result[n]);
printf("time = %dus\n", tv_end.tv_usec - tv_begin.tv_usec);
}
第一种方法的运行结果：
n = 2, result = 1.50000000000000000000
n = 5, result = 1.71666666666666678509
n = 8, result = 1.71827876984127003723
n = 11, result = 1.71828182619849312296
n = 14, result = 1.71828182845822996505
n = 17, result = 1.71828182845904531284
n = 20, result = 1.71828182845904553488
n = 23, result = 1.71828182845904553488
time = 112us

第二种方法：
#include <stdio.h>
#include <time.h>
#include <sys/time.h>

void main()
{
double result[8] = {0};
struct timeval tv_begin, tv_end;

gettimeofday(&tv_begin, NULL);
for(int n = 2; n <= 23; n += 3)
{
double temp = 1;
for(int i = 1; i <= n; i++)
{
temp /= i;
result[n/3] += temp;
}
}
gettimeofday(&tv_end, NULL);

for(int n = 0; n < 8; n++)
printf("n = %d, result = %.20f\n", n*3+2, result[n]);
printf("time = %dus\n", tv_end.tv_usec - tv_begin.tv_usec);
}
第二种方法运行结果：
n = 2, result = 1.50000000000000000000
n = 5, result = 1.71666666666666678509
n = 8, result = 1.71827876984127003723
n = 11, result = 1.71828182619849312296
n = 14, result = 1.71828182845822996505
n = 17, result = 1.71828182845904531284
n = 20, result = 1.71828182845904553488
n = 23, result = 1.71828182845904553488
time = 25us

第三种方法：
#include <stdio.h>
#include <time.h>
#include <sys/time.h>

void main()
{
double temp = 1.0, sum = 0;
struct timeval tv_begin, tv_end;

gettimeofday(&tv_begin, NULL);
for(int n = 1; n <= 23; n++)
{
temp /= n;
sum += temp;
if((n-2)%3 == 0)
printf("n = %d, result = %.20f\n", n*3+2, sum);
}
gettimeofday(&tv_end, NULL);

printf("time = %dus\n", tv_end.tv_usec - tv_begin.tv_usec);
}
第三种方法运行结果：
n = 8, result = 1.50000000000000000000
n = 17, result = 1.71666666666666678509
n = 26, result = 1.71827876984127003723
n = 35, result = 1.71828182619849312296
n = 44, result = 1.71828182845822996505
n = 53, result = 1.71828182845904531284
n = 62, result = 1.71828182845904553488
n = 71, result = 1.71828182845904553488
time = 475us
注：第三种方法结果中的time无参考价值，该方法按照你题目的要求再循环中放入了printf函数做输出，占用大量时间。前两种方法都是将结果先放入数组中，最后再输出结果，printf函数的运行时间不在计算之内，能有效的评价算法的时间复杂度。这三种方法的时间复杂度应该是递减的，第三种方法排除掉printf函数的影响后time的值大约为8us（微秒）

Answer 2

也可以通过递归绕过循环，而且这有很多好处

采用递归求阶乘绕过内存循环
采用递归求 E(n) 绕过第二层循环

下面的代码 VS2010 通过，里面加了简单的计时功能，我把循环次数都增大到 300 是为了让计算机处理起来费时，好让对比效果明显（不增加的话三种方法都在几个 ms 内完成，计时函数计算不出差别）

多运行几次程序，得到最终结果，小规模下 运行效率 方法一 > 方法二 > 方法三
大规模下运行效率 方法三 > 方法二 > 方法一

代码简洁度 方法三 > 方法二 > 方法一

算法难度 方法三 > 方法二 > 方法一

可扩展性 & 可维护性 方法三 > 方法二 > 方法一

#include <iostream>
#include <iomanip>
#include <windows.h>

#define CISHU 50
#define TOPNUM 50

long double fac(long double x) // 递归求阶乘
{
return x > 1 ? x * fac(x - 1) : 1;
}

long double Eval(long double x) // 递归求 E(n)
{
return (x > 1) ? (Eval(x - 1) + 1 / fac(x)) : 1;
}
int main()
{
long double sum = 0, nfac = 1.0;

time_t timeCount = 0, t1 = 0, t2 = 0, t3 = 0;

// 方法一
timeCount = GetTickCount(); // 计时开始
for (size_t n = 0; n != CISHU; n++)
{
system("cls");
std::cout << "\n方法一开始 ……" << std:: endl;

for(size_t n = 2; n <= TOPNUM; n+=3)
{
sum = 0;
for (size_t i = 1; i <= n; i++)
{
nfac = 1;
for (size_t j = 1; j <= i; j++)
{
nfac *= j;
}
sum += (1 / nfac);
}

if (n < 24)
{
std::cout << "E(" << n << ") =\t\t" << std::setprecision(18) << sum << std::endl;
}

}
}
t1 = GetTickCount() - timeCount; // 计时结束

// 方法二
timeCount = GetTickCount(); // 计时开始
for (size_t n = 0; n != CISHU; n++)
{
system("cls");
std::cout << "\n方法二开始 ……" << std:: endl;

for(size_t n = 2; n <= TOPNUM; n+=3)
{
sum = 0;
for (size_t i = 1; i <= n; i++)
{
sum += (1 / fac(i));
}

if (n < 24)
{
std::cout << "E(" << n << ") =\t\t" << std::setprecision(18) << sum << std::endl;
}

}
}
t2 = GetTickCount() - timeCount; // 计时结束

// 方法三
timeCount = GetTickCount(); // 计时开始
for (size_t n = 0; n != CISHU; n++)
{
system("cls");
std::cout << "\n方法三开始 ……" << std:: endl;

for(size_t n = 2; n <= TOPNUM; n+=3)
{
sum = Eval(n);

if (n < 24)
{
std::cout << "E(" << n << ") =\t\t" << std::setprecision(18) << sum << std::endl;
}

}

}
t3 = GetTickCount() - timeCount; // 计时结束

std::cout << sum << "\n\n 方法一用时: " << t1 << std::endl;
std::cout << sum << "\n\n 方法二用时: " << t2 << std::endl;
std::cout << sum << "\n\n 方法三用时: " << t3 << std::endl;

return 0;
}

Answer 3

（1）使用如下轮廓的三重循环来实现：
double E[8]={0};
for(int n=2; n<=23; n+=3) //求出多个不同的E
{

for (int i=1; i<=n; i++) //共累加n个项
{
double temp=1;
for (int j=1; j<=i; j++) //每个项中用到j的阶乘
temp*=j;
E[(n-2)/3]+=1/temp;
}
cout<<"E("<<n<<")="<<E[(n-2)/3]<<endl;
}
（2）去掉最内层用来求阶乘的循环，而改为使用二重循环的实现方法：
double E[8]={0};
for(int n=2; n<=23; n+=3) //求出多个不同的E
{
double temp=1;
for (int i=1; i<=n; i++) //共累加n个项
{
temp=temp*i;
E[(n-2)/3]+=1/temp;
}
cout<<"E("<<n<<")="<<E[(n-2)/3]<<endl;
}
（3）
double k=0,temp=1;
for(int n=1; n<=23; n++) //从第1项开始，一共（最多）累加23项
{
temp=temp*n;
k+=1/temp;
if((n-2)%3==0)
cout<<"E("<<n<<")="<<k<<endl;
}
运行速度为1<2<3;

Answer 4

#include<iostream>
using namespace std;
int main()
{
double result;
int temp,n,i,j,k;
for(n=2; n<=23; n+=3) //求出多个不同的E
{
result=0;
for (i=1; i<=n; i++) //共累加n个项
{
temp=1;
for (j=1; j<=i; j++) temp*=j;
result+=1/(double)temp;
}
cout<<n<<'\t'<<result<<endl;
}
for(n=2; n<=23; n+=3) //求出多个不同的E
{
result=0;
temp=1;
for (i=1; i<=n; i++)
{
temp*=i;
result+=1/(double)temp;
}
cout<<n<<'\t'<<result<<endl;
}
result=0;
temp=1;
for(n=1; n<=23; n++) //求出多个不同的E
{
temp*=n;
result+=1/(double)temp;
if((n+1)%3==0)cout<<n<<'\t'<<result<<endl;

}
}