常州网站建设专业的公司_微网站_2345网址导航删除办法_青岛做网站推广

高精度算法

当我们需要处理很大的数时，我们就需要用到高精度算法计算加减乘除：

• 先用字符串读入，再用数组逆序存储
• 利用数组，模拟进行加减乘除运算过程。
  高精度算法本质上还是模拟算法，用代码模拟小学列竖式计算加减乘除的过程。

因此需要利用数组进行逆序存储——即从低位到高位存储并计算。

高精度加法

洛谷 P1601 A+B Problem（高精）

题目描述

高精度加法，相当于 a+b problem，不用考虑负数。

输入格式

分两行输入。$a,b\le 10^{500}$。

输出格式

输出只有一行，代表 $a+b$ 的值。

输入输出样例 #1

输入 #1

1
1

输出 #1

2

输入输出样例 #2

输入 #2

1001
9099

输出 #2

10100

说明/提示

$20\%$ 的测试数据，$0\le a,b\le 10^9$；

$40\%$ 的测试数据，$0\le a,b\le 10^{18}$。

代码实现

正如前文所述，本题就是模拟的竖式加法。

我们将数值读入并逆向存入数组后，数组的第 $0$ 位存储个位，第 $1$ 位存储十位，以此类推。

那我们就可以从个位开始模拟竖式加法的过程：

• 两数的对应位相加并加上原结果数组中的数（即之前所进的位），存入结果数组，若大于 $10$ 则继续向前进位，否则不进位。

我们还需要处理的是进位问题，即若最高位有进位，则需要在最高位前再插入一个 $1$，并且将结果数组的长度加 $1$。

#include <iostream>
#include <string>
using namespace std;const int N = 1e6 + 10;string str1,str2;
int a[N],b[N],c[N];
int la,lb,lc;void adds(int c[],int a[],int b[]){for(int i = 0;i < lc;i++){c[i] += (a[i] + b[i]);if(c[i] >= 10){             /* 也可以不进行判断，不存在进位就是加0 */c[i + 1] += c[i] / 10;c[i] %= 10;}}/* 处理最高位的进位 */if(c[lc])lc++;
}int main(){cin >> str1 >> str2;la = str1.size(),lb = str2.size(),lc = max(la,lb);for(int i = la - 1;i >= 0;i--)a[la - i - 1] = str1[i] - '0';for(int i = lb - 1;i >= 0;i--)b[lb - i - 1] = str2[i] - '0';adds(c,a,b);for(int i = lc - 1;i >= 0;i--)cout << c[i];return 0;
}

细节要点

• 逆序存储，从低位到高位存储，其中注意：存储的是数值，而不是字符，即需要减去 '0'。

• 加法运算完成后，需要判断最高位是否有进位，因为最多也只存在一个进位，所以只需要判断一次。

高精度减法

P2142 高精度减法

题目描述

高精度减法。

输入格式

两个整数 $a,b$（第二个可能比第一个大）。

输出格式

结果（是负数要输出负号）。

输入输出样例 #1

输入 #1

2
1

输出 #1

1

说明/提示

• $20\%$ 数据 $a,b$ 在 long long 范围内；
• $100\%$ 数据 $0<a,b\le 10^{10086}$。

代码实现

与加法类似，我们依然是模拟竖式减法的过程。

这里在代码构思阶段需要注意的：

• 为了避免出现负数，我们始终需要保证被减数大于减数，即 $a\ge b$。若 $a<b$，则交换 $a,b$并提前输出一个负号。

• 在定义最终结果的数组时，我们只需要定义一个长度为 $max(la,lb)$ 的数组即可，因为最终结果最多只有 $max(la,lb)$ 位，在最后再去掉前导 $0$即可。

#include <iostream>
using namespace std;const int N = 1e6 + 10;
int a[N],b[N],c[N];
int la,lb,lc;
string str1,str2;bool cmp(string a,string b){if(a.size() != b.size())return a.size() < b.size();return a < b;
}int main(){cin >> str1 >> str2;if(cmp(str1,str2)){swap(str1,str2);cout << "-";}la = str1.size(),lb = str2.size(),lc = max(la,lb);for(int i = la - 1;i >= 0;i--){a[la - i - 1] = str1[i] - '0';}for(int i = lb - 1;i >= 0;i--){b[lb - i - 1] = str2[i] - '0';}for(int i = 0;i < lc;i++){c[i] += a[i] - b[i];if(c[i] < 0){c[i + 1] -= 1;c[i] += 10;}}while(lc > 1 && c[lc - 1] == 0)lc--;for(int i = lc - 1;i >= 0;i--)cout << c[i];return 0;
}

细节要点

• 在比较两个字符串的大小时，我们只需要比较长度，若长度相等，则比较字符串本身。在交换两个字符串时，我们只需要交换字符串本身。

• 与加法不同，减法可能导致出现很多前导零，所以我们需要通过循环去掉前导零，同时需要保证至少有 $1$ 位数字。

高精度乘法

与前面的算法相同，我们依然是模拟竖式乘法的过程。但是我们还需要另外考虑一下进位的问题。

乘法较加法而言，其进位问题更加复杂，因为乘法运算中，每一位都需要考虑进位问题，在列竖式的过程中除了考虑当前位是否需要进位外，还需要考虑上一位的进位问题。所以我们选择在运算最后统一处理进位问题，而不是跟列竖式一样，每一位的运算都考虑进位问题。

P1303 A*B Problem

题目背景

高精度乘法模板题。

题目描述

给出两个非负整数，求它们的乘积。

输入格式

输入共两行，每行一个非负整数。

输出格式

输出一个非负整数表示乘积。

输入输出样例 #1

输入 #1

1 
2

输出 #1

2

说明/提示

每个非负整数不超过 $10^{2000}$。

#include <iostream>
#include <string>
using namespace std;const int N = 1e6 + 10;
string str1,str2;
int la,lb,lc;
int a[N],b[N],c[N];int main(){cin >> str1 >> str2;la = str1.size(),lb = str2.size(),lc = la + lb;for(int i = la - 1;i >= 0;i--){a[la - i - 1] = str1[i] - '0';}for(int i = lb - 1;i >= 0;i--){b[lb - i - 1] = str2[i] - '0';}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--;for(int i = lc - 1;i >= 0;i--)cout << c[i];return 0;
}

细节要点

• 在初始化结果数组时，我们需要定义一个长度为 $la+lb$ 的数组，因为最终结果最多只有 $la+lb$ 位，在最后再去掉前导 $0$即可。

高精度除法

还是和前面类似，高精度除法依旧是模拟列竖式计算的过程，不过思路跟前面略有不同。

我们首先需要考虑一个问题，即除法运算中，被除数和除数都是从高位到低位依次进行运算的，所以我们需要从高位到低位依次进行运算，同时需要考虑数位是否够除问题。

所以这里我们引入中间变量t作为“被除的数”，更新当前“被除的数”：t = t * 10 + a[i]，然后更新当前的商：c[i] = t / b，最后更新“被除的数”：t = t % b。这样，如果当前“被除的数”t大于等于除数b，那么我们就可以继续进行运算，否则说明当前位没有商，就会进入下一个循环执行t = t * 10 + a[i]，这也就是在竖式计算中找到够除的数位的过程。

P1480 A/B Problem

题目描述

输入两个整数 $a,b$，输出它们的商。

输入格式

两行，第一行是被除数，第二行是除数。

输出格式

一行，商的整数部分。

输入输出样例 #1

输入 #1

10
2

输出 #1

5

说明/提示

$0\le a\le 10^{5000}$，$1\le b\le 10^9$。

#include <iostream>
#include <string>
using namespace std;const int N = 1e6 + 10;
string str1;
int la,lc;
int a[N],b,c[N];
long long t;int main(){cin >> str1 >> b;la = str1.size(),lc = la;for(int i = la - 1;i >= 0;i--){a[la - i - 1] = str1[i] - '0';}for(int i = la - 1;i >= 0;i--){t = t * 10 + a[i];c[i] = t / b;t = t % b;}while(lc > 1 && c[lc - 1] == 0)lc--;for(int i = lc - 1;i >= 0;i--)cout << c[i];return 0;
}