第1章 设计性实验 实验题4：求连续整数阶乘的和。编写一个程序，对于给定的正整数n，求1!+2!+3!+...+n!，给出一种时间复杂度为O(n)的解法。（可以使用Dev C++进行程序编写和运行，运行成功后，把程序代码和运行截图输入答案框。）

设计性实验题4要求我们编写一个程序，用于计算从1到n的所有连续整数的阶乘之和。为了达到O(n)的时间复杂度，我们可以采用循环结构，并依次将每个整数i的阶乘加到总和上。这里是一个基本的C++程序示例：

#include <iostream>
using namespace std;

// 计算阶乘
unsigned long long factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

int main() {
    int n;
    cout << "请输入一个正整数n: ";
    cin >> n;

    unsigned long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += factorial(i);
    }

    cout << "1! + 2! + ... + " << n << "! 的和是: " << sum << endl;

    // 这里假设你已经得到了程序运行的结果，如屏幕截图或直接输出
    // 此处省略了实际的运行结果展示

    return 0;
}

在这个程序中，`factorial`函数递归地计算阶乘，而主循环负责累加阶乘值。由于每次循环都会计算一次阶乘，所以总的时间复杂度是线性的，即O(n)。

相关问题

实验题：常见算法时间函数的增长趋势分析 目的：理解常见算法时间函数的增长情况。 内容：编写一个程序 exp1.cpp,对于1~n（n=10）的每个整数n，输出 log2n、√n、n、nlog2n、n²、n3、2”和n！的值。

实验题目要求你分析几种常见的算术运算和递归计算的时间复杂度。这些运算包括对数（log2n）、平方根（√n）、线性（n）、线性对数（nlog2n）、平方（n²）、立方（n³）、常数乘法（2^n），以及阶乘（n!）。这里的关键是理解每种操作随着输入n增加时，它们所需的时间是如何增长的。

1. 对数（log2n）：通常表现为线性的较低次幂，比如O(log n)。这是因为二进制树的高度通常是log(n)，所以查找、分割等操作的次数大致如此。

2. 平方根（√n）：这是一个渐近于线性的操作，因为计算n的平方根所需的步骤数量不会超过n的平方根本身，所以时间复杂度是O(√n)。

3. 线性（n）：这个是最直接的，对于每一个元素的操作都独立执行，所以时间复杂度是O(n)。

4. 线性对数（nlog2n）：这通常是排序或搜索算法的时间复杂度，例如快速排序和二分查找，每次操作后都要缩小一半搜索范围。

5. 平方（n²）：典型的二次操作，如两个数组完全相乘或简单的图形面积计算，所需步骤的数量是n的平方。

6. 立方（n³）：这是立方操作，如三维空间中的体积计算，时间复杂度为三次方。

7. 常数乘法（2^n）：这是一种指数级增长，当n增大时，增长速度非常快，比如计算2的n次方。

8. 阶乘（n！）：如果用循环计算，其时间复杂度也是O(n)，因为需要依次乘到n，但阶乘的增长速度比上述所有更快，因为它包含了所有小于等于n的正整数。

为了实现这个程序，你可以使用C++编写一个循环，对于给定的范围内的每个n，计算并打印这些表达式的值。以下是一个简化的示例代码：

#include <iostream>
#include <cmath>

int main() {
    const int maxN = 10;
    for (int n = 1; n <= maxN; ++n) {
        std::cout << "n = " << n << ": ";
        std::cout << "log2(" << n << ") = " << log2(n) << "\n";
        std::cout << "sqrt(n) = " << sqrt(n) << "\n";
        std::cout << "n = " << n << "\n";
        std::cout << "n * log2(n) = " << n * log2(n) << "\n";
        std::cout << "n^2 = " << n * n << "\n";
        std::cout << "n^3 = " << n * n * n << "\n";
        std::cout << "2^n = " << pow(2, n) << "\n";
        std::cout << "factorial(n) = " << factorial(n) << "\n"; // 自定义阶乘函数
        std::cout << "\n";
    }
    return 0;
}

// 用于计算阶乘的辅助函数
long long factorial(int n) {
    if (n == 0 || n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

运行这段代码，你会看到不同操作在n从1到10的变化趋势。记住，这只是理论上的增长趋势，实际运行时间还会受到具体实现、编译器优化等因素的影响。完成实验后，你可以总结每种运算的典型时间复杂性，并思考它们的实际应用场景。