当前位置：首页 > news >正文

洛谷 P1601 A+B Problem（高精）详解c++

news 来源：原创 2025/9/4 8:25:52

我们之前做题碰到的数据范围一般是10^9，多点会达到10^18级别，处理10^9用int就可以存下，10^18次方要用到long long，接着解决加减乘除的问题，但是当数据范围达到了10^10^6的时候，当数据的值特别⼤，各种类型都存不下的时候，此时就要⽤⾼精度算法来计算加减乘除：

先⽤字符串读⼊这个数，然后⽤数组逆序存储该数的每⼀位；（把123放在我们眼前，我们会认为他是个数字，在计算机视角中看123的时候，是把它们当成1字符，2字符，3字符来看的，我们用字符串string读数的时候，它就会把这个数当成字符串读进来，如果一个数据范围是10^4，撑死这个字符串的长度就是10^4长度的一个字符串而已；我们做计算的时候是先从个位数开始的，比如123+45，先是3+5=8，2+4=6，1+0=1，一共是168，所以逆序的时候，a数组下标为0的位置存的正好是个位，从下标为0，逐渐向后走的时候，是从个位到十位到百位，正好跟我们的计算过程是一一对应的，比如数组从左往右遍历的时候，是在模拟加法计算过程，也就是最低位到最高位，所以我们第一步要先把它逆序存在数组中，这是方便的形式一，有的时候处理到进位的时候，如果正序存的话，进位的那一位就不知道放在哪里了，所以第一步是要把它的每一位逆序的存在数组中）
利⽤数组，模拟加减乘除运算的过程

⾼精度算法本质上还是模拟算法，⽤代码模拟⼩学列竖式计算加减乘除的过程

题目链接： P1601 A+B Problem（高精） - 洛谷

1.题目

2.算法原理

先用字符串读入，拆分每一位，逆序放在数组中
利用数组，模拟小学列竖式计算加法的过程

把123放在我们眼前，我们会认为他是个数字，在计算机视角中看123的时候，是把它们当成1字符，2字符，3字符来看的，我们用字符串string读数的时候，它就会把这个数当成字符串读进来，如果一个数据范围是10^4，撑死这个字符串的长度就是10^4长度的一个字符串而已

我们做计算的时候是先从个位数开始的，比如123+45，先是3+5=8，2+4=6，1+0=1，一共是168，所以逆序的时候，a数组下标为0的位置存的正好是个位，从下标为0，逐渐向后走的时候，是从个位到十位到百位，正好跟我们的计算过程是一一对应的，比如数组从左往右遍历的时候，是在模拟加法计算过程，也就是最低位到最高位，所以我们第一步要先把它逆序存在数组中，这是方便的形式一，有的时候处理到进位的时候，如果正序存的话，进位的那一位就不知道放在哪里了，所以第一步是要把它的每一位逆序的存在数组中

x里面存着“439”字符串，a数组里面存着934，它们的下标是有对应关系的，x里面的4对应的下标，加上a数组里面的4对应的下标之和是2，其他x和a数组里面的两个元素所对应的下标之和分别也是2，可以发现对应位置的下标相加正好是字符串的长度-1，因此一会逆序的时候用一个变量 i 从前往后遍历字符串的时候，在a数组中对应的位置是n-1-i ，因为下标之和相加等于n -1，还有注意在遍历x的时候拿到的是它的字符，如果要拿它里面的数要减去’0’

如果是99+1的话，lc的长度等于2，结果是100，所以实际lc的程度应该等于3，所以我们要处理一下这种情况，如果当前lc里面存着值，我们要让lc的实际长度+1

总结过程（上面是数组模拟例子）

对应位相加，然后加上进位 -> x
处理进位 i -> 13/10=1，进一位
处理余数 -> 13%10=3

代码

#include <iostream>
using namespace std;const int N = 1e6 + 10;
int a[N], b[N], c[N];
int la, lb, lc; //分别标记abc数组长度// 高精度加法的模版 - c = a + b;
void add(int c[], int a[], int b[])
{for (int i = 0; i < lc; i++){c[i] += a[i] + b[i]; // 对应位相加，再加上进位 9+4=13c[i + 1] += c[i] / 10; // 处理进位 13/10=1c[i] %= 10; // 处理余数 13%10=3}if (c[lc]) lc++;
}int main()
{string x, y; cin >> x >> y;// 1. 拆分每一位，逆序放在数组中la = x.size(); lb = y.size(); lc = max(la, lb);for (int i = 0; i < la; i++) a[la - 1 - i] = x[i] - '0';for (int i = 0; i < lb; i++) b[lb - 1 - i] = y[i] - '0';// 2. 模拟加法的过程add(c, a, b); // c = a + b// 输出结果for (int i = lc - 1; i >= 0; i--) cout << c[i];return 0;
}

1.题目

2.算法原理

代码

相关文章：