现在的位置: 首页 > 综合 > 正文

大数相乘 分治法 10000 进制

2013年12月01日 ⁄ 综合 ⁄ 共 1059字 ⁄ 字号 评论关闭

优化:万进制

#include<iostream>

#include<cstring>

using namespace std;

void num1(int s[],string st1);

int a[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。

Int main()

{

string str1,str2;

int len;

cin>>str1>>str2;

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

memset(c,0,sizeof(c));

num1(a,str1); //把str1从最低位开始,每4位存放在数组a中

num1(b,str2); //把str2从最低位开始,每4位存放在数组b中

for(int i=1;i<=a[0];i++) //作按位乘法并处理进位,此处是万进制进位

for(int j=1;j<=b[0];j++)

{

c[i+j-1]+=a[i]*b[j];

c[i+j]+=c[i+j-1]/10000;

c[i+j-1]%=10000;

}

len=a[0]+b[0];//a[0]和b[0]存放的是每个数按4位处理的位数

while ((c[len]==0)&&(len>1)) len–;//去掉高位的0,并输出最高位

cout<<c[len];

for(int i=len-1;i>=1;i–)//把剩下来的每一位还原成4位输出

{

if (c[i]<1000) cout<<’0’;

if (c[i]<100) cout<<’0’;

if (c[i]<10) cout<<’0’;

cout<<c[i];

}

cout<<endl;

return 0;

}

void num1(int s[],string st1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中

{   int k=1,count=1;

s[0]=st1.length();//存放st1的长度,省去一长度变量

for(int i=s[0]-1;i>=0;i–) //从最低位开始,处理每一位

{ if (count%4==0) {s[k]+=(st1[i]-‘0’)*1000; if(i!=0) k++;}

if (count%4==1) s[k]=(st1[i]-‘0’);

if (count%4==2) s[k]+=(st1[i]-‘0’)*10;

if (count%4==3) s[k]+=(st1[i]-‘0’)*100;

count++;

}

s[0]=k; //存放数组的位数,就是按4位处理后的万进制数的位数。

Return;

}

 

抱歉!评论已关闭.