有关于阶乘的相关理解

---

一、正常阶乘求算

阶乘的算法可能会比较麻烦，一般会想到用 for 循环来计算阶乘
这里用 for 循环来写函数

long long Factorial(int n){
	if(n == 0){			//注意0的阶乘为1
		return 1;
	}
	long long box = 1;
	for(int i = 1; i <= n; i++){
		box *= i;
	}
	return box;
}
1
2
3
4
5
6
7
8
9
10

如果用递归的思想来实现

long long Factorial(int n){
	if(n == 1 || n == 0){
		return 1;
	}else{
		return n * Factorial(n-1);
	}
}
1
2
3
4
5
6
7

二、1~n 阶乘的和

如果按照上述方法继续来求的话，for 循环和递归的时间复杂度为O(n²)，会造成时间超限的问题。

---

还用一种方法是从 1~n 的阶乘和中找特点，例如：
1 + 1 * 2 + 1 * 2 * 3 + … + 1 * 2 * … * n;
提公因式法，先提公因式 1。
1 * (1 + 2 + 2 * 3 + … + 2 * … * n)
然后再提取 2
1 * (1 + 2 (1 + 3 + … + 3 * … * n))
依次类推
1 * (1 + 2 (1 + 3 (1 + 4(…n + 1))))
所以就有规律 (n - 1) * (n + 1)

代码实现如下：

long long FacAdd(int n){
	if(n == 0){
		return 1;
	}
	long long box = 0;
	for(int i = n; i >= 1; i--){
		box = (box + 1) * i;
	}
	return box;
}
1
2
3
4
5
6
7
8
9
10