• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

开发技术 开发技术 5小时前 2次浏览

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

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

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

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

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

  就像这样:No.1 A+B problem || 高精度算法初步 如果你已经理解了这个思想,那么你也就理解了高精度算法。

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

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数组相应位中(先不考虑进位,在全部算完以后再统一进位会比较方便)。

  这里是图片表达:

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

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

 

    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/ 

 


程序员灯塔
转载请注明原文链接:No.1 A+B problem || 高精度算法初步
喜欢 (0)