• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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 }

 

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

 

 

参考资料来源说明:

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均可),包含合法性检查:http://www.cnblogs.com/xiaoxi666/p/7272255.html

【模板小程序】 十进制大数除法(不含小数):http://www.cnblogs.com/xiaoxi666/p/7275353.html


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
微信小程序“满月”:尝鲜之后你还用过它吗?发布时间:2022-07-18
下一篇:
微信小程序主题皮肤切换(switch开关)发布时间:2022-07-18
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap