求阶乘的和

题意

求 $1!+2!+\cdots+n!$ 。

思路

不必每次从头计算阶乘。若 factorial 已经是 $(i-1)!$ ，乘上 $i$ 就得到 $i!$ ；把它加入 total 后继续下一轮即可。

代码

Python代码

python

1
2
3
4
5
6
7
8
9limit = int(input())
factorial = 1
total = 0

for number in range(1, limit + 1):
    factorial *= number
    total += factorial

print(total)

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15#include <cstdio>


int main(){
    int n;
    scanf("%d",&n);
    int sum=0,i,s = 1;
    for (i=1;i<=n;i++){
        s = s*i;
        sum += s;
    }
    printf("%d\n",sum);

    return 0;
}

复杂度

时间复杂度为 $O(n)$ ，额外空间复杂度为 $O(1)$ 。

总结

相邻阶乘只差一次乘法，维护递推值比重复计算更清晰也更高效。

目录

题意

思路

代码

Python代码

C++代码

复杂度

总结