成都网站建设sntuu,网站建设网络推广的好处,网络销售推广是做什么的具体,免费制作地图app1 /*2 本程序说明#xff1a;3 4 大数乘法(模拟乘法操作#xff0c;取其中一个字符串#xff0c;每一位分别相乘#xff0c;最后移位加起来)5 6 时间复杂度#xff1a;O(k1*k2),k1和k2分别为两字符串长度7 空间复杂度#xff1a;O(1)8 9 */10 11 #include iostream3 4 大数乘法(模拟乘法操作取其中一个字符串每一位分别相乘最后移位加起来)5 6 时间复杂度O(k1*k2),k1和k2分别为两字符串长度7 空间复杂度O(1)8 9 */10 11 #include iostream12 #include string13 #include algorithm14 #include vector15 16 using namespace std;17 18 //输入数据合法性检查,数字必须在0-9范围内19 bool IsVaild(const string num1,const string num2)20 {21 for(size_t i0;inum1.length();i)22 {23 if(0i -num1[0] inum1.length()){};//首位可以是-,这里直接加i,继续判断24 if(!(num1[i]0 num1[i]-09))25 return false;26 }27 for(size_t i0;inum2.length();i)28 {29 if(0i -num2[0] inum2.length()){};//首位可以是-,这里直接加i,继续判断30 if(!(num2[i]0 num2[i]-09))31 return false;32 }33 return true;34 }35 36 //辅助函数符号为两正和两负时调用,这里的num1和num2不包含符号位37 string _greatNumberAdd(string num1,string num2)38 {39 const size_t len1num1.length();40 const size_t len2num2.length();41 const size_t nlen1len2 ? len1 :len2;42 reverse(num1.begin(),num1.end());43 reverse(num2.begin(),num2.end());44 45 string result;46 int carry0;//进位47 for(size_t i0;in;i)48 {49 const int num1i ilen1 ? num1[i]-0 :0;50 const int num2i ilen2 ? num2[i]-0 :0;51 const int val (num1inum2icarry)%10;52 carry(num1inum2icarry)/10;53 result.insert(result.begin(),val0);54 }55 if(1carry)//若最前面有进位则插入156 result.insert(result.begin(),1);57 58 return result;59 }60 61 //大数相乘辅助函数执行实际的乘法62 string _greatNumberMulti(string num1,string num2)63 {64 const size_t len1num1.length();65 const size_t len2num2.length();66 67 reverse(num1.begin(),num1.end());68 reverse(num2.begin(),num2.end());69 70 string result;71 for(size_t i0;ilen1;i)72 {73 string tmp_Add;74 int carry0;//进位75 for(size_t j0;jlen2;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(),val0);80 }81 if(carry0)//若最前面有进位则插入82 tmp_Add.insert(tmp_Add.begin(),carry0);83 for(size_t _0;_i;_)//模拟乘法操作的补零84 tmp_Add0;85 result_greatNumberAdd(result,tmp_Add);86 }87 return result;88 }89 90 //大数相乘入口先判断符号两正、两负、一正一负再调用辅助函数91 string greatNumberMulti(string num1,string num2)92 {93 /*******************判断正负号开始***********************/94 int flag0;//0两正1一正一负2两负95 if(-num1[0])96 {97 num1.erase(num1.begin());98 flag1;99 }
100 if(-num2[0])
101 {
102 num2.erase(num2.begin());
103 //若1flag则说明num1也为负数即为两负否则只有num2为负数
104 flag (1flag) ? 2 : 1;
105 }
106 /*******************判断正负号结束***********************/
107
108 string result_greatNumberMulti(num1,num2);
109
110 int firstIndex_notEqualTo_00;//找出第一个不为0的位置如果前面均为0则抹去
111 for(;firstIndex_notEqualTo_0result.length();firstIndex_notEqualTo_0)
112 {
113 if(result[firstIndex_notEqualTo_0]!0)
114 break;
115 }
116 if(firstIndex_notEqualTo_00)//如果前面均为0则抹去
117 result.erase(0,firstIndex_notEqualTo_0);
118 if(result.empty())//如果两个数相加结果为0最后处理完就为空了因此直接输出0
119 {
120 result0;
121 return result;
122 }
123
124 if(1flag)//若一正一负且结果不为0在最前面添加-
125 result.insert(result.begin(),-);
126
127 return result;
128 }
129
130 int main()
131 {
132 string num1,num2;
133 while(cinnum1num2)
134 {
135 if(IsVaild(num1,num2))
136 coutgreatNumberMulti(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 iostream12 #include string13 #include algorithm14 #include vector15 16 using namespace std;17 18 //输入数据合法性检查,数字必须在0-9范围内19 bool IsVaild(const string num1,const string num2)20 {21 for(size_t i0;inum1.length();i)22 {23 if(0i -num1[0] inum1.length()){};//首位可以是-,这里直接加i,继续判断24 if(!(num1[i]0 num1[i]-09))25 return false;26 }27 for(size_t i0;inum2.length();i)28 {29 if(0i -num2[0] inum2.length()){};//首位可以是-,这里直接加i,继续判断30 if(!(num2[i]0 num2[i]-09))31 return false;32 }33 return true;34 }35 36 //辅助函数符号为两正和两负时调用,这里的num1和num2不包含符号位37 string _greatNumberAdd(string num1,string num2)38 {39 const size_t len1num1.length();40 const size_t len2num2.length();41 const size_t nlen1len2 ? len1 :len2;42 reverse(num1.begin(),num1.end());43 reverse(num2.begin(),num2.end());44 45 string result;46 int carry0;//进位47 for(size_t i0;in;i)48 {49 const int num1i ilen1 ? num1[i]-0 :0;50 const int num2i ilen2 ? num2[i]-0 :0;51 const int val (num1inum2icarry)%10;52 carry(num1inum2icarry)/10;53 result.insert(result.begin(),val0);54 }55 if(1carry)//若最前面有进位则插入156 result.insert(result.begin(),1);57 58 return result;59 }60 61 //大数相乘辅助函数执行实际的乘法62 vectorstring _greatNumberMulti(string num1,string num2)63 {64 65 const size_t len1num1.length();66 const size_t len2num2.length();67 68 reverse(num1.begin(),num1.end());69 reverse(num2.begin(),num2.end());70 71 vectorstring result;72 for(size_t i0;ilen1;i)73 {74 string tmp_Add;75 int carry0;//进位76 for(size_t j0;jlen2;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(),val0);81 }82 if(carry0)//若最前面有进位则插入83 tmp_Add.insert(tmp_Add.begin(),carry0);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 flag0;//0两正1一正一负2两负96 if(-num1[0])97 {98 num1.erase(num1.begin());99 flag1;
100 }
101 if(-num2[0])
102 {
103 num2.erase(num2.begin());
104 //若1flag则说明num1也为负数即为两负否则只有num2为负数
105 flag (1flag) ? 2 : 1;
106 }
107 /*******************判断正负号结束***********************/
108
109 vectorstring result_greatNumberMulti(num1,num2);
110
111
112 string result_output;
113
114 for(int i0;iresult.size()-1;i)//模拟乘法操作的补零
115 {
116 for(int tmp0;tmpresult.size()-1-i;tmp)
117 result[i]0;
118 }
119 for(int i0;iresult.size();i)
120 {
121 result_output_greatNumberAdd(result_output,result[i]);
122 }
123
124 int firstIndex_notEqualTo_00;//找出第一个不为0的位置如果前面均为0则抹去
125 for(;firstIndex_notEqualTo_0result_output.length();firstIndex_notEqualTo_0)
126 {
127 if(result_output[firstIndex_notEqualTo_0]!0)
128 break;
129 }
130 if(firstIndex_notEqualTo_00)//如果前面均为0则抹去
131 result_output.erase(0,firstIndex_notEqualTo_0);
132 if(result_output.empty())//如果两个数相加结果为0最后处理完就为空了因此直接输出0
133 {
134 result_output0;
135 return result_output;
136 }
137
138 if(1flag)//若一正一负且结果不为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(cinnum1num2)
149 {
150 if(IsVaild(num1,num2))
151 coutgreatNumberMulti(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转载于:https://www.cnblogs.com/xiaoxi666/p/7272255.html
