大数

  1 #include <iostream>
  2 
  3 #include <string>
  4 
  5 using namespace std;
  6 
  7  
  8 
  9 inline int compare(string str1, string str2)
 10 
 11 {
 12 
 13 if(str1.size() > str2.size()) //长度长的整数大于长度小的整数
 14 
 15 return 1;
 16 
 17 else if(str1.size() < str2.size())
 18 
 19 return -1;
 20 
 21 else
 22 
 23 return str1.compare(str2); //若长度相等，从头到尾按位比较，compare函数：相等返回0，大于返回1，小于返回－1
 24 
 25 }
 26 
 27 //高精度加法
 28 
 29 string ADD_INT(string str1, string str2)
 30 
 31 {
 32 
 33 string MINUS_INT(string str1, string str2);
 34 
 35 int sign = 1; //sign 为符号位
 36 
 37 string str;
 38 
 39 if(str1[0] == '-') {
 40 
 41 if(str2[0] == '-') {
 42 
 43 sign = -1;
 44 
 45 str = ADD_INT(str1.erase(0, 1), str2.erase(0, 1));
 46 
 47 }else {
 48 
 49 str = MINUS_INT(str2, str1.erase(0, 1));
 50 
 51 }
 52 
 53 }else {
 54 
 55 if(str2[0] == '-')
 56 
 57 str = MINUS_INT(str1, str2.erase(0, 1));
 58 
 59 else {
 60 
 61 //把两个整数对齐，短整数前面加0补齐
 62 
 63 string::size_type l1, l2;
 64 
 65 int i;
 66 
 67 l1 = str1.size(); l2 = str2.size();
 68 
 69 if(l1 < l2) {
 70 
 71 for(i = 1; i <= l2 - l1; i++)
 72 
 73 str1 = "0" + str1;
 74 
 75 }else {
 76 
 77 for(i = 1; i <= l1 - l2; i++)
 78 
 79 str2 = "0" + str2;
 80 
 81 }
 82 
 83 int int1 = 0, int2 = 0; //int2 记录进位
 84 
 85 for(i = str1.size() - 1; i >= 0; i--) {
 86 
 87 int1 = (int(str1[i]) - 48 + int(str2[i]) - 48 + int2) % 10; //48 为 '0' 的ASCII码
 88 
 89 int2 = (int(str1[i]) - 48 + int(str2[i]) - 48 +int2) / 10;
 90 
 91 str = char(int1 + 48) + str;
 92 
 93 }
 94 
 95 if(int2 != 0) str = char(int2 + 48) + str;
 96 
 97 }
 98 
 99 }
100 
101 //运算后处理符号位
102 
103 if((sign == -1) && (str[0] != '0'))
104 
105 str = "-" + str;
106 
107 return str;
108 
109 }
110 
111  
112 
113  
114 
115 //高精度减法
116 
117 string MINUS_INT(string str1, string str2)
118 
119 {
120 
121 string MULTIPLY_INT(string str1, string str2);
122 
123 int sign = 1; //sign 为符号位
124 
125 string str;
126 
127 if(str2[0] == '-')
128 
129 str = ADD_INT(str1, str2.erase(0, 1));
130 
131 else {
132 
133 int res = compare(str1, str2);
134 
135 if(res == 0) return "0";
136 
137 if(res < 0) {
138 
139 sign = -1;
140 
141 string temp = str1;
142 
143 str1 = str2;
144 
145 str2 = temp;
146 
147 }
148 
149 string::size_type tempint;
150 
151 tempint = str1.size() - str2.size();
152 
153 for(int i = str2.size() - 1; i >= 0; i--) {
154 
155 if(str1[i + tempint] < str2[i]) {
156 
157 str1[i + tempint - 1] = char(int(str1[i + tempint - 1]) - 1);
158 
159 str = char(str1[i + tempint] - str2[i] + 58) + str;
160 
161 }
162 
163 else
164 
165 str = char(str1[i + tempint] - str2[i] + 48) + str;
166 
167 }
168 
169 for(i = tempint - 1; i >= 0; i--)
170 
171 str = str1[i] + str;
172 
173 }
174 
175 //去除结果中多余的前导0
176 
177 str.erase(0, str.find_first_not_of('0'));
178 
179 if(str.empty()) str = "0";
180 
181 if((sign == -1) && (str[0] != '0'))
182 
183 str = "-" + str;
184 
185 return str;
186 
187 }
188 
189  
190 
191 //高精度乘法
192 
193 string MULTIPLY_INT(string str1, string str2)
194 
195 {
196 
197 int sign = 1; //sign 为符号位
198 
199 string str;
200 
201 if(str1[0] == '-') {
202 
203 sign *= -1;
204 
205 str1 = str1.erase(0, 1);
206 
207 }
208 
209 if(str2[0] == '-') {
210 
211 sign *= -1;
212 
213 str2 = str2.erase(0, 1);
214 
215 }
216 
217 int i, j;
218 
219 string::size_type l1, l2;
220 
221 l1 = str1.size(); l2 = str2.size();
222 
223 for(i = l2 - 1; i >= 0; i --) { //实现手工乘法
224 
225 string tempstr;
226 
227 int int1 = 0, int2 = 0, int3 = int(str2[i]) - 48;
228 
229 if(int3 != 0) {
230 
231 for(j = 1; j <= (int)(l2 - 1 - i); j++)
232 
233 tempstr = "0" + tempstr;
234 
235 for(j = l1 - 1; j >= 0; j--) {
236 
237 int1 = (int3 * (int(str1[j]) - 48) + int2) % 10;
238 
239 int2 = (int3 * (int(str1[j]) - 48) + int2) / 10;
240 
241 tempstr = char(int1 + 48) + tempstr;
242 
243 }
244 
245 if(int2 != 0) tempstr = char(int2 + 48) + tempstr;
246 
247 }
248 
249 str = ADD_INT(str, tempstr);
250 
251 }
252 
253 //去除结果中的前导0
254 
255 str.erase(0, str.find_first_not_of('0'));
256 
257 if(str.empty()) str = "0";
258 
259 if((sign == -1) && (str[0] != '0'))
260 
261 str = "-" + str;
262 
263 return str;
264 
265 }
266 
267 //高精度除法
268 
269 string DIVIDE_INT(string str1, string str2, int flag)
270 
271 {
272 
273 //flag = 1时,返回商; flag = 0时,返回余数
274 
275 string quotient, residue; //定义商和余数
276 
277 int sign1 = 1, sign2 = 1;
278 
279 if(str2 == "0") { //判断除数是否为0
280 
281 quotient = "ERROR!";
282 
283 residue = "ERROR!";
284 
285 if(flag == 1) return quotient;
286 
287 else return residue;
288 
289 }
290 
291 if(str1 == "0") { //判断被除数是否为0
292 
293 quotient = "0";
294 
295 residue = "0";
296 
297 }
298 
299 if(str1[0] == '-') {
300 
301 str1 = str1.erase(0, 1);
302 
303 sign1 *= -1;
304 
305 sign2 = -1;
306 
307 }
308 
309 if(str2[0] == '-') {
310 
311 str2 = str2.erase(0, 1);
312 
313 sign1 *= -1;
314 
315 }
316 
317 int res = compare(str1, str2);
318 
319 if(res < 0) {
320 
321 quotient = "0";
322 
323 residue = str1;
324 
325 }else if(res == 0) {
326 
327 quotient = "1";
328 
329 residue = "0";
330 
331 }else {
332 
333 string::size_type l1, l2;
334 
335 l1 = str1.size(); l2 = str2.size();
336 
337 string tempstr;
338 
339 tempstr.append(str1, 0, l2 - 1);
340 
341 //模拟手工除法
342 
343 for(int i = l2 - 1; i < l1; i++) {
344 
345 tempstr = tempstr + str1[i];
346 
347 for(char ch = '9'; ch >= '0'; ch --) { //试商
348 
349 string str;
350 
351 str = str + ch;
352 
353 if(compare(MULTIPLY_INT(str2, str), tempstr) <= 0) {
354 
355 quotient = quotient + ch;
356 
357 tempstr = MINUS_INT(tempstr, MULTIPLY_INT(str2, str));
358 
359 break;
360 
361 }
362 
363 }
364 
365 }
366 
367 residue = tempstr;
368 
369 }
370 
371 //去除结果中的前导0
372 
373 quotient.erase(0, quotient.find_first_not_of('0'));
374 
375 if(quotient.empty()) quotient = "0";
376 
377 if((sign1 == -1) && (quotient[0] != '0'))
378 
379 quotient = "-" + quotient;
380 
381 if((sign2 == -1) && (residue[0] != '0'))
382 
383 residue = "-" + residue;
384 
385 if(flag == 1) return quotient;
386 
387 else return residue;
388 
389 }
390 
391  
392 
393 //高精度除法,返回商
394 
395 string DIV_INT(string str1, string str2)
396 
397 {
398 
399 return DIVIDE_INT(str1, str2, 1);
400 
401 }
402 
403 //高精度除法,返回余数
404 
405 string MOD_INT(string str1, string str2)
406 
407 {
408 
409 return DIVIDE_INT(str1, str2, 0);
410 
411 }
412 
413  
414 
415 int main()
416 
417 {
418 
419 char ch;
420 
421 string s1, s2, res;
422 
423 while(cin >> ch) {
424 
425 cin >> s1 >> s2;
426 
427 switch(ch) {
428 
429 case '+': res = ADD_INT(s1, s2); break; //高精度加法
430 
431 case '-': res = MINUS_INT(s1, s2); break; //高精度减法
432 
433 case '*': res = MULTIPLY_INT(s1, s2); break; //高精度乘法
434 
435 case '/': res = DIV_INT(s1, s2); break; //高精度除法,返回商
436 
437 case 'm': res = MOD_INT(s1, s2); break; //高精度除法,返回余数
438 
439 default : break;
440 
441 }
442 
443 cout << res << endl;
444 
445 }
446 
447 return(0);
448 
449 }