算法入门经典 例题 2-4

访问量：31

题目

阶乘之和：输入 n，计算 S＝1！＋2！＋3！＋…＋n！的末 6 位（不含前导 0）。n≤106 ，n！表示前 n 个正整数之积。

样例输入：

1
10

样例输出：

1
37913

解答

这里应该用双层 for 循环，对于每个 i，乘每一个 j（如程序）。

初版（有 bug）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int main()
{
    int n;
    int sum = 0;
    cin >> n;

    for (int i; i <= n; i++)
    {
        int a = 1;
        for (int j; j <= i; j++)
        {
            a = i * j;
            sum = sum + a;
        }
    }
    sum = sum % 1000000;
    cout << sum;
    return 0;
}

欸？输出是 0？

经过 debug 发现，未初始化循环变量，我在使用循环变量 i 和 j 时没有初始化。

改正版（有 bug）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int main()
{
    int n;
    int sum = 0;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int a = 1;
        for (int j = 1; j <= i; j++)
        {
            a = i * j;
            sum = sum + a;
        }
    }
    sum = sum % 1000000;
    cout << sum;
    return 0;
}

令人费解的是，程序仍然有 bug。

发现：

你在内层循环中使用了 a = i * j;，这会导致计算出错误的阶乘。正确的做法应该是 a *= j;，因为阶乘是通过逐步相乘得到的。

——ChatGPT

为什么？？？

核心算法（a *= j）

使用 a *= j 来计算阶乘的原因是因为阶乘的计算是通过逐步乘积的方式进行的。具体来说，n! 是指从 1 到 n 的所有整数相乘。

我们可以这样表达 n!：

n! = 1 × 2 × 3 × ⋯ × n

因此，为了逐步计算阶乘，我们需要从 1 开始，将每个数字依次乘上当前的 j。

举个栗子：

假设我们要计算 5!，即 5! = 1 * 2 * 3 * 4 * 5。

初始时 a = 1（因为阶乘的起始值是 1）。

  • 第一次循环：a = 1 * 1 = 1（这就是 1!）。
  • 第二次循环：a = 1 * 2 = 2（这就是 2!）。
  • 第三次循环：a = 2 * 3 = 6（这就是 3!）。
  • 第四次循环：a = 6 * 4 = 24（这就是 4!）。
  • 第五次循环：a = 24 * 5 = 120（这就是 5!）。

最终 a 的值为 120，这就是 5! 的正确值。

所以，正确做法是 a *= j。

但是，我未免有一个疑问：

这样的话，外层循环有什么用？？

为什么需要外层循环？

在计算阶乘和时，我们需要依次计算每个数字的阶乘，从 1! 到 n!。这个过程是通过逐个增加数字来完成的。外层循环的作用就是遍历从 1 到 n 的每个整数，确保我们能计算出每个阶乘并累加到总和中。

也就是说，外层循环的变量 i 表示当前正在计算的是 i!，也就是阶乘的目标数字。

再简单一点，就是外层循环（i） 用来控制要计算哪个阶乘（i!），从 1! 到 n!。

再举两个栗子：

  1. 假设 n = 5，我们要计算 1! + 2! + 3! + 4! + 5!：

    • 当 i = 1 时：计算 1!，内层循环执行一次，a = 1。
      • 将 1! 加入到总和。
    • 当 i = 2 时：计算 2! = 1 * 2，内层循环执行两次。
      • 将 2! 加入到总和。
    • 当 i = 3 时：计算 3! = 1 * 2 * 3，内层循环执行三次。
      • 将 3! 加入到总和。
    • 当 i = 4 时：计算 4! = 1 * 2 * 3 * 4，内层循环执行四次。
      • 将 4! 加入到总和。
    • 当 i = 5 时：计算 5! = 1 * 2 * 3 * 4 * 5，内层循环执行五次。
      • 将 5! 加入到总和。

  2. 假设 n = 3：

    • 第一次迭代：i = 1，内层循环计算 1!。a = 1
      • 累加到 sum 中。
    • 第二次迭代：i = 2，内层循环计算 2!。a = 1 * 2 = 2
      • 累加到 sum 中。
    • 第三次迭代：i = 3，内层循环计算 3!。a = 1 * 2 * 3 = 6
      • 累加到 sum 中。
    • 最终，sum 就是 1! + 2! + 3! = 1 + 2 + 6 = 9。

因此，第一层循环是必需的，它控制了计算哪个阶乘以及循环的次数。没有它，我们无法正确地遍历每个数字并计算每个阶乘。

至此，我对这个程序没有任何疑问了。

继续解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int main()
{
    int n;
    long sum = 0;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int a = 1;
        for (int j = 1; j <= i; j++)
        {
            a = a * j;
            sum = sum + a;
        }
    }
    sum = sum % 1000000;
    cout << sum;
    return 0;
}

但是，输出仍然不对。

发现：在内层循环中，每次都重新计算 a = a * j;，并且 sum 在每次内层循环时都被累加。其实只需要在内层循环结束后，将最终的阶乘值累加到 sum 中，而不是每次乘法后都加到 sum。

也就是说，将语句 sum = sum + a; 放在外层循环。

最终版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int main()
{
    int n;
    long long sum = 0;
    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        int a = 1;
        for (int j = 1; j <= i; j++)
        {
            a = a * j;
        }
        sum = sum + a;
    }
    sum = sum % 1000000;
    cout << sum;
    return 0;
}

（这里使用的是数据类型 long long，若您的电脑不支持，请修改）

其实这个程序也能使用单层循环实现，但是我不会 ʅ（´◔౪◔）ʃ 如有大佬还请赐教了。

这个程序是自从打开这本书以来，遇到过最难的程序了。希望下一次能秒懂这些题吧。

祝各位读者早日成为神牛牪犇！