No.1 A+B problem || 高精度算法初步

2021-07-08 22:41:10

　　从oj来的朋友可能会非常疑惑，为什么一个简单的A+B问题，还能被卡住呢？

　　请大家注意一下oj上面对于A,B 的数据的范围限制！其中，A，B都是不大于1000 位的数！

　　很显然，我们没有任何一种数据类型可以存放的下A，B的其中一个，这当然也就意味着我们无法用一般方法去直接进行加法运算。

　　聪明如你，一眨眼就想到了小学的时候学过的竖式加法。我们把两个加数的末尾对齐，然后一位一位相加，这样的话，我们就只用关注每一位上的加法以及进位就可以了！

　　而一提到按位相加，聪明的你当然又想到了利用数组！我们只需要把输入的A，B存入两个数组中，然后模仿竖式加法的原理，一位一位相加，然后进位就好了！

　　就像这样：如果你已经理解了这个思想，那么你也就理解了高精度算法。

　　那么我们现在把代码逐行讲解：

1 string A,B; //A用来存储数A，B用来存储B
2 int C[10001]; //C用来存储A+B的和 
3 int next1; //用来计算进位

　　这三行是定义了变量，其中string是定义的字符串变量（c语言可以用char a[n]来代替），因为这种长串的数字我们不可以直接复制给数组，只能先把它放进字符串中，在读入结束以后，利用字符串的可以逐位访问的特点，就可以再进行后续的加法操作，这里的字符串只是提供了一个便于保存的容器。而C[10001] 是用来保存最终的结果的，next1是用来保存竖式加法中每一位的进位。

1     cin>>A>>B;
2     int lenA=A.size(); //读出A，B下标限度 
3     int lenB=B.size();
4     int lenC=max(lenA,lenB)+1; //C的长度比A，B大1 
5     lenA--;
6     lenB--; //C以1为下标开头，所以不用自减

　　用cin输入A，B（C语言里用scanf输入字符串），lenA=A.size() ;表示的是读出A的字符串的长度（C语言里可以用strlen(A)表示）;

　　lenC是用来确定两数之和的最大位，容易得出，两个数的和最长的长度就是这两个数中最长的长度+1（因为要考虑进位），所以LenC=max(lenA,lenB)+1;

　　因为字符串数组的下表是从零开始的，所以lenA，B要-1以便后续的使用，而lenC因为个人喜欢从下标1开始用，所以就不减了！

　　现在，我们要进行逐位运算，在计算之前，我们要注意一个问题，我们的加法是要从各位开始的，而我们A，B中的个位是字符串数组的最后一位，所以不要从开头开始加：

1     while(lenA>=0&&lenB>=0){ //从后到前计算
2         C[lenC--]=A[lenA--]+B[lenB--]-'0'-'0';
3     }

　　这里从后向前逐位计算该位上数字的和（从后到前！！！），然后存入C数组相应位中（先不考虑进位，在全部算完以后再统一进位会比较方便）。

　　这里是图片表达：

　　每个数从它的结尾下标一位一位向前。

    while(lenA>=0) C[lenC--]=A[lenA--]-'0';
    while(lenB>=0) C[lenC--]=B[lenB--]-'0';

　　这里是用来处理如果一个字符串比另一个字符串更长时，将那个字符串长出来的部分直接填入C中。

    lenC=max(A.size(),B.size())+1; //重新计算C的位数 
    for(int i=lenC;i>=1;i--){ //i=lenC 
        C[i]+=next1;
        next1=C[i]/10;
        C[i]%=10;
    }

　　这里重新计算了C的位数以便于接下来的进位操作（因为原先的lenC已经被改变了），接下来的几行应该很好理解，从后向前逐位查询，看C[i]是否大于10，如果大于10的话就把需要进位的数值赋给next1，把C[i]对10去模，然后在计算下一位时C[i+1]先加上next1的值。

　　至此，计算部分就全部完成了。接下来只需要正序把C数组输出就可以了！（但是需要先判断首位是否有0，如果有0当然是不能输出的！）

1     for(int i=1;i<=lenC;i++){
2         if(i==1&&C[i]==0) continue;
3         printf("%d",C[i]);
4     }

　　最后奉上全部的代码（直接复制提交通过了是不好的！）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string A,B; //A用来存储数A，B用来存储B
 4 int C[10001]; //C用来存储A+B的和 
 5 int next1; //用来计算进位 
 6 int main(){
 7     cin>>A>>B;
 8     int lenA=A.size(); //读出A，B下标限度 
 9     int lenB=B.size();
10     int lenC=max(lenA,lenB)+1; //C的长度比A，B大1 
11     lenA--;
12     lenB--; //C以1为下标开头，所以不用自减 
13     while(lenA>=0&&lenB>=0){ //从后到前计算 
14         C[lenC--]=A[lenA--]+B[lenB--]-'0'-'0';
15     }
16     while(lenA>=0) C[lenC--]=A[lenA--]-'0';
17     while(lenB>=0) C[lenC--]=B[lenB--]-'0';
18     lenC=max(A.size(),B.size())+1; //重新计算C的位数 
19     for(int i=lenC;i>=1;i--){ //i=lenC 
20         C[i]+=next1;
21         next1=C[i]/10;
22         C[i]%=10;
23     }
24     for(int i=1;i<=lenC;i++){
25         if(i==1&&C[i]==0) continue;
26         printf("%d",C[i]);
27     }
28 }

　　感谢大家阅读！

欢迎关注oj：http://8.130.177.92/

码农公寓

相关文章