一、概念
在我们进行计算的过程中，经常会遇到几十位，甚至几百位的数字的计算问题，也有可能会遇到小数点后几十位，几百位的情况，而我们面对这样的情况下， 和 的数据范围显然是不够使用的了。因此这时，我们就需要引入一个新的算法，叫做高精度算法。
高精度算法：它是处理大数字的数学计算方法，在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除等运算。
思想：高精度算法本质上是用字符串模拟数字进行计算，再利用类似于数学里的竖式的形式，一位一位进行相关计算 。
注意事项：
高精度加法：
- 倒叙输入，倒序输出，但中间是正着运算；
- 相加之后的进位处理；
高精度减法：
- 考虑结果出现的正情况；
- 前导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; }
运行结果如下：
五、乘法
大数乘法可以看成多个数大数乘以一位的数再相加
1.输入与初始化：
- 从用户那里接收两个字符串s1和s2，它们代表两个大整数。
- 将这两个字符串转换为数组a和b，使得数组中的元素是从低位到高位存储的整数。这是通过将字符串中的每个字符减去字符'0'的ASCII值来实现的，因为字符'0'到'9'的ASCII值是连续的。
- 初始化一个整数数组c，用于存储进位值。
- 初始化一个std::vector<int>（名为vec），用于存储最终的乘积结果。
2.计算乘积：
- 使用两层循环来计算
a和b中每个元素的乘积，并累加到vec中。- 外层循环遍历
a中的每个元素，内层循环遍历b中的每个元素。- 对于
a和b中的每对元素，计算它们的乘积，并加上之前的进位值（如果有的话）。- 将乘积的个位数加到
vec的对应位置，并更新进位值。
3.处理进位：
- 进位逻辑在内层循环结束后处理。如果最后一个乘法操作后存在进位，需要将其加到
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; }
