一、概念
在我们进行计算的过程中，经常会遇到几十位，甚至几百位的数字的计算问题，也有可能会遇到小数点后几十位，几百位的情况，而我们面对这样的情况下，
和
的数据范围显然是不够使用的了。因此这时，我们就需要引入一个新的算法，叫做高精度算法。
高精度算法：它是处理大数字的数学计算方法，在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除等运算。
思想：高精度算法本质上是用字符串模拟数字进行计算，再利用类似于数学里的竖式的形式，一位一位进行相关计算 。
注意事项：
高精度加法：
- 倒叙输入，倒序输出，但中间是正着运算；
- 相加之后的进位处理；
高精度减法：
- 考虑结果出现的正情况；
- 前导0的处理；
- 考虑减法的借位处理；
高精度乘法：
- 前导0的处理（0被相乘）；
- 可以将乘法单个位数相乘再转化成加法的思想；
- 此时题目中没有涉及到负数的情况。如出现负数，只需考虑两个字符串第一位是否为负号，然后结尾特殊判断一下即可；
高精度除法：（高精度÷低精度）
- 输入、计算、输出、需要同时逆序或同时正序；
- 前导0的处理；
- 不能考虑进位的情况
二、数据的处理
2.1 数据的存储
当输入的数很长时，可采用字符串方式输入，这样可输入位数很长的数，利用字符串函数和操作运算，将每一位取出，存入数组中 。
void init(int a[]) { // 传入数组
string s;
cin >> s;
len = s.length(); // s.length --> 计算字符串位数
for(int i=1; i<=len; i++)
a[i] = s[len -i] - '0'; //将字符串s转换为数组a, 倒序存储
}2.2 借位和进位
// 加法进位: c[i] = a[i] + b[i]
code: if(c[i] >= 10) {
c[i] %= 10;
++c[i++];
}
//减法借位: c[i] = a[i] - b[i]
code: if(a[i] < b[i]) {
--a[i+1];
a[i] += 10;
}
//乘法进位: c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];
x = c[i + j - 1] / 10;
c[i + j - 1] % 10;三、加法
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
int main()
{
char s1[500], s2[500];
int a[500] = { 0 }, b[500] = { 0 }, c[501] = { 0 };
int i = 0;
vector<int>vec_add;
cin >> s1 >>s2;
int len_s1 = strlen(s1);//求两个“数字”位数
int len_s2 = strlen(s2);
for (i = 0;i < len_s1;i++)
{
a[i] = s1[len_s1 - i - 1] - '0';//倒叙存储，方便最高位进位，按字符型输入，按整型的方式存储在数组里面
}
for (i = 0;i < len_s2;i++)
{
b[i] = s2[len_s2 - i - 1] - '0';
}
for (i = 0;i < (len_s1 > len_s2 ? len_s1 : len_s2);i++)
{
vec_add.push_back(a[i] + b[i] + c[i]);
if (vec_add[i] >= 10)//如果可以进位
{
c[i + 1] = vec_add[i] / 10;
vec_add[i] %= 10;
if (i == (len_s1 > len_s2 ? len_s1 : len_s2))
{
vec_add.push_back(1);
}
}
}
int len_vec_add = vec_add.size();
for (i = len_vec_add - 1;i >= 0;i--)
{
cout << vec_add[i];
}
cout << endl;
return 0;
}运行示例如下：
四、减法
#include<iostream>
#include<cstring>
#include<vector>
int main()
{
char s1[500], s2[500];
int a[500] = { 0 }, b[500] = { 0 }, c[501] = { 0 };
int i = 0;
vector<int>vec;
cin >> s1 >> s2;
int len_s1 = strlen(s1);//求两个“数字”位数
int len_s2 = strlen(s2);
for (i = 0;i < len_s1;i++)
{
a[i] = s1[len_s1 - i - 1] - '0';//倒叙存储，方便最高位进位，按字符型输入，按整型的方式存储在数组里面
}
for (i = 0;i < len_s2;i++)
{
b[i] = s2[len_s2 - i - 1] - '0';
}
for (i = 0;i < (len_s1 > len_s2 ? len_s1 : len_s2);i++)
{
if (strcmp(s1, s2) >= 0)
{
vec.push_back(a[i] - b[i]);
if (vec[i] < 0)
{
a[i + 1] -= 1;
a[i] += 10;
vec[i] += 10;
}
}
else
{
vec.push_back(b[i] - a[i]);
if (vec[i] < 0)
{
b[i + 1] -= 1;
b[i] += 10;
vec[i] += 10;
}
}
}
int len_vec = vec.size();
if (strcmp(s1, s2) >= 0)
{
for (i = len_vec - 1;i >= 0;i--)
{
cout << vec[i];
}
}
else
{
cout << "-";
for (i = len_vec - 1;i >= 0;i--)
{
cout << vec[i];
}
}
cout << endl;
return 0;
}运行结果如下：
五、乘法
大数乘法可以看成多个数大数乘以一位的数再相加
- 输入与初始化：
- 从用户那里接收两个字符串
s1和s2，它们代表两个大整数。- 将这两个字符串转换为数组
a和b，使得数组中的元素是从低位到高位存储的整数。这是通过将字符串中的每个字符减去字符'0'的ASCII值来实现的，因为字符'0'到'9'的ASCII值是连续的。- 初始化一个整数数组
c，用于存储进位值。- 初始化一个
std::vector<int>（名为vec），用于存储最终的乘积结果。- 计算乘积：
- 使用两层循环来计算
a和b中每个元素的乘积，并累加到vec中。- 外层循环遍历
a中的每个元素，内层循环遍历b中的每个元素。- 对于
a和b中的每对元素，计算它们的乘积，并加上之前的进位值（如果有的话）。- 将乘积的个位数加到
vec的对应位置，并更新进位值。- 处理进位：
- 进位逻辑在内层循环结束后处理。如果最后一个乘法操作后存在进位，需要将其加到
vec的下一个位置。- 需要注意，由于
vec的大小在循环过程中是变化的，因此直接通过索引访问vec可能会导致越界错误。正确的做法是在需要添加新元素时，使用vec.push_back()。
代码示例如下：
int main()
{
char s1[500], s2[500];
int a[500] = { 0 }, b[500] = { 0 };
int i = 0;
int z = 0;
vector<int>vec;
cin >> s1 >> s2;
int len_s1 = strlen(s1);//求两个“数字”位数
int len_s2 = strlen(s2);
//初始化vec的大小至少为len_s1 + len_s2，这样可以保证在计算过程中不会越界。
vec.resize(len_s1 + len_s2, 0);
for (i = 0;i < len_s1;i++)
{
a[i] = s1[len_s1 - i - 1] - '0';//倒叙存储，方便最高位进位，按字符型输入，按整型的方式存储在数组里面
}
for (i = 0;i < len_s2;i++)
{
b[i] = s2[len_s2 - i - 1] - '0';
}
for (i = 0; i < len_s1; i++)
{
int carry = 0; // 每次循环开始时，进位为0
for (int j = 0; j < len_s2; j++)
{
// 计算乘积，加上已有的值和进位
int product = a[i] * b[j] + vec[i + j] + carry;
vec[i + j] = product % 10; // 取个位数
carry = product / 10; // 更新进位
}
// 检查最后一个乘法操作后的进位
if (carry > 0)
{
vec[i + len_s2] += carry;
}
}
// 处理vec中可能的前导0
while (!vec[vec.size() - 1])
{
if (vec[vec.size() - 1] == 0)
{
vec.pop_back();
}
}
int len_vec = vec.size();
for (i = len_vec - 1;i >= 0;i--)
{
cout << vec[i];
}
cout << endl;
return 0;
}测试输出结果如下：
六、除法
高精度除以低精度：
思路：
除法时，每一次的商值都在 0~9 之间，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避免高精度乘法，用 0~9 次循环减法取代得到商的值。采用按位相除法。
#include<iostream>
int main()
{
char n1[100];
int a[100] = { 0 }, c[100] = { 0 }, i, x = 0, b;
cin >> n1 >> b;
int len_a = strlen(n1);
for (i = 1; i <= len_a; i++)
{
a[i] = n1[i - 1] - '0'; //除法不需要逆序存放
}
for (i = 1; i <= len_a; i++)
{
c[i] = (a[i] + x * 10) / b; // 算上上一位剩下的继续除
x = (a[i] + 10 * x) % b; // 求余
}
int len_c = 1;
while (c[len_c] == 0 && len_c < len_a)
{
len_c++;
}
for (i = len_c; i < len_a; i++)
{
cout << c[i];
}
return 0;
}