高精度算法
高精度的基本概念
概念： 高精度就是我们使用数组与字符串结合来表示大数字的方法。
原因： 在c++里面，每个变量都有其数据范围。
int 类型二进制位为32位，上线约为正负21亿。long 类型在不同操作系统不太一样，在windows系统为32位，也是正负21亿，但一般不使用。long long类型存较大的数字，二进制位为64位，上限为19位数字。
可见不是所有的数字都能存下来，一旦我们的数字超过了19位数，就爆掉了，会报各种乱起八糟的错，因此我们在使用数字运算前要对数字大小进行一个预估，然后使用合适的数字类型。
引入
以一道例子来引入： 请计算一下100！有多大，
答案： 约为9 * 10^157
这么大的数字根本不可能用常规的数据类型来实现，这时我们就能用高精度代码来实现。
一下为演示代码，只作为引入，并没有题解。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<bits/stdc++.h>
using namespace std;
int a[10020],b[10020],c[10020];
string mul="1";
string multi(string x,int y)
{
memset(a,0,sizeof(a));
string res="";
int lena=x.size(),lenc=lena+5;
for(int i=0;i<lena;i++) a[i]=x[lena-1-i]-'0';
for(int i=0;i<lenc;i++) c[i]=a[i]*y;
if(c[lenc]==0) lenc--;
for(int i=0;i<lenc;i++){
while(c[i]>=10){
c[i+1]+=c[i]/10;
c[i]%=10;
}
}
while(c[lenc]==0&&lenc>0) lenc--;
for(int i=lenc;i>=0;i--)
res+=c[i]+'0';
return res;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
mul=multi(mul,i);
}
cout<<sum<<endl;
return 0;
}
|
这是一段高精度成低精度的典型例子，求阶乘。
详细教程
高精度加法：
流程：
- 首先我们要处理输入问题，高精度的数字一般较大，无法用正常的变量接收，这是我们可以用可无限扩展的字符串来接收。
- 但是字符串不好处理，因此第二步我们用数组来存储数字（用vector也是可以的，道理是一样的，下面只演示静态数组），将两个待相加的数字都存起来，分别为A，B。
- 处理相加的过程，定义数组C，用来存我们相加的结果。
- 相加完处理进位问题。
- 最后输出结果。
代码演示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
int main() {
int a[2000] = {0}, b[2000] = {0}, c[4000] = {0};
string num1, num2;
cin >> num1 >> num2;
int len1 = num1.size();
int len2 = num2.size();
for (int i = len1 - 1, j = 0; i >= 0; i--, j++) {
a[j] = num1[i] - '0';
}
for (int i = len2 - 1, j = 0; i >= 0; i--, j++) {
b[j] = num2[i] - '0';
}
for (int i = 0; i < maxLen; i++) {
if (c[i] >= 10) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
}
int highIndex = maxLen;
while (highIndex > 0 && c[highIndex] == 0) {
highIndex--;
}
for (int i = highIndex; i >= 0; i--) {
cout << c[i];
}
return 0;
}
|
高精度减法：
流程：
- 输入输出与高精度加法相同，后面不过多赘述。
- 高精度加法的实现与我们的常见的减法竖式运算相同
- 在这个算式里面，我们从低位开始减，不够向高位借1，然后高位开始减，以此类推。
- 用C数组来存我们的数字。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| #include<bits/stdc++.h>
using namespace std;
int main(){
4string num1;
4string num2;
4cin>>num1>>num2;
4int a[5005]={0};
4int b[5005]={0};
4int c[5005]={0};
4a[0]=num1.size();
4b[0]=num2.size();
4c[0]=a[0];
4for(int i=1;i<=a[0];i++) a[i]=num1[a[0]-i]-'0';
4for(int i=1;i<=b[0];i++) b[i]=num2[b[0]-i]-'0';
4for(int i=1;i<=a[0];i++){
44if(a[i]<b[i]){
444a[i]+=10;
444a[i+1]--;
44}
44c[i]=a[i]-b[i];
4}
4while(c[c[0]]==0) c[0]--;
4for(int i=c[0];i>=1;i--) cout<<c[i];
4return 0;
}
|
高精度乘法：
流程：
- 我们高精度乘法有两种思路，我建议使用类似贡献的思路，原理如下：
1
2
3
4
5
6
7
8
9
| 18 18
19 19
----- -----
162 ---》 72
18 9
----- 8
342 1
-----
342
|
- 首先我们将这个乘法里面每个数字都单独和上面的数字相乘，得到下面的四个数字，但是乘的结果是不一样的，有的数字位数天生就比别的位数高。
- 如果我们把个位看成1，那么第
i位数字乘第j位数字得到结果就要加在第i+j-1上面。
- 这是个很容易发现的规律，没发现可以直接套用结论，不影响。
- 如果我们把个位看成0，结果就要加在第
i+j上面
代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<bits/stdc++.h>
using namespace std;
int main(){
4string num1,num2;
4cin>>num1>>num2;
4int a[5005];
4int b[5005];
4int c[10010];
4a[0]=num1.size();
4b[0]=num2.size();
4c[0]=a[0]+b[0];
4for(int i=1;i<=a[0];i++) a[i]=num1[a[0]-i]-'0';
4for(int i=1;i<=b[0];i++) b[i]=num2[b[0]-i]-'0';
4for(int i=1;i<=a[0];i++){
44for(int j=1;j<=b[0];j++) c[i+j-1]+=a[i]*b[j];
4}
4for(int i=1;i<=c[0];i++){
44if(c[i]>=10){
444c[i+1]+=c[i]/10;
444c[i]%=10;
44}
4}
4while(c[0]>0&&c[c[0]]==0) c[0]--;
4if(c[0]==0) cout<<0;
4for(int i=c[0];i>=1;i--) cout<<c[i];
4return 0;
}
|
低精度除法（多位小数）：
流程：
- 低精度除法主要用于求多位小数，因为小数类型也是具有上限的，double也最多存15到16位数字，因此我们如果想求17位以上的小数就要用低精度除法。
- 我们用了除法的原理，每当除一个数后，结果等于整除的结果，留下的数为取余后的结果。
- 之后下一轮除法中，我们继续进行同样的操作，即可完成求多位小数。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| #include<bits/stdc++.h>
using namespace std;
int main(){
4int num1,num2;
4cin>>num1>>num2;
4int num=num1/num2;
4int t=num1%num2;
4int n;
4cin>>n;
4cout<<num<<".";
4while(n){
44n--;
44t*=10;
44int ans=t/num2;
44cout<<ans;
44t%=num2;
4}
4return 0;
}
|
高精度除法：
流程：
- 高精度除法我们的思路与正常的除法思路大致相同，难点在于我们该怎么用代码实现。
- 首先我们要先把两个数存起来，之后在定义一个数组来存数字。
- 之后根据两个数：被除数和除数，现将两个数对齐，之后将被除数减去除数，然后将我们答案对于数字加一，如果还大，继续加一，直到对应位置小于除数。
- 随后除数整体往后移动一位。
代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include<bits/stdc++.h>
using namespace std;
void subs(int x[],int y[]){
4for(int i=x[0];i>=1;i--){
44if(x[i]<y[i]){
444x[i]=x[i]+10;
444x[i-1]=x[i-1]-1;
44}
44x[i]-=y[i];
4}
}
bool comp(int x[],int y[]){
4for(int i=1;i<=x[0];i++){
44if(x[i]>y[i]) return true;
44if(x[i]<y[i]) return false;
4}
4return true;
}
void cpy(int x[],int y[],int offset){
4for(int i=1;i<=x[0];i++){
44y[i+offset]=x[i];
4}
4y[0]=x[0]+offset;
}
int main(){
4string num1;
4string num2;
4cin>>num1>>num2;
4int a[5005];
4int b[5005];
4int c[5005];
4a[0]=num1.size();
4b[0]=num2.size();
4c[0]=a[0]-b[0]+1;
4for(int i=1;i<=a[0];i++) a[i]=num1[i-1]-'0';
4for(int i=1;i<=b[0];i++) b[i]=num2[i-1]-'0';
4int t[10002];
4for(int i=1;i<=c[0];i++){
44memset(t,0,sizeof(t));
44cpy(b,t,i-1);
44a[0]=t[0];
44while(comp(a,t)){
444subs(a,t);
444c[i]++;
44}
4}
4if(c[1]!=0){
44for(int i=1;i<=c[0];i++) cout<<c[i];
4}
4else{
44for(int i=2;i<=c[0];i++) cout<<c[i];
4}
4return 0;
}
|
