点击打开链接
方法(一):
关于大数乘法,可以使用数组来模拟小学三年级的乘法竖式计算过程,代码如下:
- #include?"iostream"??
- #include?"string"??
- using?namespace?std;??
- int?main(void)??
- {??
- ????char?str1[1000],str2[1000];??
- ????int?i,j,len1,len2,len;??
- bool?flag=false;??
- ????cout<<"任意两个大数的乘法(用数组来模拟小学三年级的乘法竖式计算过程):"<<endl;??
- ????cout<<"请输入被乘数:";??
- ????gets(str1);??
- ????cout<<"请输入乘数:";??
- ????gets(str2);??
- ????len1=strlen(str1);??
- ????len2=strlen(str2);??
- int?*a=new?int[len1];??
- int?*b=int[len2];??
- ????len=len1*len2+1;??
- int?*result=?int[len];??
- ????for(i=0;i<len;i++)??
- ????????result[i]=0;??
- for(i=0;i<len1;i++)???
- ????????a[i]=str1[len1-1-i]-'0';??
- for(i=0;i<len2;i++)??
- ????????b[i]=str2[len2-1-i]-'0';??
- for(i=0;i<len1;i++)????
- ????{??
- ????????for(j=0;j<len2;j++)??
- ????????????result[i+j]+=a[i]*b[j];??
- ????}??
- ????for(i=0;i<len;i++)?????
- ????{??
- ????????if(result[i]>9)??
- ????????{??
- ????????????result[i+1]+=result[i]/10;??
- ????????????result[i]%=10;??
- ????????}??
- ????cout<<"两个大整数相乘的结果为:";??
- for(i=len-1;i>=0;i--)??
- if(flag)??
- ????????????cout<<result[i];??
- else?if(result[i]!=0)??
- ????????{??
- ????????????cout<<result[i];??
- ????????????flag=true;??
- ????????}??
- ????}??
- ????cout<<endl;??
- delete?[]a;??
- delete?[]b;??
- delete?[]result;??
- ????system("pause");??
- return?0;??
- }??
方法(二):关于大数乘法,可以使用大整数乘法的分治方法:
设X和Y都是n位的整数,现在要计算它们的乘积XY。如果 **利用小学所学的方法,将每两个一位数都进行相乘,最后 **再相加,效率比较低下,乘法需要n^2次。分治的方法可以 **减少乘法的次数,设X被分成2部分A和B,即X=A*10^(n/2)+B **Y也同样处理,即Y=C*10^(n/2)+D. **那么,XY=(A*10^(n/2)+B)*(C*10^(n/2)+D) ?????????????? =AC*10^n+(AD+BC)*10^(n/2)+BD ------>(1) **AD和BC可以利用AC和BD来表示,AD+BC=(A-B)*(D-C)+AC+BD --->(2) **这样(1)的乘法次数由4次减少到3次。
**最后的运算效率会有所提高。
***以上出自?? 计算机算法设计与分析(王晓东) *******/
代码如下:
copy
- #include?"iostream"??
- #include?"list"??
- #include?"string"??
- namespace?std;??
- ??
- ? ? ? ? ? ? ? ? ? ? ? ? ? //选择list容器是因为要进行频繁的插入操作
- list<char>?long_sub(list<char>?clist1,?list<char>?clist2);??
- ??
- char>?long_add(list<char>?clist2)??
- {??
- ????list<char>?rs;???
- ??????
- ????if?(?*(clist1.begin())?==?'-'?&&?*(clist2.begin())?!=?'-'?)??
- ????{??
- ????????clist1.erase(clist1.begin());???
- ????????rs?=?long_sub(clist2,?clist1);??
- ????????return?rs;??
- ????}??
- ??????
- if?(?*(clist1.begin())?!=?'-'?&&?*(clist2.begin())?==?'-'?)??
- ????{??
- ????????clist2.erase(clist2.begin());???
- ????????rs?=?long_sub(clist1,?clist2);??
- return?rs;??
- ????}??
- if?(?*(clist1.begin())?==?'-'?&&?*(clist2.begin())?==?'-'?)??
- ????????clist1.erase(clist1.begin());??
- ????????clist2.erase(clist2.begin());??
- ????????rs?=?long_add(clist1,clist2);??
- ????????rs.push_front('-');??
- if?(?*(clist1.begin())?!=?'-'?&&?*(clist2.begin())?!=?'-'?)??
- ??????????
- ????????int???length1?=?clist1.size();??
- ????????int???length2?=?clist2.size();??
- if(?length1?<?length2?)??
- ????????{??
- ????????????for(int?i=0;?i<(length2?-length1);?++i)??
- ????????????{??
- ????????????????clist1.push_front('0');??
- ????????????}??
- ????????}??
- if?(?length1?>?length2?)??
- ????????{??
- ????????????int?i=0;?i<(length1?-length2);?++i)??
- ????????????{??
- ????????????????clist2.push_front('0');??
- ????????????}??
- ????????}??
- ??
- //整数加法,从低位加起,最低位的进位初始为0??
- int???c=0;???
- int???low;???
- ????????list<char>::iterator?iter1?=?clist1.end();??
- ????????--iter1;??
- char>::iterator?iter2?=?clist2.end();??
- ????????--iter2;??
- for(;?iter1!=clist1.begin()?&&?iter2!=clist2.begin();--iter1,--iter2)??
- ????????????int???num1?=?*iter1?-'0';??
- ????????????int???num2?=?*iter2?-'0';??
- ????????????low?=?(num1+num2+c)%10;??
- ????????????c?=?(num1+num2+c)/10;??
- ????????????rs.push_front(low+'0');//因为list容器里面是char型所以存入的时候要以整数的ascii码存入
- //双方最高位相加的处理??
- int???num1?=?*iter1?-'0';??
- int???num2?=?*iter2?-'0';??
- ????????low?=?(num1+num2+c)%10;??
- ????????c?=?(num1+num2+c)/10;??
- ????????rs.push_front(low+'0');??
- if?(?c?!=?0?)??
- ????????????rs.push_front(c+'0');??
- }??
- ??
- ??
- list<char>?clist2)??
- {??
- ????list<//存放最后的结果??
- //如果一正一负相减,做相加??
- if?(*(clist1.begin())?!=?'-'?&&?*(clist2.begin())?==?'-'?)??
- ????????rs?=?long_add(clist1,0); background-color:inherit">//如果一负一正相减,做相加(添符号)??
- ????????rs???=?long_add(clist1,?clist2);??
- //如果两负相减,作相减??
- if?(?*(clist1.begin())?==?'-'?&&?*(clist2.begin())?==?'-'?)??
- ????????clist1.erase(clist1.begin());??
- ????????clist2.erase(clist2.begin());???
- //如果两正相减,做相减??
- if?(?*(clist1.begin())?!=?'-'?&&?*(clist2.begin())?!=?'-'?)??
- int???sign?=?-1;?????
- //首先保证加数位数相同(填充0)??
- ????????????sign?=?'-';??
- int?i=0;?i<(length2?-length1);?++i)??
- ????????????????clist1.push_front('0');??
- if?(?length1?>?length2?)??
- int?i=0;?i<(length1?-length2);?++i)??
- ????????????????clist2.push_front('0');??
- if?(?*(clist1.begin())?<?*(clist2.begin())?)??
- ????????????sign?=?'-';??
- //整数减法,从低位减起,最低位的借位初始为0??
- int???c?=?0;??(sign?!=?'-'?)??
- ???????????????? ????????????????int???c_new?=?0;???
- ????????????????if?(?num1?<?num2+c?)??
- ????????????????{??
- ????????????????????c_new?=?1;??
- ????????????????????num1?=?num1+10;??
- ????????????????}??
- ????????????????low?=?(num1-num2-c)%10;??
- ????????????????c?=?c_new;??
- ????????????????rs.push_front(low+'0');??
- ??????????????
- ????????????low?=?(num1-num2-c)%10;??
- if?(?low?!=?0?)??
- if?(?sign?==?'-'?)??
- //向高位的借位??
- ????????????????if?(?num2?<?num1+c?)??
- ????????????????{??
- ????????????????????c_new?=?1;??
- ????????????????????num2?=?num2+10;??
- ????????????????}??
- ????????????????low?=?(num2-num1-c)%10;??
- ????????????????c?=?c_new;??
- ????????????????rs.push_front(low+'0');??
- ??????????????
- ????????????low?=?(num2-num1-c)%10;??
- if?(?low?!=?0?)??
- ????????????rs.push_front('-');???
- }??
- /*******大整数乘法*********/??
- char>?long_mul(list<char>?rs;?????
- //递归出口??
- if(clist1.size()?==?1?&&?clist2.size()?==?1)?????
- int?num1?=?*(clist1.begin())-'0';??
- int?num2?=?*(clist2.begin())-'0';??
- int???high?=?(num1*num2)/10;?????
- int???low???=?(num1*num2)%10;?????
- if?(?high?!=?0?)??
- ????????????rs.push_back(high+'0');??
- ????????rs.push_back(low+'0');??
- if?(clist1.size()?==?1?&&?clist2.size()?>?1)??
- int?sign?=?-1;???
- char?high_bit2?=?*(clist2.begin());???
- if?(?high_bit2?==?'-'?)??
- ????????????sign?=?'-';???
- ????????????clist2.erase(clist2.begin());???
- int?length2?=?clist2.size();???
- if?(?length2?>?1?)??
- //对clist2进行拆分??
- ????????????list<char>???clist2_1;?????
- ????????????list<char>???clist2_2;?????
- int?i;??
- char>::iterator?iter;??
- for?(i=0,iter=clist2.begin();?i<length2/2;?++i,++iter)??
- ????????????????clist2_1.push_back(*iter);??
- for(;?iter?!=?clist2.end();?++iter)??
- ????????????????clist2_2.push_back(*iter);??
- char>?rs1;???
- char>?rs2;???
- ????????????rs1?=?long_mul(clist1,?clist2_1);??
- ????????????rs2?=?long_mul(clist1,?clist2_2);??
- //对高位积进行移位(末尾添0)??
- for(?i=0;?i<clist2_2.size();?++i?)??
- ????????????????rs1.push_back('0');??
- ????????????rs?=?long_add(rs1,rs2);???
- if(?sign?==?'-'?)??
- ????????????????rs.push_front('-');??
- else??
- ????????????rs?=?long_mul(clist1,153); background-color:inherit; font-weight:bold">if?(?sign?==?'-'?)??
- ????????????????rs.push_front('-');???
- if?(clist1.size()?>1?&&?clist2.size()?==?1)??
- //最后结果的正负标志,'-'表示负,其他表示正??
- char?high_bit1?=?*(clist1.begin());???
- if?(?high_bit1?==?'-'?)??
- ????????????clist1.erase(clist1.begin());??length1?=?clist1.size();???
- if?(?length1?>?1?)??
- //对clist1进行拆分??
- char>???clist1_1;???>???clist1_2;???
- for(;?iter?!=?clist1.end();?++iter)??
- ????????????????clist1_2.push_back(*iter);??
- //高位部分和clist2的积??
- //低位部分和clist2的积??
- ????????????rs1?=?long_mul(clist1_1,108); list-style:decimal-leading-zero outside; line-height:18px"> ????????????rs2?=?long_mul(clist1_2,153); background-color:inherit; font-weight:bold">for(?i=0;?i<clist1_2.size();?++i?)??
- if?(clist1.size()?>1?&&?clist2.size()?>?1?)??
- char???high_bit1?=?*(clist1.begin());??????high_bit2?=?*(clist2.begin());?????
- if?(?high_bit1?==?'-'???&&?high_bit2?!=?'-'?)??
- ????????????sign?=?'-';?????
- ????????????clist1.erase(clist1.begin());?????
- if?(?high_bit1?!=?'-'?&&?high_bit2?==?'-'?)??
- ????????????sign?=?'-';???
- ????????????clist1.erase(clist1.begin());??
- ????????????clist2.erase(clist2.begin());??????
- //clist2的有效长度??
- if?(?length1?==?1?||?length2?==?1?)??
- if?(?length1?>?1?&&?length2?>?1?)??
- //对clist1和clist2分别进行划分??
- char>?clist1_1;?????
- char>?clist1_2;?????
- char>?clist2_1;?????
- char>?clist2_2;?????
- for(i=0,153); background-color:inherit; font-weight:bold">for(;?iter!=clist1.end();?++iter)??
- for(;?iter!=clist2.end();?++iter)??
- char>?rs_hh;?????
- char>?rs_ll;?????
- ????????????rs_hh?=?long_mul(clist1_1,0); background-color:inherit">//高位相乘结果移位(末尾添0)??
- for(i=0;?i<clist1_2.size()+clist2_2.size();?++i)??
- ????????????????rs_hh.push_back('0');??
- ????????????rs_ll?=?long_mul(clist1_2,?clist2_2);??
- char>?sub1_hl;?????
- char>?sub2_lh;?????
- //两个高位分别移位??
- for(i=0;?i<clist1_2.size();?++i)??
- ????????????????clist1_1.push_back('0');??
- for(i=0;?i<clist2_2.size();?++i)??
- ????????????????clist2_1.push_back('0');??
- ????????????sub1_hl?=?long_sub(clist1_1,?clist1_2);??
- ????????????sub2_lh?=?long_sub(clist2_2,?clist2_1);??
- char>?rs_sub1_sub2;???
- ????????????rs_sub1_sub2?=?long_mul(sub1_hl,?sub2_lh);??
- //把几个乘积的结果加起来??
- ????????????list<char>?tmp1?=?long_add(rs_hh,?rs_ll);??
- ????????????list<char>?tmp2?=?long_add(tmp1,?rs_sub1_sub2);??
- ????????????list<char>?tmp3?=?long_add(tmp2,?rs_hh);??
- ????????????rs?=?long_add(tmp3,?rs_ll);??
- ????????????????rs.push_front('-');??
- void)??
- char>?clist1;??
- char>?clist2;??
- ????cout?<<"请您输入2个乘数:?"<<endl;??
- ????cout?<<"请您输入被乘数:?";??
- ????int?i;??
- ????string???str1;??
- ????cin?>>?str1;??
- for(i=0;?i<str1.size();?++i)??
- if?(str1[i]?>=?'0'?&&?str1[i]?<=?'9'?)??
- ????????????clist1.push_back(str1[i]);??
- else??
- ????????????cout?<<"被乘数中的数字只能为0~9"?<<endl;??
- ????????????exit(1);??
- ????cout?<<"请您输入乘数:?";??
- ????string?str2;??
- ????cin?>>?str2;??
- for(i=0;?i<str2.size();?++i)??
- if?(?str2[i]?>=?'0'?&&?str2[i]?<=?'9'?)??
- ????????????clist2.push_back(str2[i]);??
- ????????????cout?<<"乘数中的数字只能为0~9"?<<endl;??
- ????????????exit(1);??
- char>?rs?=?long_mul(clist1,clist2);??
- ????cout?<<?"两个大整数相乘的积为:?";??
- for(list<char>::iterator?iter=rs.begin();?iter!=rs.end();?++iter)??
- ????????cout?<<?*iter;??
- ????cout?<<endl;??
- ????system("pause");??
- return?0;??
- }??
转自:http://blog.csdn.net/hackbuteer1/article/details/6532490
1.第22行代码进行了倒置操作,是因为这样就把输入的数字的个位放到了a[0],十位放到了a[1]........然后这样从a[0]开始的操作就符合了我们一般进行数学运算的习惯.
2.result[i+j]+=a[i]*b[j];这个是计算两个数乘法的基本运算式子.接下来进行进位操作就好了.
3.rs.push_front(low+'0'); 第68行中low+‘0’是因为list<char>所以存入的时候要以char的形式存入,否则会变成low对应的ascii码的内容。
(编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|