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

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

版本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 }

为方便理解,特画出版本二的程序运行流程图(为图示清晰,省略了函数形参):

参考资料来源说明:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏nnngu

Java面试题库及答案解析

1、面向对象编程(OOP)有哪些优点? 代码开发模块化,更易维护和修改。 代码复用。 增强代码的可靠性和灵活性。 增加代码的可理解性。 2、面向对象编程有哪些特...

35750
来自专栏NetCore

.NET反射、委托技术与设计模式

1 反射技术与设计模式   反射(Reflection)是。NET中的重要机制,通过放射,可以在运行时获得。NET中每一个类型(包括类、结构、委托、接口和枚举...

24590
来自专栏xiaoxi666的专栏

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

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

10010
来自专栏微信公众号:Java团长

Java动态代理原理及解析

代理模式是一种常用的设计模式,其目的就是为其他对象提供一个代理以控制对某个真实对象的访问。代理类负责为委托类预处理消息,过滤消息并转发消息,以及进行消息被委托类...

10540
来自专栏xx_Cc的学习总结专栏

C - 基础总结

367110
来自专栏Linyb极客之路

并发编程之Synchronized关键字

一、Synchronized的基本使用 Synchronized是Java中解决并发问题的一种最常用的方法,也是最简单的一种方法。Synchronized的作...

30160
来自专栏逆向技术

C++反汇编第二讲,不同作用域下的构造和析构的识别

               C++反汇编第二讲,不同作用域下的构造和析构的识别 目录大纲:   1.全局(静态)对象的识别,(全局静态全局一样的,都是编译期间...

208100
来自专栏Java帮帮-微信公众号-技术文章全总结

通过字节码分析JDK8中Lambda表达式编译及执行机制【面试+工作】

在Class文件中,方法调用即是对常量池(ConstantPool)属性表中的一个符号引用,在类加载的解析期或者运行时才能确定直接引用。

26110
来自专栏编程

经常出现却又容易被忽略的Java SE面试题 必看

在面试的过程中往往会遇到javase的题目,这个又是容易被忽略,来看一下是哪些呢? 1)运行时异常,非运行时异常。 运行时异常可进行处理,也可不进行处理。非运行...

22050
来自专栏liulun

Nim教程【十五】【完结】

模版 模版是Nim语言中的抽象语法树,它是一种简单的替换机制,在编译期被处理 这个特性使Nim语言可以和C语言很好的运行在一起 像调用一个方法一样调用一个模版 ...

24080

扫码关注云+社区

领取腾讯云代金券