进阶数据结构——高精度运算
目录
- 前言
- 一、高精度运算的定义与背景
- 二、高精度运算的实现方式
- 三、高精度运算的算法实现
- 四、高精度运算的应用场景
- 五、代码模版（c++）
- 六、经典例题
- 1.[高精度加法](https://www.lanqiao.cn/problems/1516/learning/?page=1&first_category_id=1&name=%E9%AB%98%E7%B2%BE%E5%BA%A6%E5%8A%A0%E6%B3%95)
- 3.[高精度减法](https://www.luogu.com.cn/problem/P2142)
- 3.[高精度乘法](https://www.lanqiao.cn/problems/1515/learning/?page=1&first_category_id=1&name=%E9%98%B6%E4%B9%98%E8%AE%A1%E7%AE%97)
- 4.[高精度除法](https://www.luogu.com.cn/problem/P1480)
- 七、总结
- 结语
前言
从这期开始我们就开始进入进阶数据结构的学习了。进阶数据结构中的高精度运算分析，主要聚焦于如何在计算机编程中有效处理超出常规数据类型表示范围的极大或极精确数值。
一、高精度运算的定义与背景
高精度运算是指在计算机编程中，对超出常规数据类型（如整型、浮点型）所能表示范围的极大或极精确数值进行的各种数学运算。在标准的计算机编程语言中，内置的整数和浮点数类型有其固定的字节数和精度限制，一旦数字过大或精度过高，就会导致溢出或精度丢失的问题。因此，高精度运算技术应运而生。
二、高精度运算的实现方式
高精度运算的实现方式通常涉及自定义数据结构来存储极大数值的每一位。这些数据结构能够模拟人类手算时多位数列的运算规则，使得在理论上能够处理任意长度和精度的数字。常见的实现方式包括：
数组：数组是最常用的数据结构之一，在高精度运算中，可以使用数组来存储每一位数字。例如，在C++中，可以使用std::vector或std::deque等动态数组来分别存储每一位数字。这种方式的好处是访问和修改数字的各个位非常方便，且能够处理任意长度的数字。
字符串：在某些情况下，也可以使用字符串来表示高精度数。字符串的好处是能够直接输入和输出，且不需要考虑数字的位数和进位问题。但是，字符串中的每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算，这增加了运算的复杂性。
三、高精度运算的算法实现
高精度运算的算法实现包括加、减、乘、除等基本运算。以下是对这些运算的简要分析：
加法：高精度加法的基本思想是将两个加数和被加数数组从第一位开始对其，并从第一位开始向后遍历，每一位相加并判断进位，直至到达输入数据末端为止。最后，如果最高位有进位，则需要添加一位。
减法：高精度减法与加法类似，但需要注意处理借位问题。当被减数小于减数时，需要向前一位借位。借位的过程可以通过在该位加上10并减去下一位的值来实现。同时，需要注意处理结果的符号和前导零。
乘法：高精度乘法的基本思想是两个数组相对应位置的数字相乘并考虑进位。可以使用双重循环来遍历两个数组的每一位，并将乘积累加到结果数组中。最后，需要处理进位问题。
除法：高精度除法相对复杂，通常使用长除法或更高效的算法如Karatsuba算法等来实现。除法的关键是逐位确定商的值，并通过减法来确定余数。由于除法运算的复杂性，实现时需要注意处理各种边界情况和异常情况。
四、高精度运算的应用场景
高精度运算在许多领域都有广泛的应用场景，包括但不限于：
科学计算：在科学计算中，经常需要处理小数点后几百位甚至更多的数字，高精度运算能够提供必要的精度和范围支持。
金融计算：在金融领域，高精度运算用于处理大额货币交易和精确计算利息等金融指标。
密码学：在密码学中，高精度运算用于实现加密算法和生成大素数等安全操作。
计算机图形学：在计算机图形学中，高精度运算用于处理浮点数运算中的精度丢失问题，以确保图形的精确渲染。
五、代码模版（c++）
六、经典例题
1.高精度加法
蓝色字体点进去看原题
蓝色字体点进去看原题
蓝色字体点进去看原题
#include<iostream>
#include<cstring>
using namespace std;
const int Base = 1000; //进制数
const int Capacity = 100; //数组容量
class BigInt {
private:
int m_size;
int m_data[Capacity];
void removeLendingZero(); //去除前导0
public:
BigInt(int v);
BigInt();
BigInt(char s[]); //将数字字符串存入数据
void print(char end);
BigInt(const BigInt& bi);
BigInt& operator=(const BigInt& bi);
int compare(const BigInt& bi);
BigInt operator+(const BigInt& bi);
BigInt operator-(const BigInt& bi);
BigInt operator*(const BigInt& bi);
BigInt operator/(const BigInt& bi);
};
BigInt::BigInt() {
m_size = 0;
memset(m_data, 0, sizeof(m_data));
}
BigInt::BigInt(int v) {
m_size = 0;
while (v > 0) {
m_data[m_size++] = v % Base;
v /= Base;
}
}
BigInt::BigInt(char s[]) {
m_size = 0;
int b = 1;
memset(m_data, 0, sizeof(m_data));
for (int i = strlen(s) - 1; i >= 0; i--) {
m_data[m_size] += (s[i] - '0') * b;
b *= 10;
if (b >= Base) {
b = 1;
m_size++;
m_data[m_size] = 0;
}
}
if (m_data[m_size] > 0) m_size++;
removeLendingZero();
}
BigInt::BigInt(const BigInt& bi) {
m_size = bi.m_size;
memcpy(m_data, bi.m_data, sizeof(bi.m_data));
}
BigInt& BigInt::operator=(const BigInt& bi) {
m_size = bi.m_size;
memcpy(m_data, bi.m_data, sizeof(m_data));
return *this;
}
void BigInt::print(char end) {
cout << (m_size == 0 ? 0 : m_data[m_size - 1]);
for (int i = m_size - 2; i >= 0; i--) {
for (int j = Base / 10; j > 0; j /= 10) {
cout << (m_data[i] / j) % 10;
}
}
cout << end;
}
void BigInt::removeLendingZero() {
while (m_size > 0 && m_data[m_size - 1] == 0) {
m_size--;
}
}
int BigInt::compare(const BigInt& bi) {
if (m_size != bi.m_size)return m_size > bi.m_size ? 1 : -1;
for (int i = m_size - 1; i >= 0; i--) {
if (m_data[i] != bi.m_data[i]) return m_data[i] > bi.m_data[i] ? 1 : -1;
}
return 0;
}
BigInt BigInt::operator+(const BigInt& bi) {
BigInt ret;
int carry = 0, i;
for (i = 0; i < bi.m_size || i < m_size || carry > 0 ; i++) {
/*if (i < m_size)*/carry += m_data[i];
/*if (i < bi.m_size)*/carry += bi.m_data[i];
ret.m_data[i] = carry % Base;
carry /= Base;
}
ret.m_size = i; //注意此时ret的长度就是为i
return ret;
}
int main() {
char s1[1000], s2[1000];
while (cin >> s1 >> s2) {
BigInt a(s1), b(s2);
(a + b).print('\n');
}
return 0;
}
3.高精度减法
这一题你们要注意范围长度，还要处理负数的情况
#include<iostream>
#include<cstring>
using namespace std;
const int Base = 1000; //进制数
const int Capacity = 10086 / 3 + 1; //数组容量
class BigInt {
private:
int m_size;
int m_data[Capacity];
void removeLendingZero(); //去除前导0
public:
BigInt(int v);
BigInt();
BigInt(char s[]); //将数字字符串存入数据
void print(char end);
BigInt(const BigInt& bi);
BigInt& operator=(const BigInt& bi);
int compare(const BigInt& bi);
BigInt operator+(const BigInt& bi);
BigInt operator-(const BigInt& bi);
BigInt operator*(const BigInt& bi);
BigInt operator/(const BigInt& bi);
};
BigInt::BigInt() {
m_size = 0;
memset(m_data, 0, sizeof(m_data));
}
BigInt::BigInt(int v) {
m_size = 0;
while (v > 0) {
m_data[m_size++] = v % Base;
v /= Base;
}
}
BigInt::BigInt(char s[]) {
m_size = 0;
int b = 1;
memset(m_data, 0, sizeof(m_data));
for (int i = strlen(s) - 1; i >= 0; i--) {
m_data[m_size] += (s[i] - '0') * b;
b *= 10;
if (b >= Base) {
b = 1;
m_size++;
m_data[m_size] = 0;
}
}
if (m_data[m_size] > 0) m_size++;
removeLendingZero();
}
BigInt::BigInt(const BigInt& bi) {
m_size = bi.m_size;
memcpy(m_data, bi.m_data, sizeof(bi.m_data));
}
BigInt& BigInt::operator=(const BigInt& bi) {
m_size = bi.m_size;
memcpy(m_data, bi.m_data, sizeof(m_data));
return *this;
}
void BigInt::print(char end) {
cout << (m_size == 0 ? 0 : m_data[m_size - 1]);
for (int i = m_size - 2; i >= 0; i--) {
for (int j = Base / 10; j > 0; j /= 10) {
cout << (m_data[i] / j) % 10;
}
}
cout << end;
}
void BigInt::removeLendingZero() {
while (m_size > 0 && m_data[m_size - 1] == 0) {
m_size--;
}
}
int BigInt::compare(const BigInt& bi) {
if (m_size != bi.m_size)return m_size > bi.m_size ? 1 : -1;
for (int i = m_size - 1; i >= 0; i--) {
if (m_data[i] != bi.m_data[i]) return m_data[i] > bi.m_data[i] ? 1 : -1;
}
return 0;
}
BigInt BigInt::operator+(const BigInt& bi) {
BigInt ret;
int carry = 0, i;
for (i = 0; i < bi.m_size || i < m_size || carry > 0 ; i++) {
/*if (i < m_size)*/carry += m_data[i];
/*if (i < bi.m_size)*/carry += bi.m_data[i];
ret.m_data[i] = carry % Base;
carry /= Base;
}
ret.m_size = i; //注意此时ret的长度就是为i
return ret;
}
BigInt BigInt::operator-(const BigInt& bi) {
BigInt ret;
int carry = 0;
ret.m_size = m_size;
for (int i = 0; i < m_size; i++) {
ret.m_data[i] = m_data[i] - carry;
if (i < bi.m_size) ret.m_data[i] -= bi.m_data[i]; //一定是判断减数的每一位减完了没有，如果没有结果值为乱数
if (ret.m_data[i] < 0) {
ret.m_data[i] += Base;
carry = 1;
}
else carry = 0; //注意carry一定要重新赋值为0,不然到下一位的时候carry的值就被污染了
}
ret.removeLendingZero();
return ret;
}
int main() {
char s1[100087], s2[100087];
while (cin >> s1 >> s2) {
BigInt a(s1), b(s2);
if (a.compare(b) >= 0) (a - b).print('\n');
else {
cout << "-";
(b - a).print('\n');
}
}
return 0;
}
3.高精度乘法
#include<iostream>
#include<cstring>
using namespace std;
const int Base = 1000; //进制数
const int Capacity = 1000; //数组容量
class BigInt {
private:
int m_size;
int m_data[Capacity];
void removeLendingZero(); //去除前导0
public:
BigInt(int v);
BigInt();
BigInt(char s[]); //将数字字符串存入数据
void print(char end);
BigInt(const BigInt& bi);
BigInt& operator=(const BigInt& bi);
int compare(const BigInt& bi);
BigInt operator+(const BigInt& bi) const;
BigInt operator-(const BigInt& bi) const;
BigInt operator*(const BigInt& bi) const;
BigInt operator/(const BigInt& bi) const;
};
BigInt::BigInt() {
m_size = 0;
memset(m_data, 0, sizeof(m_data));
}
BigInt::BigInt(int v) {
m_size = 0;
while (v > 0) {
m_data[m_size++] = v % Base;
v /= Base;
}
}
BigInt::BigInt(char s[]) {
m_size = 0;
int b = 1;
memset(m_data, 0, sizeof(m_data));
for (int i = strlen(s) - 1; i >= 0; i--) {
m_data[m_size] += (s[i] - '0') * b;
b *= 10;
if (b >= Base) {
b = 1;
m_size++;
m_data[m_size] = 0;
}
}
if (m_data[m_size] > 0) m_size++;
removeLendingZero();
}
BigInt::BigInt(const BigInt& bi) {
m_size = bi.m_size;
memcpy(m_data, bi.m_data, sizeof(bi.m_data));
}
BigInt& BigInt::operator=(const BigInt& bi) {
m_size = bi.m_size;
memcpy(m_data, bi.m_data, sizeof(m_data));
return *this;
}
void BigInt::print(char end) {
cout << (m_size == 0 ? 0 : m_data[m_size - 1]);
for (int i = m_size - 2; i >= 0; i--) {
for (int j = Base / 10; j > 0; j /= 10) {
cout << (m_data[i] / j) % 10;
}
}
cout << end;
}
void BigInt::removeLendingZero() {
while (m_size > 0 && m_data[m_size - 1] == 0) {
m_size--;
}
}
int BigInt::compare(const BigInt& bi) {
if (m_size != bi.m_size)return m_size > bi.m_size ? 1 : -1;
for (int i = m_size - 1; i >= 0; i--) {
if (m_data[i] != bi.m_data[i]) return m_data[i] > bi.m_data[i] ? 1 : -1;
}
return 0;
}
BigInt BigInt::operator+(const BigInt& bi) const {
BigInt ret;
int carry = 0, i;
for (i = 0; i < bi.m_size || i < m_size || carry > 0 ; i++) {
if (i < m_size)carry += m_data[i];
if (i < bi.m_size)carry += bi.m_data[i];
ret.m_data[i] = carry % Base;
carry /= Base;
}
ret.m_size = i; //注意此时ret的长度就是为i
return ret;
}
BigInt BigInt::operator-(const BigInt& bi) const {
BigInt ret;
int carry = 0;
ret.m_size = m_size;
for (int i = 0; i < m_size; i++) {
ret.m_data[i] = m_data[i] - carry;
if (i < bi.m_size) ret.m_data[i] -= bi.m_data[i]; //一定是判断减数的每一位减完了没有，如果没有结果值为乱数
if (ret.m_data[i] < 0) {
ret.m_data[i] += Base;
carry = 1;
}
else carry = 0; //注意carry一定要重新赋值为0,不然到下一位的时候carry的值就被污染了
}
ret.removeLendingZero();
return ret;
}
BigInt BigInt:: operator*(const BigInt& bi) const {
BigInt ret;
ret.m_size = m_size + bi.m_size;
for (int i = 0; i < ret.m_size; i++) {
ret.m_data[i] = 0;
}
for (int i = 0; i < m_size; i++) {
int carry = 0;
for (int j = 0; j < bi.m_size; j++) {
ret.m_data[i + j] += m_data[i] * bi.m_data[j] + carry;
if (ret.m_data[i + j] >= Base) {
carry = ret.m_data[i + j] / Base;
ret.m_data[i + j] %= Base;
}
else carry = 0;
}
ret.m_data[i + bi.m_size] += carry;
}
ret.removeLendingZero();
return ret;
}
int main() {
int n;
while (cin >> n) {
BigInt ret(1);
for (int i = 2; i <= n; i++) {
ret = ret * i;
}
ret.print('\n');
}
return 0;
}
4.高精度除法
#include<iostream>
#include<cstring>
using namespace std;
const int Base = 1000;
const int Capacity = 10000;
class BigInt {
private:
int m_data[Capacity];
int m_size;
void removeLeadingZeros();
public:
BigInt();
BigInt(int v);
BigInt(const BigInt& bi);
BigInt(char s[]);
BigInt& operator=(const BigInt& bi);
void print(char end);
int compare(const BigInt& bi);
BigInt operator+(const BigInt& bi) const;
BigInt operator-(const BigInt& bi) const;
BigInt operator*(const BigInt& bi) const;
BigInt operator/(const BigInt& bi) const;
};
BigInt::BigInt(int v) {
m_size = 0;
while(v > 0) {
m_data[m_size++] = v % Base;
v /= Base;
}
}
BigInt::BigInt() :m_size(0) {
memset(m_data, 0, sizeof(m_data));
}
BigInt::BigInt(const BigInt& bi) :m_size(bi.m_size) {
memcpy(m_data, bi.m_data, sizeof(bi.m_data));
}
BigInt::BigInt(char s[]) {
m_size = 0;
m_data[m_size] = 0;
int b = 1;
for (int i = strlen(s) - 1; i >= 0; i--) {
m_data[m_size] += (s[i] - '0') * b;
b *= 10;
if (b >= Base) {
m_size++;
b = 1;
m_data[m_size] = 0;
}
}
if (m_data[m_size] > 0) { //注意m_size可能会比原来多所以要判断
m_size++;
}
removeLeadingZeros();
}
BigInt& BigInt::operator=(const BigInt& bi) {
m_size = bi.m_size;
memcpy(m_data, bi.m_data, sizeof(m_data));
return *this;
}
void BigInt::print(char end) {
cout << (m_size == 0 ? 0 : m_data[m_size - 1]);
for (int i = m_size - 2; i >= 0; i--) {
for (int j = Base / 10; j > 0; j/=10) {
cout << (m_data[i] / j) % 10;
}
}
cout << end;
}
int BigInt::compare(const BigInt& bi) {
if (m_size != bi.m_size) {
return m_size > bi.m_size ? 1 : -1;
}
for (int i = m_size - 1; i >= 0; i--) {
if (m_data[i] != bi.m_data[i])return m_data[i] > bi.m_data[i] ? 1 : -1;
}
return 0;
}
void BigInt::removeLeadingZeros() {
while (m_size > 0 && m_data[m_size - 1] == 0) {
m_size--;
}
}
BigInt BigInt::operator+(const BigInt& bi) const {
BigInt ret;
int i = 0, carry = 0;
for (; i < m_size || i < bi.m_size || carry > 0; i++) {
if (i < m_size) carry += m_data[i];
if (i < bi.m_size) carry += bi.m_data[i];
ret.m_data[i] = carry % Base;
carry /= Base;
}
ret.m_size = i;
return ret;
}
BigInt BigInt::operator-(const BigInt& bi) const {
BigInt ret;
int carry = 0;
ret.m_size = m_size; //被减数赋值给ret
for (int i = 0; i < ret.m_size; i++) {
ret.m_data[i] = m_data[i] - carry;
if (i < bi.m_size) ret.m_data[i] -= bi.m_data[i];
if (ret.m_data[i] < 0) {
carry = 1;
ret.m_data[i] += Base;
}
else {
carry = 0;
}
}
ret.removeLeadingZeros();
return ret;
}
BigInt BigInt::operator*(const BigInt& bi) const {
BigInt ret;
ret.m_size = m_size + bi.m_size;
for (int i = 0; i < ret.m_size; i++) {
ret.m_data[i] = 0;
}
for (int i = 0; i < m_size; i++) {
int carry = 0;
for (int j = 0; j < bi.m_size; j++) {
ret.m_data[i + j] += m_data[i] * bi.m_data[j] + carry;
if (ret.m_data[i + j] >= Base) {
carry = ret.m_data[i + j] / Base;
ret.m_data[i + j] %= Base;
}
else {
carry = 0;
}
}
ret.m_data[i + bi.m_size] += carry;
}
ret.removeLeadingZeros();
return ret;
}
BigInt BigInt::operator/(const BigInt& bi) const {
BigInt ret, carry = 0;
int l , r , mid;
for (int i = m_size - 1; i >= 0; i--) {
carry = carry * Base + m_data[i];
l = -1;
r = Base;
while (l + 1 < r) {
mid = (l + r) / 2;
if ((bi * mid).compare(carry) <= 0) {
l = mid;
}
else r = mid;
}
ret.m_data[i] = l;
carry = carry - bi * l;
}
ret.m_size = m_size;
ret.removeLeadingZeros();
return ret;
}
int main() {
char s1[10000], s2[10000];
while (cin >> s1 >> s2) {
BigInt a(s1), b(s2);
if (a.compare(b) >= 0)(a - b).print('\n');
else {
cout << '-';
(b - a).print('\n');
}
}
return 0;
}
七、总结
高精度运算是一种重要的进阶数据结构技术，它能够处理超出常规数据类型表示范围的极大或极精确数值。通过自定义数据结构（如数组或字符串）和专门的算法实现（如加法、减法、乘法和除法），高精度运算能够在许多领域提供必要的精度和范围支持。掌握高精度运算技术对于提高程序的性能和效率具有重要意义。
结语
当前进阶的数据结构比之前学的初级数据结构要复杂了，希望大家一定要动手敲一遍代码，敲完之后提交到例题里检查一下是否正确，出现bug不用慌张，耐心差错，这样你的水平才能提升。
希望大家可以一键三连，后续我们一起学习，谢谢大家！！！
