【模板小程序】十进制大数相加（正整数版本+整数版本【正负0】），包含合法性检查 ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›小程序云开发高级教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

为适应于不同用途，将大数算法写成了两个版本，分别为只处理正整数的版本和包含负数处理的版本，可根据需要选用。

版本1：只能处理正整数

 1 //大数相加（十进制正整数）,用string处理
 2 #include <iostream>
 3 #include <string>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 //输入数据合法性检查,数字必须在0-9范围内
 9 bool IsVaild(const string& num1,const string& num2)
10 {
11     for(auto val:num1)
12     {
13         if(!(val>='0' && val-'0'<='9'))
14             return false;
15     }
16     for(auto val:num2)
17     {
18         if(!(val>='0' && val<='9'))
19             return false;
20     }
21     return true;
22 }
23 
24 string greatNumberAdd(string num1,string num2)
25 {
26     const size_t len1=num1.length();
27     const size_t len2=num2.length();
28     const size_t n=len1>len2 ? len1 :len2;
29     reverse(num1.begin(),num1.end());
30     reverse(num2.begin(),num2.end());
31     
32     string result;
33     int carry=0;
34     for(size_t i=0;i<n;++i)
35     {
36         const int num1i = i<len1 ? num1[i]-'0' :0;
37         const int num2i = i<len2 ? num2[i]-'0' :0;
38         const int val   = (num1i+num2i+carry)%10;
39         carry=(num1i+num2i+carry)/10;
40         result.insert(result.begin(),val+'0');
41     }
42     if(1==carry)//若最前面有进位，则插入'1'
43         result.insert(result.begin(),'1');
44     
45     return result;
46 }
47 
48 int main()
49 {
50     string num1,num2;
51     while(cin>>num1>>num2)
52     {
53         if(IsVaild(num1,num2))
54             cout<<greatNumberAdd(num1,num2)<<endl;
55         else
56             cout<<"输入数据不合法"<<endl;
57     }
58     return 0;
59 }

版本2：可处理正整数、0、负整数（STL编码风格）

  1 /*
  2 本程序说明：
  3 
  4 大数相加（十进制正负整数）,用string处理
  5 
  6 时间复杂度：O(k),k为字符串长度(取大者)
  7 空间复杂度：O(1)
  8 
  9 */
 10 
 11 #include <iostream>
 12 #include <string>
 13 #include <algorithm>
 14 
 15 using namespace std;
 16 
 17 //输入数据合法性检查,数字必须在0-9范围内
 18 bool IsVaild(const string& num1,const string& num2)
 19 {
 20     for(size_t i=0;i<num1.length();++i)
 21     {
 22         if(0==i && '-'==num1[0] && ++i<num1.length()){};//首位可以是'-',这里直接加i,继续判断
 23         if(!(num1[i]>='0' && num1[i]-'0'<='9'))
 24             return false;
 25     }
 26     for(size_t i=0;i<num2.length();++i)
 27     {
 28         if(0==i && '-'==num2[0] && ++i<num2.length()){};//首位可以是'-',这里直接加i,继续判断
 29         if(!(num2[i]>='0' && num2[i]-'0'<='9'))
 30             return false;
 31     }
 32     return true;
 33 }
 34 
 35 //辅助函数：num1-num2
 36 string __greatNumberMinu(string num1,string num2)
 37 {
 38     const size_t len1=num1.length();
 39     const size_t len2=num2.length();
 40     const size_t n=len1>len2 ? len1 :len2;
 41     reverse(num1.begin(),num1.end());
 42     reverse(num2.begin(),num2.end());
 43 
 44     string result;
 45     int carry=0;//借位
 46     for(size_t i=0;i<n;++i)
 47     {
 48         const int num1i = i<len1 ? num1[i]-'0' :0;
 49         const int num2i = i<len2 ? num2[i]-'0' :0;
 50         const int val   = (num1i-carry-num2i>=0) ? (num1i-carry-num2i) : (num1i-carry-num2i+10);
 51         carry=(num1i-carry-num2i>=0) ? 0 : 1;
 52         result.insert(result.begin(),val+'0');
 53     }
 54     int firstIndex_notEqualTo_0=0;//找出第一个不为0的位置（如果前面均为0，则抹去）
 55     for(;firstIndex_notEqualTo_0<result.length();++firstIndex_notEqualTo_0)
 56     {
 57         if(result[firstIndex_notEqualTo_0]!='0')
 58             break;
 59     }
 60     if(firstIndex_notEqualTo_0>0)//（如果前面均为0，则抹去）
 61         result.erase(0,firstIndex_notEqualTo_0);
 62 
 63     return result;
 64 }
 65 
 66 //辅助函数：符号为一正一负时调用,这里的num1和num2不包含符号位（较大的减较小的，在本函数内判断）,sign为判断位
 67 string _greatNumberMinu(string num1,string num2,bool flag)
 68 {
 69     string result;
 70 
 71     size_t len1=num1.length();
 72     size_t len2=num2.length();
 73     if(len1>len2)//字符串比较,必须先判断长度（不能直接比较字符串，例如比较结果"2">"111",实际上按照数值来看"111">"2"）
 74     {
 75         result=__greatNumberMinu(num1,num2);
 76         if(flag)
 77             result.insert(result.begin(),'-');//在最前面添加'-'
 78     }
 79     else if(len1<len2)
 80     {
 81         result=__greatNumberMinu(num2,num1);
 82         if(!flag)
 83             result.insert(result.begin(),'-');//在最前面添加'-'
 84     }
 85     else/*len1==len2*/
 86     {
 87         if(num1>num2)//字符串比较（两字符串长度相等时就可以比较了）
 88         {
 89             result=__greatNumberMinu(num1,num2);
 90             if(flag)
 91                 result.insert(result.begin(),'-');//在最前面添加'-'
 92         }
 93         else if(num1<num2)
 94         {
 95             result=__greatNumberMinu(num2,num1);
 96             if(!flag)
 97                 result.insert(result.begin(),'-');//在最前面添加'-'
 98         }
 99         else
100             result="0";
101     }
102 
103     return result;
104 }
105 
106 //辅助函数：符号为两正和两负时调用,这里的num1和num2不包含符号位
107 string _greatNumberAdd(string num1,string num2)
108 {
109     const size_t len1=num1.length();
110     const size_t len2=num2.length();
111     const size_t n=len1>len2 ? len1 :len2;
112     reverse(num1.begin(),num1.end());
113     reverse(num2.begin(),num2.end());
114 
115     string result;
116     int carry=0;//进位
117     for(size_t i=0;i<n;++i)
118     {
119         const int num1i = i<len1 ? num1[i]-'0' :0;
120         const int num2i = i<len2 ? num2[i]-'0' :0;
121         const int val   = (num1i+num2i+carry)%10;
122         carry=(num1i+num2i+carry)/10;
123         result.insert(result.begin(),val+'0');
124     }
125     if(1==carry)//若最前面有进位，则插入'1'
126         result.insert(result.begin(),'1');
127 
128     return result;
129 }
130 
131 //大数相加入口，先判断符号（两正、两负、一正一负），再调用辅助函数
132 string greatNumberAdd(string num1Andsign,string num2Andsign)
133 {
134     string result;
135     if('-'==num1Andsign[0] && '-'==num2Andsign[0])//两负
136     {
137         result=_greatNumberAdd(num1Andsign.substr(1,num1Andsign.length()-1),num2Andsign.substr(1,num2Andsign.length()-1));
138         result.insert(result.begin(),'-');//在最前面添加'-'
139     }
140     else if('-'==num1Andsign[0] || '-'==num2Andsign[0])//一正一负
141     {
142         if('-'==num1Andsign[0])
143             result=_greatNumberMinu(num1Andsign.substr(1,num1Andsign.length()-1),num2Andsign,true);
144         else if('-'==num2Andsign[0])
145             result=_greatNumberMinu(num1Andsign,num2Andsign.substr(1,num2Andsign.length()-1),false);
146     }
147     else
148         result=_greatNumberAdd(num1Andsign,num2Andsign);//两正
149 
150     int firstIndex_notEqualTo_0=0;//找出第一个不为0的位置（如果前面均为0，则抹去）
151     for(;firstIndex_notEqualTo_0<result.length();++firstIndex_notEqualTo_0)
152     {
153         if(result[firstIndex_notEqualTo_0]!='0')
154             break;
155     }
156     if(firstIndex_notEqualTo_0>0)//（如果前面均为0，则抹去）
157         result.erase(0,firstIndex_notEqualTo_0);
158     if(result.empty())//如果两个数相加结果为0，最后处理完就为空了，因此直接输出"0"
159         result="0";
160     return result;
161 }
162 
163 int main()
164 {
165     string num1,num2;
166     while(cin>>num1>>num2)
167     {
168         if(IsVaild(num1,num2))
169             cout<<greatNumberAdd(num1,num2)<<endl;
170         else
171             cout<<"输入数据不合法"<<endl;
172     }
173     return 0;
174 }