【模板小程序】 十进制大数相乘，正数、负数、0均可，包含合法性检查
1 /*
2 本程序说明：
3
4 大数乘法(模拟乘法操作，取其中一个字符串，每一位分别相乘，最后移位加起来)
5
6 时间复杂度：O(k1*k2),k1和k2分别为两字符串长度
7 空间复杂度：O(1)
8
9 */
10
11 #include <iostream>
12 #include <string>
13 #include <algorithm>
14 #include <vector>
15
16 using namespace std;
17
18 //输入数据合法性检查,数字必须在0-9范围内
19 bool IsVaild(const string& num1,const string& num2)
20 {
21 for(size_t i=0;i<num1.length();++i)
22 {
23 if(0==i && '-'==num1[0] && ++i<num1.length()){};//首位可以是'-',这里直接加i,继续判断
24 if(!(num1[i]>='0' && num1[i]-'0'<='9'))
25 return false;
26 }
27 for(size_t i=0;i<num2.length();++i)
28 {
29 if(0==i && '-'==num2[0] && ++i<num2.length()){};//首位可以是'-',这里直接加i,继续判断
30 if(!(num2[i]>='0' && num2[i]-'0'<='9'))
31 return false;
32 }
33 return true;
34 }
35
36 //辅助函数：符号为两正和两负时调用,这里的num1和num2不包含符号位
37 string _greatNumberAdd(string num1,string num2)
38 {
39 const size_t len1=num1.length();
40 const size_t len2=num2.length();
41 const size_t n=len1>len2 ? len1 :len2;
42 reverse(num1.begin(),num1.end());
43 reverse(num2.begin(),num2.end());
44
45 string result;
46 int carry=0;//进位
47 for(size_t i=0;i<n;++i)
48 {
49 const int num1i = i<len1 ? num1[i]-'0' :0;
50 const int num2i = i<len2 ? num2[i]-'0' :0;
51 const int val = (num1i+num2i+carry)%10;
52 carry=(num1i+num2i+carry)/10;
53 result.insert(result.begin(),val+'0');
54 }
55 if(1==carry)//若最前面有进位，则插入'1'
56 result.insert(result.begin(),'1');
57
58 return result;
59 }
60
61 //大数相乘辅助函数（执行实际的乘法）
62 string _greatNumberMulti(string num1,string num2)
63 {
64 const size_t len1=num1.length();
65 const size_t len2=num2.length();
66
67 reverse(num1.begin(),num1.end());
68 reverse(num2.begin(),num2.end());
69
70 string result;
71 for(size_t i=0;i<len1;++i)
72 {
73 string tmp_Add;
74 int carry=0;//进位
75 for(size_t j=0;j<len2;++j)
76 {
77 const int val = ((num1[i]-'0')*(num2[j]-'0')+carry)%10;
78 carry=((num1[i]-'0')*(num2[j]-'0')+carry)/10;
79 tmp_Add.insert(tmp_Add.begin(),val+'0');
80 }
81 if(carry>0)//若最前面有进位，则插入
82 tmp_Add.insert(tmp_Add.begin(),carry+'0');
83 for(size_t _=0;_<i;++_)//模拟乘法操作的补零
84 tmp_Add+="0";
85 result=_greatNumberAdd(result,tmp_Add);
86 }
87 return result;
88 }
89
90 //大数相乘入口，先判断符号（两正、两负、一正一负），再调用辅助函数
91 string greatNumberMulti(string num1,string num2)
92 {
93 /*******************判断正负号开始***********************/
94 int flag=0;//0：两正；1：一正一负；2：两负
95 if('-'==num1[0])
96 {
97 num1.erase(num1.begin());
98 flag=1;
99 }
100 if('-'==num2[0])
101 {
102 num2.erase(num2.begin());
103 //若1==flag，则说明num1也为负数，即为两负；否则只有num2为负数
104 flag= (1==flag) ? 2 : 1;
105 }
106 /*******************判断正负号结束***********************/
107
108 string result=_greatNumberMulti(num1,num2);
109
110 int firstIndex_notEqualTo_0=0;//找出第一个不为0的位置（如果前面均为0，则抹去）
111 for(;firstIndex_notEqualTo_0<result.length();++firstIndex_notEqualTo_0)
112 {
113 if(result[firstIndex_notEqualTo_0]!='0')
114 break;
115 }
116 if(firstIndex_notEqualTo_0>0)//（如果前面均为0，则抹去）
117 result.erase(0,firstIndex_notEqualTo_0);
118 if(result.empty())//如果两个数相加结果为0，最后处理完就为空了，因此直接输出"0"
119 {
120 result="0";
121 return result;
122 }
123
124 if(1==flag)//若一正一负且结果不为0，在最前面添加'-'
125 result.insert(result.begin(),'-');
126
127 return result;
128 }
129
130 int main()
131 {
132 string num1,num2;
133 while(cin>>num1>>num2)
134 {
135 if(IsVaild(num1,num2))
136 cout<<greatNumberMulti(num1,num2)<<endl;
137 else
138 cout<<"输入数据不合法"<<endl;
139 }
140 return 0;
141 }以下是调试版本（保存乘法每一步的结果），因此空间复杂度高一点：
1 /*
2 本程序说明：
3
4 大数乘法(模拟乘法操作，取其中一个字符串，每一位分别相乘，最后移位加起来)
5
6 时间复杂度：O(k1*k2),k1和k2分别为两字符串长度
7 空间复杂度：O(k),k为字符串num1的长度
8
9 */
10
11 #include <iostream>
12 #include <string>
13 #include <algorithm>
14 #include <vector>
15
16 using namespace std;
17
18 //输入数据合法性检查,数字必须在0-9范围内
19 bool IsVaild(const string& num1,const string& num2)
20 {
21 for(size_t i=0;i<num1.length();++i)
22 {
23 if(0==i && '-'==num1[0] && ++i<num1.length()){};//首位可以是'-',这里直接加i,继续判断
24 if(!(num1[i]>='0' && num1[i]-'0'<='9'))
25 return false;
26 }
27 for(size_t i=0;i<num2.length();++i)
28 {
29 if(0==i && '-'==num2[0] && ++i<num2.length()){};//首位可以是'-',这里直接加i,继续判断
30 if(!(num2[i]>='0' && num2[i]-'0'<='9'))
31 return false;
32 }
33 return true;
34 }
35
36 //辅助函数：符号为两正和两负时调用,这里的num1和num2不包含符号位
37 string _greatNumberAdd(string num1,string num2)
38 {
39 const size_t len1=num1.length();
40 const size_t len2=num2.length();
41 const size_t n=len1>len2 ? len1 :len2;
42 reverse(num1.begin(),num1.end());
43 reverse(num2.begin(),num2.end());
44
45 string result;
46 int carry=0;//进位
47 for(size_t i=0;i<n;++i)
48 {
49 const int num1i = i<len1 ? num1[i]-'0' :0;
50 const int num2i = i<len2 ? num2[i]-'0' :0;
51 const int val = (num1i+num2i+carry)%10;
52 carry=(num1i+num2i+carry)/10;
53 result.insert(result.begin(),val+'0');
54 }
55 if(1==carry)//若最前面有进位，则插入'1'
56 result.insert(result.begin(),'1');
57
58 return result;
59 }
60
61 //大数相乘辅助函数（执行实际的乘法）
62 vector<string> _greatNumberMulti(string num1,string num2)
63 {
64
65 const size_t len1=num1.length();
66 const size_t len2=num2.length();
67
68 reverse(num1.begin(),num1.end());
69 reverse(num2.begin(),num2.end());
70
71 vector<string> result;
72 for(size_t i=0;i<len1;++i)
73 {
74 string tmp_Add;
75 int carry=0;//进位
76 for(size_t j=0;j<len2;++j)
77 {
78 const int val = ((num1[i]-'0')*(num2[j]-'0')+carry)%10;
79 carry=((num1[i]-'0')*(num2[j]-'0')+carry)/10;
80 tmp_Add.insert(tmp_Add.begin(),val+'0');
81 }
82 if(carry>0)//若最前面有进位，则插入
83 tmp_Add.insert(tmp_Add.begin(),carry+'0');
84
85 result.insert(result.begin(),tmp_Add);
86 }
87
88 return result;
89 }
90
91 //大数相乘入口，先判断符号（两正、两负、一正一负），再调用辅助函数
92 string greatNumberMulti(string num1,string num2)
93 {
94 /*******************判断正负号开始***********************/
95 int flag=0;//0：两正；1：一正一负；2：两负
96 if('-'==num1[0])
97 {
98 num1.erase(num1.begin());
99 flag=1;
100 }
101 if('-'==num2[0])
102 {
103 num2.erase(num2.begin());
104 //若1==flag，则说明num1也为负数，即为两负；否则只有num2为负数
105 flag= (1==flag) ? 2 : 1;
106 }
107 /*******************判断正负号结束***********************/
108
109 vector<string> result=_greatNumberMulti(num1,num2);
110
111
112 string result_output;
113
114 for(int i=0;i<result.size()-1;++i)//模拟乘法操作的补零
115 {
116 for(int tmp=0;tmp<result.size()-1-i;++tmp)
117 result[i]+="0";
118 }
119 for(int i=0;i<result.size();++i)
120 {
121 result_output=_greatNumberAdd(result_output,result[i]);
122 }
123
124 int firstIndex_notEqualTo_0=0;//找出第一个不为0的位置（如果前面均为0，则抹去）
125 for(;firstIndex_notEqualTo_0<result_output.length();++firstIndex_notEqualTo_0)
126 {
127 if(result_output[firstIndex_notEqualTo_0]!='0')
128 break;
129 }
130 if(firstIndex_notEqualTo_0>0)//（如果前面均为0，则抹去）
131 result_output.erase(0,firstIndex_notEqualTo_0);
132 if(result_output.empty())//如果两个数相加结果为0，最后处理完就为空了，因此直接输出"0"
133 {
134 result_output="0";
135 return result_output;
136 }
137
138 if(1==flag)//若一正一负且结果不为0，在最前面添加'-'
139 result_output.insert(result_output.begin(),'-');
140
141 return result_output;
142
143 }
144
145 int main()
146 {
147 string num1,num2;
148 while(cin>>num1>>num2)
149 {
150 if(IsVaild(num1,num2))
151 cout<<greatNumberMulti(num1,num2)<<endl;
152 else
153 cout<<"输入数据不合法"<<endl;
154 }
155 return 0;
156 }同类文章：
【模板小程序】十进制大数相加（正整数版本+整数版本【正负0】），包含合法性检查：http://www.cnblogs.com/xiaoxi666/p/7258312.html
【模板小程序】十进制大数除法（不含小数）：http://www.cnblogs.com/xiaoxi666/p/7275353.html