（1.1.1.1）大数相乘

发布时间：2020-12-14 02:19:48 所属栏目：大数据来源：网络整理

导读：方法（一）：关于大数乘法，可以使用数组来模拟小学三年级的乘法竖式计算过程，代码如下： [cpp] ? view plain copy #include?"iostream" ?? #include?"string" ?? using ? namespace ?std;?? int ?main( void )?? {?? ???? char ?str1[1000],str2[1000];??

方法（一）：

关于大数乘法，可以使用数组来模拟小学三年级的乘法竖式计算过程，代码如下：

[cpp]? 
   view plain 
   copy 
    
   
 #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?"list"??

#include?"string"??
namespace?std;??
??
/*******大整数减法*********/??
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())?!=?'-'?)??
????????//首先保证两数位数相同(填充0)??
????????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;?//低位借位初始为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');??
//双方最高位相加的处理??
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());??? ????????rs?=?long_sub(clist2,?clist1);??
//如果两正相减，做相减??
if?(?*(clist1.begin())?!=?'-'?&&?*(clist2.begin())?!=?'-'?)??
int???sign?=?-1;???//代表两数相减结果的正负，如果最高位为'-'(ascii码为45)表示负，否则表示正??
//首先保证加数位数相同(填充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;?if?(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)???//两个数都成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;?//最后结果的正负标志，'-'(ascii码为45)表示负，其他表示正??
char?high_bit2?=?*(clist2.begin());?//clist2的最高位??
if?(?high_bit2?==?'-'?)??
????????????sign?=?'-';?//相乘结果为负??
????????????clist2.erase(clist2.begin());?//去掉高位的'-'??
int?length2?=?clist2.size();?//clist2的有效长度(去除'-'号后)??
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;?//高位部分和clist1的积??
char>?rs2;?//低位部分和clist1的积??
????????????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); font-weight:bold; background-color:inherit">if?(?sign?==?'-'?)??
????????????????rs.push_front('-');?//结果添上'-'号??
if?(clist1.size()?>1?&&?clist2.size()?==?1)??
//最后结果的正负标志，'-'表示负，其他表示正??
char?high_bit1?=?*(clist1.begin());?//clist1的最高位??
if?(?high_bit1?==?'-'?)??
????????????clist1.erase(clist1.begin());?int?length1?=?clist1.size();?//clist1的有效长度(去除'-'号后)??
if?(?length1?>?1?)??
//对clist1进行拆分??
char>???clist1_1;???char>???clist1_2;??? ????????????????clist1_1.push_back(*iter);??
for(;?iter?!=?clist1.end();?++iter)??
????????????????clist1_2.push_back(*iter);??
//高位部分和clist2的积??
//低位部分和clist2的积??
????????????rs1?=?long_mul(clist1_1,108); list-style:decimal-leading-zero outside; color:inherit; line-height:18px; margin:0px!important; padding:0px 3px 0px 10px!important"> ????????????rs2?=?long_mul(clist1_2,153); font-weight:bold; background-color:inherit">for(?i=0;?i<clist1_2.size();?++i?)??
if?(clist1.size()?>1?&&?clist2.size()?>?1?)??
char???high_bit1?=?*(clist1.begin());???char???high_bit2?=?*(clist2.begin());???//clist2的最高位??
if?(?high_bit1?==?'-'???&&?high_bit2?!=?'-'?)??
????????????sign?=?'-';???//相乘结果为负??
????????????clist1.erase(clist1.begin());???//去掉高位的'-'??
if?(?high_bit1?!=?'-'?&&?high_bit2?==?'-'?)??
????????????sign?=?'-';??? ????????????clist2.erase(clist2.begin());???if?(?high_bit1?=='-'?&&?high_bit2?==?'-'?)??
????????????clist1.erase(clist1.begin());??
????????????clist2.erase(clist2.begin());????//clist1的有效长度??
//clist2的有效长度??
if?(?length1?==?1?||?length2?==?1?)??
if?(?length1?>?1?&&?length2?>?1?)??
//对clist1和clist2分别进行划分??
char>?clist1_1;???//clist1的高位部分??
char>?clist1_2;???//clist1的低位部分??
char>?clist2_1;???//clist2的高位部分??
char>?clist2_2;???//clist2的低位部分??
for(i=0,153); font-weight:bold; background-color:inherit">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;???//clist1的高位和低位部分的差??
char>?sub2_lh;???//clist2的低位和高位部分的差??
//两个高位分别移位??
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);??
//把几个乘积的结果加起来??
char>?tmp1?=?long_add(rs_hh,?rs_ll);??
char>?tmp2?=?long_add(tmp1,?rs_sub1_sub2);??
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;??
}??

（编辑：李大同）

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