为适应于不同用途,将大数算法写成了两个版本,分别为只处理正整数的版本和包含负数处理的版本,可根据需要选用。
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 }
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 }
为方便理解,特画出版本二的程序运行流程图(为图示清晰,省略了函数形参):
1、正整数版本,借鉴了牛客网“赞一下”用户的思想,在此感谢,原题目参见https://www.nowcoder.com/questionTerminal/5821836e0ec140c1aa29510fd05f45fc?orderByHotValue=0&mutiTagIds=578_579&page=2&onlyReference=false。
2、含负数版本,参考了这篇文章的实现思路:http://blog.csdn.net/to_be_better/article/details/50375420