高精度加法、减法

0705

一、为什么需要高精度运算？

1.1 整数范围限制

数据类型 位数 范围
int 32位 -2,147,483,648 ~ 2,147,483,647
long long 64位 -9.2×10¹⁸ ~ 9.2×10¹⁸

问题：当数值超过 10^18 或位数达到1000位时，基础类型无法存储。
string类型，日常使用几乎没有长度限制

32位系统 最大约 21 亿 字符
64位系统 最大约 9e18 字符（天文数字）

1.2 需要高精度运算的场景

  • 大整数阶乘计算（100! 远超 long long 范围）
  • 组合数学中的精确计算
  • 超过 64 位整数范围的所有场景

二、高精度加法

2.1 核心思想

逐位相加，进位传递

模拟小学竖式加法运算：

    9 9 9
  + 1 2 3
  -------
  1 1 2 2

从右往左逐位相加，如果和 ≥ 10，则进位。

原理：使用数组存储，将数字的低位存放在低下标，高位存放在高下标。

目的：为了方便处理进位和借位运算（模拟竖式计算），使得数组下标与进位方向一致。

示例：数字 123 存储为数组 a[1]=3, a[2]=2, a[3]=1（通常 a[0] 用来记录位数）。

2.2 算法步骤

输入：字符串 a, b（存储非负整数）
输出：字符串 result

1. 反转字符串，使最低位在前
2. 从左到右遍历：
   a. 取当前位的数字（不存在则视为0）
   b. 计算 sum = a[i] + b[i] + carry
   c. result[i] = sum % 10
   d. carry = sum / 10
3. 如果最后 carry > 0，在结果末尾添加
4. 反转结果字符串，去除前导零

2.3 C++ 实现

#include<bits/stdc++.h>
using namespace std;
int a[1005], b[1005], c[1005];
string sa, sb;


void s2BIG(string s, int a[])
{
	a[0] = s.size();
	for(int i = 1; i <= a[0]; i++)
		a[i] = s[a[0]-i] - '0';
}
void printBIG(int a[])
{
	for(int i = a[0]; i >= 1; i--)
		cout << a[i];
}
void addBIG(int a[], int b[], int c[])
{
	c[0] = max(a[0], b[0]);
	int u = 0;
	for(int i = 1; i <= c[0]; i++)
	{
		int t = a[i] + b[i] + u;
		c[i] = t % 10;
		u = t / 10;
	}
	if(u > 0) c[++c[0]] = u; //最高位进位
}


int main()
{
	cin >> sa >> sb;
	s2BIG(sa, a);
	s2BIG(sb, b);
	addBIG(a, b, c);
	printBIG(c);
    return 0;
}

2.4 复杂度分析

指标 复杂度
时间复杂度 O(max(n, m))，n、m 为两数长度
空间复杂度 O(max(n, m))

三、高精度减法

3.1 核心思想

逐位相减，借位处理

模拟小学竖式减法运算：

    1 0 0 0
  -     9 9
  ----------
      9 0 1

关键点：确保被减数 ≥ 减数，否则交换位置并标记负号。

3.2 算法步骤

输入：字符串 a, b（存储非负整数）
输出：字符串 result

1. 比较 a 和 b 的大小：
   - 如果 a < b，交换 a 和 b，记录负号
2. 反转字符串
3. 从左到右遍历：
   a. 取当前位的数字
   b. 如果 a[i] < b[i]，向左借位
   c. result[i] = a[i] - b[i]
4. 去除结果的前导零，保留至少一位
5. 如果最初被交换过，添加负号

3.3 C++ 实现

#include<bits/stdc++.h>
using namespace std;
int a[1005], b[1005], c[1005];
string sa, sb;


void s2BIG(string s, int a[])
{
	a[0] = s.size();
	for(int i = 1; i <= a[0]; i++)
		a[i] = s[a[0]-i] - '0';
}
void printBIG(int a[])
{
	for(int i = a[0]; i >= 1; i--)
		cout << a[i];
}
void i2BIG(int n, int a[])
{
	while(n > 0)
	{
		a[++a[0]] = n % 10;
		n /= 10;
	}
	if(a[0] == 0) a[0] = 1;
}
bool cmpBIG(int a[], int b[])
{
	if(a[0] != b[0]) return a[0] > b[0];
	for(int i = a[0]; i >= 1; i--)
		if(a[i] != b[i]) return a[i] > b[i];
	return false;
}
void subBIG(int a[], int b[], int c[])
{
    c[0] = max(a[0], b[0]);
    int u = 0;
    for(int i = 1; i <= c[0]; i++)
    {
        int t = a[i] - u - b[i];
        if(t < 0)
        {
            c[i] = t + 10;
            u = 1;
        }
        else
        {
            c[i] = t;
            u = 0;
        }
    }
    while(c[ c[0] ] == 0 && c[0] > 1) c[0]--;//去除高位多余的前缀0
}
int main()
{
	cin >> sa >> sb;
	s2BIG(sa, a);
	s2BIG(sb, b);
	if(cmpBIG(a, b)) 
    	subBIG(a, b, c);
	else
	    subBIG(b, a, c);
	printBIG(c);
    return 0;
}

3.4 复杂度分析

指标 复杂度
时间复杂度 O(max(n, m))
空间复杂度 O(max(n, m))

四、常见题型与模板

/ 字符串转换为数组函数
void s2BIG(string s, int a[]){
	a[0] = s.size();
	for(int i = 1; i <= a[0]; i++)
		a[i] = s[a[0]-i] - '0';
}


// 输出函数
void printBIG(int a[]){
	for(int i = a[0]; i >= 1; i--)
		cout << a[i];
}


// 加法运算函数，c = a + b，结果存储到 c
void addBIG(int a[], int b[], int c[]){
	c[0] = max(a[0], b[0]);
	int u = 0; // 是否进位，初始0代表无进位
	for(int i = 1; i <= c[0]; i++){
		int t = a[i] + b[i] + u;
		c[i] = t % 10;
		u = t / 10;
	}
    // 处理最高位进位
	if(u > 0) c[++c[0]] = u;
}


// 将int类型的数字 n 转化为高精度存储 a 函数
void i2BIG(int n, int a[]){ 
	while(n > 0){
		a[++a[0]] = n % 10; // 位数++，存储低位
		n /= 10;
	}
 	if(a[0] == 0) a[0] = 1;// 若n是0，记录位数是1
}


// 高精度比较大小函数，若a大返回t，否则返回f
bool cmpBIG(int a[], int b[]){
    // 先比较位数
	if(a[0] != b[0]) return a[0] > b[0];
	// 位数相同，从前往后比较
	for(int i = a[0]; i >= 1; i--)
		if(a[i] != b[i]) return a[i] > b[i];
	return false;
}


// 减法函数，c = a - b，a减去b结果存到c
void subBIG(int a[], int b[], int c[]){
    c[0] = max(a[0], b[0]);
    int u = 0; // 是否借位，初始0代表无借位
    for(int i = 1; i <= c[0]; i++){
        int t = a[i] - u - b[i];
        if(t < 0){ // 需要借位
            c[i] = t + 10;
            u = 1;
        }
        else{
            c[i] = t;
            u = 0;
        }
    }
    // 去除高位多余的前缀0
    while(c[c[0]] == 0 && c[0] > 1) c[0]--;
}

五、易错点与注意事项

5.1 加法易错点

错误类型 正确做法
未处理最后进位 循环结束后检查 carry > 0
未处理前导零 最后去除前导零
字符串未反转 从低位开始运算

5.2 减法易错点

错误类型 正确做法
未处理负号 比较大小，必要时交换并标记负号
借位处理错误 借位后高位需减1
前导零未去除 保留至少一位”0″

5.3 调试技巧

// 中间输出调试
cout << "a = " << a << ", b = " << b << endl;
cout << "step " << i << ": " << da << " + " << db << " = " << sum << endl;
cout << "carry = " << carry << ", digit = " << digit << endl;

六、总结

运算 核心操作 关键点
加法 逐位相加 + 进位 处理最后的进位
减法 逐位相减 + 借位 确保被减数 ≥ 减数

核心思想：将大整数用字符串表示，从低位到高位逐位运算，人工模拟竖式计算过程。

七、经典题目

高精度输入输出

#include<bits/stdc++.h>
using namespace std;
int a[1005];
void s2BIG(string s, int a[])
{
// 	int len = s.size();
// 	for(int i = 1; i <= len; i++)
// 		a[i] = s[len-i] - '0';
//技巧：长度存a[0]，可以跟着a数组一起走
    a[0] = s.size(); 
	for(int i = 1; i <= a[0]; i++)
		a[i] = s[a[0]-i] - '0';    
}


void printBIG(int a[])
{
	for(int i = a[0]; i >= 1; i--)
		cout << a[i];
}


int main()
{
    string s;
    cin>>s;
    s2BIG(s,a);
    printBIG(a);
    return 0;
}

a+b高精度

#include<bits/stdc++.h>
using namespace std;
int a[1005], b[1005], c[1005];
string sa, sb;


void s2BIG(string s, int a[])
{
	a[0] = s.size();
	for(int i = 1; i <= a[0]; i++)
		a[i] = s[a[0]-i] - '0';
}
void printBIG(int a[])
{
	for(int i = a[0]; i >= 1; i--)
		cout << a[i];
}
void addBIG(int a[], int b[], int c[])
{
	c[0] = max(a[0], b[0]);
	int u = 0;
	for(int i = 1; i <= c[0]; i++)
	{
		int t = a[i] + b[i] + u;
		c[i] = t % 10;
		u = t / 10;
	}
	if(u > 0) c[++c[0]] = u; //最高位进位
}


int main()
{
	cin >> sa >> sb;
	s2BIG(sa, a);
	s2BIG(sb, b);
	addBIG(a, b, c);
	printBIG(c);
    return 0;
}

斐波那契高精度

#include<bits/stdc++.h>
using namespace std;
int n, f[4005][1005];
//f[i]表示斐波拉契数列中的第i个数字
//f[i][j]表示斐波拉契数列中的第i个数字的倒数第j位


void s2BIG(string s, int a[])
{
	a[0] = s.size(); //存储高精度数字a的位数
	for(int i = 1; i <= a[0]; i++)
		a[i] = s[a[0]-i] - '0';
}
void printBIG(int a[])
{
	for(int i = a[0]; i >= 1; i--)
		cout << a[i];
}
void addBIG(int a[], int b[], int c[])
{
	c[0] = max(a[0], b[0]);
	int u = 0;
	for(int i = 1; i <= c[0]; i++)
	{
		int t = a[i] + b[i] + u;
		c[i] = t % 10;
		u = t / 10;
	}
	if(u > 0) c[++c[0]] = u;
}
//将int类型的数字n转化为高精度数字a
void i2BIG(int n, int a[])
{ 
	while(n > 0)
	{
		a[++a[0]] = n % 10;
		n /= 10;
	}
 	if(a[0] == 0) a[0] = 1;//如果n是0,记录位数是1位
}


int main()
{
	cin >> n;
	i2BIG(1, f[1]);
	i2BIG(1, f[2]);
	for(int i = 3; i <= n; i++)
		addBIG(f[i-1], f[i-2], f[i]);
	printBIG(f[n]);
    return 0;
}

a-b高精度

#include<bits/stdc++.h>
using namespace std;
int a[1005], b[1005], c[1005];
string sa, sb;


void s2BIG(string s, int a[])
{
	a[0] = s.size();
	for(int i = 1; i <= a[0]; i++)
		a[i] = s[a[0]-i] - '0';
}
void printBIG(int a[])
{
	for(int i = a[0]; i >= 1; i--)
		cout << a[i];
}
void i2BIG(int n, int a[])
{
	while(n > 0)
	{
		a[++a[0]] = n % 10;
		n /= 10;
	}
	if(a[0] == 0) a[0] = 1;
}
bool cmpBIG(int a[], int b[])
{
	if(a[0] != b[0]) return a[0] > b[0];
	for(int i = a[0]; i >= 1; i--)
		if(a[i] != b[i]) return a[i] > b[i];
	return false;
}
void subBIG(int a[], int b[], int c[])
{
    c[0] = max(a[0], b[0]);
    int u = 0;
    for(int i = 1; i <= c[0]; i++)
    {
        int t = a[i] - u - b[i];
        if(t < 0)
        {
            c[i] = t + 10;
            u = 1;
        }
        else
        {
            c[i] = t;
            u = 0;
        }
    }
    while(c[ c[0] ] == 0 && c[0] > 1) c[0]--;//去除高位多余的前缀0
}
int main()
{
	cin >> sa >> sb;
	s2BIG(sa, a);
	s2BIG(sb, b);
	if(cmpBIG(a, b)) 
    	subBIG(a, b, c);
	else
	    subBIG(b, a, c);
	printBIG(c);
    return 0;
}

票选冠军

#include<bits/stdc++.h>
using namespace std;
int n, a[1005], b[1005], x[1005];
void s2BIG(string s, int a[])
{
	a[0] = s.size();
	for(int i = 1; i <= a[0]; i++)
		a[i] = s[a[0]-i] - '0';
}
void printBIG(int a[])
{
	for(int i = a[0]; i >= 1; i--)
		cout << a[i];
}
void addBIG(int a[], int b[], int c[])
{
	c[0] = max(a[0], b[0]);
	int u = 0;
	for(int i = 1; i <= c[0]; i++)
	{
		int t = a[i] + b[i] + u;
		c[i] = t % 10;
		u = t / 10;
	}
	if(u > 0) c[++c[0]] = u;
}
void i2BIG(int n, int a[])
{
	while(n > 0)
	{
		a[++a[0]] = n % 10;
		n /= 10;
	}
	if(a[0] == 0) a[0] = 1;
}
bool cmpBIG(int a[], int b[])
{
	if(a[0] != b[0]) return a[0] > b[0];
	for(int i = a[0]; i >= 1; i--)
		if(a[i] != b[i]) return a[i] > b[i];
	return false;
}


int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		char c;
		string sx;
		cin >> c >> sx;
		memset(x, 0, sizeof(x));
		s2BIG(sx, x);
		if(c == 'A') 
		    addBIG(a, x, a);
		else 
		    addBIG(b, x, b);
	}
	if(cmpBIG(a, b))
	{
		cout << "A\n";
		printBIG(a);
	}
	else
	{
		cout << "B\n";
		printBIG(b);
	}
    return 0;
}
© 版权声明
🎀 🌸
📜 版权声明：

本站信息： 码图星探 https://matuxingtan.com/
本站资源均来源网络，仅供学习参考，如有侵权，请联系我们删除
本站资源大多存储在云存储、图床及网盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END
数据结构与算法
喜欢就支持一下吧
点赞5 分享
lingyi的头像-码途星探
GESP赛前备考-码途星探
GESP赛前备考
GESP赛前备考
2个月前 512
2026年3月一级真题解析-码途星探
2026年3月一级真题解析
2026年3月一级真题解析
2个月前 251
2026年3月三级真题解析-码途星探
2026年3月三级真题解析
2026年3月三级真题解析
2个月前 167
二维数组基础-码途星探
二维数组基础
二维数组基础
3个月前 143
2026年3月二级真题解析-码途星探
2026年3月二级真题解析
2026年3月二级真题解析
2个月前 140
编程解题技巧-高效解题-码途星探
编程解题技巧-高效解题
编程解题技巧-高效解题
3个月前 129
相关推荐
高精度加法、减法-码途星探
高精度加法、减法
高精度加法、减法
7天前 70
埃式筛和欧拉筛-码途星探
埃式筛和欧拉筛
埃式筛和欧拉筛
19天前 66
队列-码途星探
队列
队列
2个月前 52
栈-码途星探
栈
栈
2个月前 86
map容器-码途星探
map容器
map容器
2个月前 23
前缀和-码途星探
前缀和
前缀和
3个月前 66
评论 抢沙发

请登录后发表评论

    暂无评论内容