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
『注:本文來自部落格園“小溪的部落格”,若非聲明均為原創内容,請勿用于商業用途,轉載請注明出處http://www.cnblogs.com/xiaoxi666/』