编写一个程序exp1-4.cpp对于给定的正整数n,求1!+2!+3!+...n!给出一种时间复杂度为O(n)的解法
时间: 2024-09-07 20:04:09 浏览: 27
在编写程序`exp1-4.cpp`时,我们可以利用阶乘的数学性质来降低时间复杂度。具体来说,n的阶乘可以通过`(n-1)!`来计算,即`n! = n * (n-1)!`。基于这个性质,我们可以用一个循环来逐步计算阶乘,并累加到总和中。这样,每次计算新的阶乘时,我们只需要将前一个阶乘与当前的数字相乘即可。由于每一步中我们只进行一次乘法操作,整个算法的时间复杂度为O(n)。
下面是一个简单的实现示例:
```cpp
#include <iostream>
using namespace std;
// 函数用于计算阶乘的和
long long sumOfFactorials(int n) {
long long sum = 0; // 总和初始化为0
long long factorial = 1; // 阶乘初始值为1(0! 和 1!)
for (int i = 1; i <= n; ++i) {
factorial *= i; // 计算i的阶乘
sum += factorial; // 将当前阶乘加到总和中
}
return sum; // 返回阶乘的和
}
int main() {
int n;
cout << "请输入一个正整数n: ";
cin >> n; // 读取用户输入
// 计算并输出阶乘的和
cout << "1! + 2! + ... + " << n << "! = " << sumOfFactorials(n) << endl;
return 0;
}
```
在这个程序中,我们首先定义了一个`sumOfFactorials`函数,它接受一个整数`n`作为参数,并返回从1到`n`的阶乘和。然后,在`main`函数中,我们从用户那里获取这个`n`值,并调用`sumOfFactorials`函数计算结果,最后输出结果。