阶乘之和

发表于 分类于 ，
本文讲解了C++语言算法题目阶乘求和，运用高精度乘法与加法

题目来自洛谷平台 （P1009 [NOIP1998 普及组] 阶乘之和）

题目

img

思路

通过题目可以大体看出这道题需要完成阶乘和求和两个算法，通过循环从1遍历到n，先算阶乘再求和

根据n的范围，我们知道n最大可以取到50，那么仅仅计算 n！就已经可以远超 long long 类型的储存范围了，此时需要考虑使用高精度加法和乘法

如果不会这两种算法可以去看之前写过的两篇算法讲解

高精度加法

高精度乘法

创建变量

首先创建两个数组用于保存每一步阶乘与求和的值

mul用于阶乘 add用于求和

为了方便操作，两个数组设置为全局变量；

1
int mul[110] = { 0 }, add[110] = { 0 };

主函数结构

为了使代码清晰明了，将阶乘和求和的功能封装为函数，这一步先写主函数的结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
	mul[100] = 1;//将两个数组中下标为100的元素设置为1，表示1的阶乘和求和
	add[100] = 1;
 
	int n;//创建变量n用于保存输入
	cin >> n;
 
	for (int i = 2; i <= n; i++)//1的阶乘和求和已经在前面完成，所以循环从2开始，到n结束
	{
		Mul(i);//求阶乘的函数
		Add();//求和的函数
	}
	print();//打印结果的函数
 
	return 0;
}

阶乘函数

  1. 创建中间变量t，用于保存进位
  2. 数组中下标100处是数位的第一位，所以从100遍历到0
  3. 第一步，用当前数位的数乘以 x 再加上进位数
  4. 第二步，计算上一步结果的进位，用t保存进位数
  5. 第三步，模拟十进制，将当前数位的值更新为进位后的数

因为每一次计算阶乘都是连续的，例如：2! = 1 × 2 ，3! = 1 × 2 × 3，n! = (n-1)! × n

这个函数中 x 相当于上式的n，数组mul相当于(n-1)!，函数结束计算之后的数组mul相当于n!

因此不需要对每个数都完整的循环求阶乘，可以很大程度减少时间

1
2
3
4
5
6
7
8
9
10
void Mul(int x)
{
	int t = 0;
	for (int i = 100; i >= 0; i--)
	{
		mul[i] = mul[i] * x + t;
		t = mul[i] / 10;
		mul[i] %= 10;
	}
}

求和函数

（求和函数与阶乘函数的原理基本相同，都是按数位依次处理数值）

  1. 创建中间变量t，用于保存进位
  2. 数组中下标100处是数位的第一位，所以从100遍历到0
  3. 第一步，将上一个数阶乘的结果（数组mul）与数组add按数位相加，再加上进位数
  4. 第二步，计算当前数位的进位数，用t保存
  5. 第三步，模拟十进制，将当前数位的值更新为进位后的数

注：数组add保存的值是每次阶乘之后累加的结果

1
2
3
4
5
6
7
8
9
10
void Add()
{
	int t = 0;
	for (int i = 100; i >= 0; i--)
	{
		add[i] = add[i] + mul[i] + t;
		t = add[i] / 10;
		add[i] %= 10;
	}
}

打印函数

因为数字最低位在最右端，所以打印时需要从左端开始遍历

  1. 创建变量s用于保存结果最高位的下标
  2. 第一个for循环用来寻找结果的最高位，消除前导0，找到最高位时用s保存下标，跳出循环
  3. 第二个for循环用来遍历打印结果，从下标s处开始，到下标100处结束

初始化后的数组add中未被修改的元素一定为0，所以寻找最高位只需要从下标0开始遍历，如果add[i]处元素不为0那当前位置就是最高位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void print()
{
	int s = 0;
	for (int i = 0; i <= 100; i++)
	{
		if (add[i] != 0)
		{
			s = i;
			break;
		}
	}
	for (int i = s; i <= 100; i++)
	{
		printf("%d",add[i]);
	}
}

注意

如果构造函数写在主函数之后，不要忘记在主函数之前写函数头，否则函数无法使用

阶乘和求和函数中进位与更新数值的步骤顺序不能写反

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
using namespace std;
 
int mul[110] = { 0 }, add[110] = { 0 };
 
void Mul(int x)
{
	int t = 0;
	for (int i = 100; i >= 0; i--)
	{
		mul[i] = mul[i] * x + t;
		t = mul[i] / 10;
		mul[i] %= 10;
	}
}
 
void Add()
{
	int t = 0;
	for (int i = 100; i >= 0; i--)
	{
		add[i] = add[i] + mul[i] + t;
		t = add[i] / 10;
		add[i] %= 10;
	}
}
 
void print()
{
	int s = 0;
	for (int i = 0; i <= 100; i++)
	{
		if (add[i] != 0)
		{
			s = i;
			break;
		}
	}
	for (int i = s; i <= 100; i++)
	{
		cout << add[i];
	}
}
 
int main()
{
	mul[100] = 1;
	add[100] = 1;
 
	int n;
	cin >> n;
 
	for (int i = 2; i <= n; i++)
	{
		Mul(i);
		Add();
	}
	print();
 
	return 0;
}
如果文章内容有误，欢迎指出