高精度

算法 / 大数处理
字数统计: 2.2k   |   阅读时长≈ 11 分钟

2024.4.7更新：

重新写了下，老的在下面

加

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a,b;
	cin>>a>>b;
	int lena = a.size(), lenb = b.size();
	if(lena < lenb){
		swap(a,b);
		swap(lena, lenb);
	}
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	
	vector<int>ans(lena + 1, 0);
	int n = ans.size();
	for(int i = 0; i < n; i++){
		if(i < lenb) ans[i] += a[i] + b[i] - '0'*2;
		else if(i < lena) ans[i] += a[i] - '0';
		if(ans[i] >= 10){
			ans[i] %= 10; 
			ans[i+1]++;
		}
	}
	bool flag = 1;
	for(int i = n-1; i >= 0; i--){
		if(ans[i] == 0 && flag) continue;
		flag = 0;
		cout<<ans[i];
	}
	if(flag && ans[0] == 0) cout<<0; 
	return 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
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a,b;
	cin>>a>>b;
	int lena = a.size(), lenb = b.size();
	if(lena < lenb || (lena == lenb && a < b)){
		swap(a,b);
		swap(lena, lenb);
		cout<<"-";
	}
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	
	vector<int>ans(lena, 0);
	int n = ans.size();
	for(int i = 0; i < n; i++){
		if(i < lenb) ans[i] += a[i] - b[i];
		else if(i < lena) ans[i] += a[i] - '0';
		if(ans[i] < 0 && i < n){
			ans[i+1]--;
			ans[i] += 10;
		}
	}
	bool flag = 1;
	for(int i = n - 1; i >= 0; i--){
		if(flag && ans[i] == 0) continue;
		flag = 0;
		cout<<ans[i];
	}
	if(flag && ans[0] == 0) cout<<0;
	return 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
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a,b;
	cin>>a>>b;
	int lena = a.size(), lenb = b.size();
	if(lena < lenb || (lena == lenb && a < b)){
		swap(a,b);
		swap(lena, lenb);
		cout<<"-";
	}
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	vector<int>ans(lena + lenb + 1, 0);
	int n = ans.size();
	for(int i = 0; i < lena; i++){
		for(int j = 0; j < lenb; j++){
			int x = a[i] - '0', y = b[j] - '0'; 
			ans[i + j] += x*y;
			if(ans[i+j] >= 10){
				ans[i+j+1] += ans[i+j] / 10;
				ans[i+j] %= 10;
			}
		}
	}
	bool flag = 1;
	for(int i = n - 1; i >= 0; i--){
		if(flag && ans[i] == 0) continue;
		flag = 0;
		cout<<ans[i];
	}
	if(flag && ans[0] == 0) cout<<0;
	return 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
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a;
	long long b;
	cin>>a>>b;
	int n = a.size();
	vector<long long>ans;
	long long cur = 0;
	for(int i = 0; i < n; i++){
		cur*=10;
		cur += a[i] - '0';
		ans.push_back(cur / b);
		cur %= b;
	}
	bool flag = 1;
	for(int i = ； i < ans.size(); i++){
		if(ans[i] == 0 && flag) continue;
		flag = 0;
		cout<<ans[i];
	}
	if(flag) cout<<0;
	return 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

const int N = 1e5 + 10;
int a[N],b[N],c[N];//数组C存储结果
char s1[N],s2[N];//存储读入的字符串

int main()
{
    cin >> s1 >> s2;
    int la = strlen(s1);
    int lb = strlen(s2);
    for (int i = 0;i < la;i++) a[la - i] = s1[i] - '0';//倒序存储
    for (int i = 0;i < lb;i++) b[lb - i] = s2[i] - '0';
    int lc = max(la,lb) + 1;
    for (int i = 1;i <= lc;i++)//注意此处的下标从1开始(可以使用12345 + 23456模拟)
    {
        c[i] += (a[i] + b[i]);//两式相加
        c[i + 1] = c[i] / 10;//如果有进位的话,向高位进位
        c[i] = c[i] % 10;//如果是两位数,则进位之后需要取模
    }
    //删除前导0
    if (c[lc] == 0) lc --;
    for (int i = lc;i > 0;i --) printf("%d",c[i]);
    return 0;
}
1
2
3
4
5
6
7
for(int i(1);i<cz;i++)//cz的长度为max(sz1,sz2)+1;
{
		c[i]=n1[i]+n2[i]+x;    
		x=c[i]/10;                   //其实这里也可以加一个条件 当..x>=10时才执行
		c[i]%=10;                    //%10保存<10的数
}
		c[i]=x;//保存最后的进位;

减法

如果a < b，则需要先交换a与b，最后在输出结果前加上负号

在高精度计算时，如果a[i] < b[i]，则需要先向高位借一位

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
const int N = 1e5 +10;
int a[N],b[N],c[N];//数组c用来存储结果
char s1[N],s2[N],s3[N];//s3用来帮助交换s1和s2
int flag;//默认为0

//判断s1和s2的大小关系:如果s1 >= s2,返回true;否则,返回false
bool cmp(char s1[],char s2[])
{
    int u = strlen(s1),v = strlen(s2);
    if (u != v) return u > v;

    for (int i = 0;i < u;i++)//执行到这里,说明u == v
        if (s1[i] != s2[i])
            return s1[i] > s2[i];
    return true;//s1 == s2
}

int main()
{
    int la,lb,lc; cin >> s1 >> s2;
    if (!cmp(s1,s2))//表示s1 < s2
    {
        //交换之后可以保证s1 > s2
        flag = 1;
        strcpy(s3,s1);
        strcpy(s1,s2);
        strcpy(s2,s3);
    }
    la = strlen(s1),lb = strlen(s2);

    //将输入的字符串转化为数字并倒序存储
    for (int i = 0;i < la;i++) a[la - i] = s1[i] - '0';
    for (int i = 0;i < lb;i++) b[lb - i] = s2[i] - '0';

    //高精度算法核心代码
    lc = max(la,lb);
    for (int i = 1;i <= lc;i++)
    {
        if (a[i] < b[i])
        {
            a[i + 1] --;//借位
            a[i] += 10;
        }
        c[i] = a[i] - b[i];
    }

    while (c[lc] == 0 && lc > 1) lc --;//删除前导0
    if (flag == 1) cout << "-";
    for (int i = lc;i > 0;i--) cout << c[i];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
	//先判断ss1是否比ss2小，如果小就交换两则的顺序
	if ((ss1.size()<ss2.size()) || (ss1.size() ==ss2.size() && ss1<ss2)) {
		swap(ss1, ss2);   //交换
		cout << "-";
	}//并率先输出一个负号} 

int max_c = max(sz1, sz2);    //这里与加法不同没有+1，因为减法不存在最后多一位的情况
	for (int i(1); i <= max_c; i++) {
		if (a[i] < b[i]) {
			a[i + 1] --;                        //如果a<b我们直接向下一位借位，然后本位加10.
			a[i] += 10;}
		c[i] = a[i] - b[i];
	}

乘法

高精度运算中数组的总结
与高精度加法、高精度减法一样，在高精度乘法中，利用两个字符数组s1[N]、s2[N]存储输入的数据，然后将输入的数据(字符)转化为数字并逆序存放在数组a[N]、b[N]中。最后，通过对数组a[N]、b[N]进行操作，将操作的结果保存在c[N]即可。输出结果的时候需要逆序输出c[N]，抵消之前逆序存储带来的影响。

A[i] \* B[j] —> C[i + j - 1]

核心

1
2
3
[i + j - 1] += (a[i] * b[j]);
c[i + j] += c[i + j - 1] / 10;
c[i + j - 1] %= 10;
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
const int N = 1e5 + 10;
int a[N],b[N],c[N];//c数组用来保存结果
char s1[N],s2[N];

int main()
{
cin >> s1 >> s2;//输入数据
int la = strlen(s1),lb = strlen(s2);

for (int i = 0;i < la;i++) a[la - i] = s1[i] - '0';//转化为数字再逆序存储
for (int i = 0;i < lb;i++) b[lb - i] = s2[i] - '0';

int lc = la + lb;    
for (int i = 1;i <= la;i++)//高精度算法核心代码
{
  for (int j = 1;j <= lb;j++)
  {
      c[i + j - 1] += (a[i] * b[j]);//计算
      c[i + j] += c[i + j - 1] / 10;//向高位进位
      c[i + j - 1] %= 10;
  }
}

while (c[lc] == 0 && lc > 1) lc --;//删除前导0
for (int i = lc;i > 0;i--) cout << c[i];//输出结果
return 0;
}
1
2
3
4
5
6
7
for (int i = 1; i <= a.size(); i++) {
	for (int j=1; j <= b; j++) {
		c[i + j - 1] += a[i] * b[j];                  //看不懂,可以直接记模板
		c[i + j] += c[i + j - 1] / 10;
		c[i + j - 1] %= 10;
	}
}

除法(高除以低)

算法核心：逐位试商法

①从被除数的第一位开始，用此数除以除数，得出商和余数

②用得出的余数与被除数的下一位数字结合继续除以除数，以此类推

思路

1、定义存储数组。

2、读入数据处理。

3、试商过程。

4、删除前导 0 。所谓前导零，就是出现类似这样数据 01234，这个 0 实际是不需要的。

5、输出结果。倒序输出减法的结果数组 C，因为我们的个位是存储在下标为 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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>

using namespace std;
typedef long long LL;
const int N = 1E5 + 10;
LL b,x;//x代表余数
LL a[N],c[N];//c:结果数组
char s1[N];

int main()
{
    cin >> s1 >> b;
    LL la = strlen(s1);//输入数据的长度
    for (int i = 1;i <= la;i++) a[i] = s1[i - 1] - '0';//正序存储输入的数据
    
    for (int i = 1;i <= la;i++)//高精度除以单精度核心代码
    {
        c[i] = (x * 10 + a[i]) / b;
        x = (x * 10 + a[i]) % b;
    }
    
    LL lc = 1;//输出结果
    while (c[lc] == 0 && lc < la) lc ++;//删除前导0
    for (int i = lc;i <= la;i++) cout << c[i];
    return 0;
}

  • Copyrights © 2023-2024 Kano
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信