{??
1. ????int?size_a=a.size();??
2. ????int?size_b=b.size();??
3. ????for?(int?i=size_a-1;i>=0;i--)??
4. ????{??
5. ????????tempcheng.a.push_back(a[i]-'0');??
6. ????}??
7. int?i=size_b-1;i>=0;i--)??
8. ????????tempcheng.b.push_back(b[i]-'0');??
9. }??

（3）处理进位，消除多余的0；代码为：

void?multiply(bigcheng?&tempcheng,87); font-weight:bold; background-color:inherit">int>?&result_num)??
1. for?(unsigned?int?i=0;i<tempcheng.a.size();i++)??
2. ????????int?j=0;j<tempcheng.b.size();j++)??
3. ????????{??
4. ????????????result_num[i+j]+=(tempcheng.a[i])*(tempcheng.b[j]);??
5. ????????}??
6. ????}??
7. ????int?i=result_num.size()-1;i>=0;i--)??
8. ????{??
9. ????????if?(result_num[i]!=0)??
10. ????????{??
11. ????????????break;??
12. ????????}??
13. else??
14. ????????????result_num.pop_back();??
15. int?c=0;??
16. int?i=0;i<result_num.size();i++)//处理进位??
17. ????????result_num[i]+=c;??
18. ????????c=result_num[i]/10;??
19. ????????result_num[i]=result_num[i]%10;??
20. if?(c!=0)??
21. ????????result_num.push_back(c);??
22. }??

（4）转换并反转，将计算结果转换为字符串并反转。

{???int?size=result_num.size();??
1. int?i=0;i<result_num.size();i++)??
2. ????????tempcheng.result_str.push_back(char(result_num[size-1-i]+'0'));??
3. 
   主函数为：

   
   int?main()??
   1. ???????bigcheng?tempcheng;??
   2. ????string?a,b;??
   3. ????cin>>a>>b;??
   4. ????chartonum(a,b,tempcheng);??
   5. int>?resultnum(a.size()+b.size(),0);??
   6. ????multiply(tempcheng,resultnum);??
   7. ????numtochar(tempcheng,resultnum);??
   8. ????cout<<tempcheng.result_str<<endl;??
   9. ????system("pause");??
   10. return?0;??
   11. }??

   
   ?????上面的思路还是很清晰的，但代码有些过长，考虑优化如下：
   

   （1）上述思路是先转换反转，其实无需先将全部字符串转换为数字的，可即用即转，节约空间；

   （2）无需等到逐位相乘都结束，才处理进位，可即乘即进；

   （3）无需等到所有结果出来后，将结果转换为字符，可即乘即转。

   ? ? ?优化后时间复杂度不变，但节省了空间，代码更简洁。如下：

   

   #include?<assert.h>??
   1. namespace?std;??
   2. struct?bigcheng2??
   3. ????string?a;??
   4. ????string?b;??
   5. ????string?result_str;??
   6. };??
   7. void?reverse_data(?string?&data)；//字符串反转??
   8. void?multiply2(bigcheng2?&tempcheng2);//字符串模拟相乘??

   字符串反转：

   
   void?reverse_data(?string?&data)??
   1. char?temp?=?'0';??
   2. int?start=0;??
   3. int?end=data.size()-1;??
   4. ????assert(?data.size()&&?start?<=?end?);??
   5. while?(?start?<?end?)??
   6. ????????temp?=?data[start];??
   7. ????????data[start++]?=?data[end];??
   8. ????????data[end--]?=?temp;??
   9. 
      两数相乘：

      
      void?multiply2(bigcheng2?&tempcheng2)??
      1. ????reverse_data(tempcheng2.a); ????reverse_data(tempcheng2.b);??
      2. ????string?temp(tempcheng2.a.size()+tempcheng2.b.size(),'0');//将temp全部初始化为0字符??
      3. int?i=0;i<tempcheng2.a.size();i++)??
      4. ????????unsigned?int?j;??
      5. for?(j=0;j<tempcheng2.b.size();j++)??
      6. ????????????c+=temp[i+j]-'0'+(tempcheng2.a[i]-'0')*(tempcheng2.b[j]-'0');//注意temp[i+j]可能保存有上一次计算的结果??
      7. ????????????temp[i+j]=(c%10)+'0';//将结果转换为字符??
      8. ????????????c=c/10;??
      9. while(c)??
      10. ????????????temp[i+j++]+=c%10;//temp里已存字符??
      11. ????????????c=c/10;??
      12. int?i=temp.size()-1;i>=0;i--)??
      13. if?(temp[i]!='0')??
      14. ????????????break;??
      15. ????????????temp.pop_back();??
      16. ????reverse_data(temp);//结果?字á?符¤?串??反¤??转áa??
      17. ????tempcheng2.result_str=temp;??
      18. 主函数：

          
          ???????bigcheng2?tempcheng2;??
          1. ???????string?a,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> ???????cin>>a>>b;??
          2. ???????tempcheng2.a=a;??
          3. ???????tempcheng2.b=b;??
          4. ???????multiply2(tempcheng2);??
          5. ???????cout<<tempcheng2.result_str<<endl;??
          6. ???????system("pause");??
          7. ???????return?0;??
          8. }??

          3.2 移位进位法

          ? ? ? ?移位进位法也是普通的大数相乘算法，其时间复杂度也为O（N2）其基本思路参考博客5，简述如下：

          　　按照乘法的计算过程来模拟计算：

          　　　　 ? 1 2

          　　　　× 3 6

          　　 ---------- ---- 其中，上标数字为进位数值。

          　　　　　7¹?2 ?--- 在这个计算过程中，2×6=12。本位保留2，进位为1.这里是一个简单的计算过程，如果在高位也需要进位的情况下，如何处理？

          　　　　3 6

          　 ? -----------

          　　　　4¹3 ?2

          ? ? ? ? 其代码优化如下：

          
          void?reverse_data(?string?&data);void?compute_value(?string?lhs,string?rhs,string?&result?);??
          1. }??
          2. ????reverse_data(lhs);??
          3. ????reverse_data(rhs);??
          4. int?i?=?0,?j?=?0,?res_i?=?0;??
          5. int?tmp_i?=?0;??
          6. int?carry?=?0;??
          7. ??
          8. for?(?i?=?0;?i!=lhs.size();?++i,?++tmp_i?)??
          9. ????????res_i?=?tmp_i;??//在每次计算时，结果存储的位需要增加??
          10. for?(?j?=?0;?j!=?rhs.size();?++j?)??
          11. ????????????carry?+=?(?result[res_i]?-?'0'?)+(lhs[i]?-?'0')?*?(rhs[j]?-?'0');//此处注意，每次计算并不能保证以前计算结果的进位都消除，?并且以前的计算结果也需考虑。??
          12. ????????????result[res_i++]?=?(?carry?%?10?+?'0'?);??
          13. ????????????carry?/=?10;??
          14. while?(carry)//乘数的一次计算完成，可能存在有的进位没有处理??
          15. ????????????result[res_i++]?=?(carry?%?10?+?'0');??
          16. ????????????carry?/=?10;??
          17. int?i=result.size()-1;i>=0;i--)??
          18. if?(result[i]!='0')??
          19. else??
          20. ????????????result.pop_back();??
          21. ????????reverse_data(result);??
          22. int?main()??
          23. ????string?result(a.size()+b.size(),'0');??
          24. ????compute_value(a,result);??
          25. ????cout<<result<<endl;??

          26. 3.3大数相乘优化

              3.2 移位进位法中的反转字符串其实不必要的，只需从数组的后面开始计算存储即可，下面实现代码：
              

              [cpp]? view plain copy

              

              

              char*?bigcheng1(char?*p1,char?*p2)??
              1. {??
              2. if?(check(p1)||check(p2))??
              3. throw?exception("Invalid?input!");??
              4. int?index1=strlen(p1)-1,index2=strlen(p2)-1,index3,carry=0;??
              5. char?*p3=new?char[index1+index2+3];??
              6. ????memset(p3,'0',index1+index2+2);??
              7. ????p3[index1+index2+2]='';??
              8. for?(;index2>=0;--index2)??
              9. ????{??
              10. for?(index1=strlen(p1)-1;index1>=0;--index1)??
              11. ????????{??
              12. ????????????int?num=p3[index1+index2+1]-'0'+(p1[index1]-'0')*(p2[index2]-'0')+carry;//p3[index1+index2+1]-'0',注意都是数字参与运算??
              13. ????????????p3[index1+index2+1]=num%10+'0';??
              14. ????????????carry=num/10;??
              15. ????????}??
              16. ????????int?i=0;??
              17. while(carry)??
              18. ????????{??
              19. ????????????p3[index1+index2+1+(i--)]+=(carry%10);//注意字符和字符串的不同??
              20. ????????????carry/=10;??
              21. ????????index3=index1+index2+1+i;??
              22. ????}??
              23. while(index3>=0)??
              24. ????????p3[index3--]='0';??
              25. return?p3;??
              26. }??
              
              
              

              或者下面这样，其实是一样的，下面的相加、相减、相除一样的思路啦

              
              

              

              char*?bigcheng(char?*p1,87); font-weight:bold; background-color:inherit">char?*p2)??
              1. if?(check(p1)||check(p2))??
              2. throw?exception("Invalid?input!");??
              3. int?index1=strlen(p1)-1,carry=0;??
              4. char?*p3=new?char[index1+index2+3];??
              5. ????p3[index1+index2+2]='';??
              6. for?(;index2>=0;--index2)??
              7. for?(index1=strlen(p1)-1;index1>=0;--index1)??
              8. int?num=p3[index1+index2+1]-'0'+(p1[index1]-'0')*(p2[index2]-'0')+carry;??
              9. if?(num>=10)??
              10. ????????????{??
              11. ????????????????carry=num/10;??
              12. ????????????????num%=10;??
              13. ????????????}??
              14. else?carry=0;??
              15. ????????????p3[index1+index2+1]=num+'0';??
              16. ????????int?i=0;??
              17. while(carry)??
              18. ????????????p3[index1+index2+1+(i--)]+=(carry%10);//注意字符和字符串的不同??
              19. ????????????carry/=10;??
              20. ????????index3=index1+index2+1+i;??
              21. while(index3>=0)??
              22. ????????p3[index3--]='0';??
              23. return?p3;??
              24. }??
              
              
              

              3.4运行结果

              ? ? ? ? 运行结果如图1、图2所示

              

              ? ?

              ??????????????????? 图1 ? ?

              ?

              

              ????????????????????????????????????????????????????????????????????图2

              
              

              3.5 大数相加

              check合法性校验，校验字符串中是否有非数字。

              

              bool?check(char?*p)??
              1. if?(!p)??
              2. return?1;??
              3. int?i=0;??
              4. while(p[i]!='')???
              5. ????{??
              6. if?(p[i]<'0'||p[i]>'9')??
              7. return?1;??
              8. ????????}??
              9. else?++i;??
              10. ????}??
              11. return?0;//合法??
              12. }??

              
              

              
              char*?bigadd(char?*p2)??
              1. if?(check(p1)||check(p2))??
              2. throw?exception("Invalid?input!");??
              3. int?len1=strlen(p1);??
              4. int?len2=strlen(p2);??
              5. int?len3=max(len1,len2)+1;??
              6. char[len3+1];??
              7. ????p3[len3]='';??
              8. int?index1=len1-1,index2=len2-1,index3=len3-1;??
              9. int?carry=0;??
              10. while(index1>=0&&index2>=0)??
              11. int?num=p1[index1--]-'0'+p2[index2--]-'0'+carry;??
              12. if?(num>=10)??
              13. ????????????carry=1;??
              14. ????????????num-=10;??
              15. else??
              16. ????????????carry=0;??
              17. ????????p3[index3--]=num+'0';??
              18. while(index1>=0)??
              19. int?num=p1[index1--]-'0'+carry;??
              20. while(index2>=0)??
              21. int?num=p1[index2--]-'0'+carry;??
              22. ????p3[index3]=carry?'1':'0';??
              23. return?p3;??
              24. }??
              
              
              

              3.6大数相减

              
              char*?bigminus(char?*p2,87); font-weight:bold; background-color:inherit">bool?&flag)??
              1. ????flag=0;//正数默认??
              2. if?(strlen(p1)<strlen(p2))??
              3. ????????flag=1;??
              4. char?*tmp=p1;??
              5. ??????????????p1=p2;??
              6. ??????????????p2=tmp;??
              7. else?if?(strlen(p1)==strlen(p2))??
              8. if?(strcmp(p1,p2)<0)??
              9. ????????????flag=1;??
              10. ????????????char?*tmp=p1;??
              11. ????????????p1=p2;??
              12. ????????????p2=tmp;??
              13. char[strlen(p1)+2];??
              14. ????p3[index3+1]='';??
              15. int?carry=0;??
              16. while(index1>=0&&index2>=0)??
              17. int?num=p1[index1--]-p2[index2--]-carry;??
              18. if?(num<0)??
              19. ????????????carry=1;??
              20. ????????????num+=10;??
              21. else?carry=0;??
              22. int?num=p1[index1--]-'0'-carry;??
              23. if?(num<0)??
              24. ????????????num+=10;??
              25. else?carry=0;??
              26. ????????p3[index3--]=num+'0'?;??
              27. int?i=0;??
              28. while(p3[i]=='0')?++i;??
              29. if?(flag)??
              30. ??????????p3[i-1]='-';??
              31. 3.7大数相除

                  
                  char*?bigchu(char?*p2)//大数除，有问题，但思想是对的，关键怎么处理前面多样的0??
                  1. bool?flag=0;??
                  2. char?*tmp1=char[strlen(p2)-strlen(p2)+1];??
                  3. char?*tmp0=tmp1,*p3,*p4;??
                  4. ????memset(tmp1,strlen(p2)-strlen(p2));??
                  5. ????tmp1[strlen(p2)-strlen(p2)]='';??
                  6. char?*tmp2=bigminus(p1,p2,flag);??
                  7. ??????????p1=tmp2;???
                  8. while(!flag)??
                  9. ????{???
                  10. ??
                  11. ????????p3=bigadd(tmp0,"1");??
                  12. ????????tmp1=tmp0;??
                  13. ????????tmp0=p3;??????????
                  14. delete?[]tmp1;??
                  15. ??
                  16. ????????tmp2=bigminus(p1,flag);??
                  17. ????????p4=p1;??
                  18. ????????p1=tmp2;???
                  19. delete?[]p4;??
                  20. return?tmp0;??
                  21. ??????
                  22. }??
                  
                  

                  3.8主函数测试

                  
                  int?_tmain(int?argc,?_TCHAR*?argv[])??
                  1. ????string?a,b;??
                  2. while(1)??
                  3. ????????cin>>a>>b;??
                  4. char?*p1=const_cast<char?*>(a.c_str());??
                  5. char?*p2=char?*>(b.c_str());??
                  6. char?*p3=bigadd(p1,p2);??
                  7. char?*p4=bigminus(p1,flag);??
                  8. char?*p5=bigcheng1(p1,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> ????????//char?*p6=bigchu(p1,p2);??
                  9. //cout<<p3<<endl<<endl<<p4<<endl<<endl<<p5<<endl<<endl;??
                  10. ????????cout<<p1<<endl<<"bigadd"<<endl<<p2<<endl<<"equal:?";??
                  11. ????????printnum(p3);??
                  12. ????????cout<<endl;??
                  13. ????????cout<<p1<<endl<<"bigminus"<<endl<<p2<<endl<<"equal:?";??
                  14. ????????printnum(p4);??
                  15. ????????cout<<endl;??
                  16. ????????cout<<p1<<endl<<"bigcheng1"<<endl<<p2<<endl<<"equal:?";??
                  17. ????????printnum(p5);??
                  18. ????system("pause");??
                  19. return?0;??
                  20. }??
                  
                  测试结果如下：

                  

                  
                  

                  欢迎各位交流批评指正^_^····

                  （编辑：李大同）

                  【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!