大数相乘 分治法 10000 进制
优化:万进制 #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,sizeof(a)); memset(b,sizeof(b)); memset(c,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; {?? 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; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |