算法-高精度问题(带图详细解读~)

今天来分享四道大数运算的模板题.

目录

• • 1. 大数相加
  • 2. 大数相减
  • 3. 大数相乘
  • 4. 大数相除

1. 大数相加

题目链接: LINK
基本思路: 存入数组, 模拟运算.

1. 逆序字符串
2. 补零操作
3. 依次取数据, 依次相加
   3-1 加: (t-ret = s1[i] + s2[i] + carry) % 10;
   3-2 进: (t-ret = s1[i] + s2[i] + carry) / 10;
4. 逆序, 返回结果

下面是图解过程:

参考代码:

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int a[N], b[N], c[N];
int la, lb, lc;

// ?精度加法的模版 - c = a + b;
void add(int c[], int a[], int b[])
{
	for (int i = 0; i < lc; i++)
	{
		c[i] += a[i] + b[i]; // 对应位相加，再加上进位
		c[i + 1] += c[i] / 10; // 处理进位
		c[i] %= 10; // 处理余数
	}

	if (c[lc]) lc++;
}

int main()
{
	string x, y; cin >> x >> y;

	// 1. 拆分每?位，逆序放在数组中
	la = x.size(); lb = y.size(); lc = max(la, lb);
	for (int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';
	for (int i = 0; i < lb; i++) b[lb - 1 - i] = y[i] - '0';

	// 2. 模拟加法的过程
	add(c, a, b); // c = a + b

	// 输出结果
	for (int i = lc - 1; i >= 0; i--) cout << c[i];

	return 0;
}

2. 大数相减

题目链接: LINK
基本思想: 区分大小, 大 - 小, 存入数组, 模拟运算.

参考代码:

#include<iostream>
#include<string>
#include<algorithm> 
using namespace std;

int main()
{
	// 读入字符串 
	string s1;
	string s2;
	cin >> s1 >> s2;
	string ret;
	
	// 判断大小, 保证s1比较大
	if ((s1.size() < s2.size()) || (s1.size() == s2.size() && s2 > s1)) 
	{
		swap(s1, s2);
		cout << '-';
	}
	
	// 逆序一下  
	reverse(s1.begin(), s1.end());
	reverse(s2.begin(), s2.end());
	
	// 补充0 
	while(s2.size() < s1.size()) s2 += '0';
	
	// 相减 
	int borrow = 0;
	for(int i = 0; i < s1.size(); i++) 
	{
		int x = s1[i] - '0' - borrow;
		int y = s2[i] - '0';
		int sum = x - y;
		//cout << "x: " << x << " y: " << y << " sum: " << sum << endl;
		if(sum < 0)
		{
			borrow = 1;
			sum = 10 + x - y;
			//cout << "x: " << x << " y: " << y << " sum: " << sum << endl;
		}
		else
		{
			borrow = 0;	
		} 
		
		ret += sum % 10 + '0';
	}
	//cout << ret << endl;
	for(int i = ret.size() - 1; i > 0; i--)
	{
		if(ret[i] == '0') ret.pop_back();
		else break;
	}
	
	reverse(ret.begin(), ret.end());
	cout << ret << endl;
	
	return 0;
}

3. 大数相乘

题目链接: LINK
基本思路: 放到数组里模拟实现.

参考代码:

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int a[N], b[N], c[N];
int la, lb, lc;

// ?精度乘法的模版 - c = a * b
void mul(int c[], int a[], int b[])
{
	// ?进位相乘,然后相加
	for (int i = 0; i < la; i++)
	{
		for (int j = 0; j < lb; j++)
		{
			c[i + j] += a[i] * b[j];
		}
	}

	// 处理进位
	for (int i = 0; i < lc; i++)
	{
		c[i + 1] += c[i] / 10;
		c[i] %= 10;
	}

	// 处理前导零
	while (lc > 1 && c[lc - 1] == 0) lc--;
}

int main()
{
	string x, y; cin >> x >> y;

	// 1. 拆分每?位，逆序放在数组中
	la = x.size(); lb = y.size(); lc = la + lb;
	for (int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';
	for (int i = 0; i < lb; i++) b[lb - 1 - i] = y[i] - '0';

	// 2. 模拟乘法的过程
	mul(c, a, b); // c = a * b

	// 输出结果
	for (int i = lc - 1; i >= 0; i--) cout << c[i];

	return 0;
}

4. 大数相除

题目链接: LINK
基本思路: 放到数组里模拟实现.

参考代码:

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
int a[N], b, c[N];
int la, lc;
// ⾼精度除法的模板 - c = a / b （⾼精度 / 低精度）
void sub(int c[], int a[], int b)
{
	LL t = 0; // 标记每次除完之后的余数
	for (int i = la - 1; i >= 0; i--)
	{
		// 计算当前的被除数
		t = t * 10 + a[i];
		c[i] = t / b;
		t %= b;
	}

	// 处理前导 0
	while (lc > 1 && c[lc - 1] == 0) lc--;
}

int main()
{
	string x; cin >> x >> b;
	la = x.size();

	for (int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';

	// 模拟除法的过程
	lc = la;
	sub(c, a, b); // c = a / b

	for (int i = lc - 1; i >= 0; i--) cout << c[i];


	return 0;
}

EOF.