highPrecisionMultiply 关于那个注释是否添加
查看原帖
highPrecisionMultiply 关于那个注释是否添加
1344588
xiaozhongnuli楼主2024/5/4 18:24
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> highPrecisionAddition(vector<int>& a, vector<int>& b); //高精度加法
void highPrecisionMultiply(vector<int>& a, vector<int>& b, vector<int>& c); //高精度乘法
void factorial(vector<int>& a, int n); //阶乘
void found_array(vector<int>& a, int n);   //容器存储数字

int main()
{
	int n;
	cin >> n;
	vector<int> s;
	vector<int> a;
	vector<int> b;
	vector<int> c = {0};
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			found_array(s, 1);
		}
		else {
			found_array(a, 1);
			for (int j = 2; j < i + 2; j++) {
				found_array(b, j);
				highPrecisionMultiply(a, b, s);
				a = s;
				b.clear();
			}
		}
		c = highPrecisionAddition(s, c);
		s.clear();
		a.clear();
	}
	for (auto it = c.rbegin(); it != c.rend(); ++it) {
		cout << *it;
	}

	return 0;
}

vector<int> highPrecisionAddition(vector<int>& a, vector<int>& b)
{
	int alen = a.size();
	int blen = b.size();
	int len = max(alen, blen);
	vector<int> c;
	c.resize(len+1, 0);
	int i = 0;
	while (i < len) {
		if (a[i] + b[i] >= 10) {
			int d;
			c[i] += a[i] + b[i] - 10;
			++c[++i];
		}
		else {
			c[i] += a[i] + b[i];
			i++;
		}
	}
	while (c.size() > 1 && c.back() == 0)   c.pop_back();

	return c;
}

void highPrecisionMultiply(vector<int>& a, vector<int>& b, vector<int>& c)
{
	int alen = a.size();
	int blen = b.size();
//	c.clear();
	c.resize(alen * blen + 1, 0);
	
	for (int i=0; i<alen; i++)
		for (int j = 0; j < blen; j++) {
			if (a[i] * b[j] >= 10) {
				c[i + j] += (a[i] * b[j]) % 10;
				c[i + j + 1] += (a[i] * b[j]) / 10;
			}
			else {
				c[i + j] += a[i] * b[j];
			}
		}
	while (c.back() == 0 && c.size()>1)  c.pop_back();
}

void factorial(vector<int>& a, int n)
{
	int i = 1;
	vector<int> x;
	found_array(x,1);
	vector<int> y;
	while (i < n) {
		++i;
		found_array(y, i);
		highPrecisionMultiply(x, y, a);
		x = a;
		y.clear();
	}
}

void found_array(vector<int>& a, int n)
{
	a.clear();
	int num;
	while (n > 0) {
		num = n % 10;
		a.push_back(num);
		n /= 10;
	}
}
2024/5/4 18:24
加载中...