[数据结构与算法]C++的高精乘＋高精加

题目

想法

?这题的原型就是在简单的求阶乘和基础上加入一个高精度操作

那么把求阶乘的两步操作用升级版的高精度函数代替即可

👆 所说的两步操作即为：

// FOR循环内 第一步单独求每一项阶乘 第二步把各项相加 代码实现如下：

for(int i = 0; i < N; ++i) {

? ? ? ? num *= i;

? ? ? ? sum += num;

}

题解【BY SocietyNiu】

#include<iostream>
using namespace std;
#define N 1000
int arr[N+1000] = { 0 };
int sum[N+1000] = { 0 };
int num;
void ppuls(int* arr, int* sum) // 高精加
{
	int jw = 0;// u must set jw inside the function otherwise it'll be change by other function
	for (int i = 1; i <= N; ++i) 
	{
		sum[i] += arr[i] + jw;
		jw = sum[i] / 10;
		sum[i] %= 10;
	}
	return;
	//++jw;
	//cout << jw << endl;
}
void pmut(int* arr, int n) // 高精乘
{
	int jw = 0;
	for (int i = 1; i <= N; ++i)
	{
		arr[i] = arr[i] * n + jw;
		jw = arr[i] / 10;
		arr[i] %= 10;
	}
	return;
	//++jw;
	//cout << jw;
}
int main() 
{
	// ceculate
	cin >> num;
	arr[1] = 1; // do not forget this!!
	for (int i = 1; i <= num; ++i)
	{
		pmut(arr, i);
		ppuls(arr, sum);
	}
	
	// print
	int flag = 0; // decline the front "0"
	for (int i = N; i >= 1; --i) // 倒叙
	{
		if (sum[i] != 0)
			++flag;
		if (flag)
			cout << sum[i];
	}
	return 0;
}

新知识

1、用高精乘算阶乘时，要对每一位都进行乘法操作，再对每一位进行进位

2、进位和加减乘除可以在一个循环里同时进行，不需要分开操作再遍历

3、高精度数的输出都是倒序输出去掉前导零，用一个标记即可轻松完成前导零的查找

4、由于是阶乘，记得要给第一位赋一个“1”，算式才能进行

5、数组的下标是从第二个元素开始，也即是“1”开始，还有分配空间的时候记得要多出一点

黑科技

在不支持PY的竞赛中，可以利用PY的一些特性来打表

比如这个题，可以直接用PY的高精度算出N <= 50的阶乘和，再一一打表