大数相乘分治法 10000 进制

短命女 2022-09-17 14:30 175阅读 0赞

优化：万进制

\#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;

\}

发表评论取消回复

表情：

评论列表（有 0 条评论，175人围观）

还没有评论，来说两句吧...

相关阅读

相关大数相乘

一、背景最近在看算法的时候发现了一个问题，我们都知道方法的形参是要指定类型的，假如有以下方法 public int example(int a,int b){

傷城~/ 2022年09月30日 13:55/ 0 赞/ 221 阅读

相关大数相乘分治法 10000 进制

优化：万进制 \include<iostream> \include<cstring> using namespace std; void num1(int s\[\]

短命女/ 2022年09月17日 14:30/ 0 赞/ 176 阅读

相关大整数相乘(分治法）

分治法的原理讨论问题时，先来了解一下什么是分治法。 > 分治法的意思就是，分而治之，也就是把一个问题，拆分成几个小问题，最后再汇总解决的方法 ![watermark

「爱情、让人受尽委屈。」/ 2022年09月11日 14:13/ 0 赞/ 555 阅读

相关大数相乘

无意中看到一个华为面试题，使用代码计算[1234567891011121314151617181920\2019181716151413121110987654321][123

系统管理员/ 2022年08月11日 20:29/ 0 赞/ 204 阅读

相关大数进制转换

一般的数字进制转换大家都很熟悉，先转换为十进制数字，再进行除 n 取余，这种情况适用于操作数不大的情况（不大于最大的基本数据类型（long long）），但是如果操

心已赠人/ 2022年07月15日 03:40/ 0 赞/ 176 阅读

相关大数相乘

在这之前我们先来了解一下Java 中每种基本数据类型所占存储空间的大小。其中 1Byte = 8bit。 <table> <tbody> <tr> <th>

朱雀/ 2022年06月02日 02:36/ 0 赞/ 264 阅读

相关大数相乘

设X和Y是n位的二进制整数，现在要计算X\Y的结果将a和b分为两段，每段长均为总长的1/2， ![20180329214901958][]

拼搏现实的明天。/ 2022年05月28日 05:06/ 0 赞/ 224 阅读

相关大数相乘

题目编写两个任意位数的大数相乘的程序，给出计算结果。比如： > 题目描述：输出两个不超过100位的大整数的乘积。 > 输入：输入两个大整数，如1234567

今天药忘吃喽~/ 2022年05月23日 11:23/ 0 赞/ 345 阅读

相关矩阵相乘问题（分治法求解）

采用蛮力+分治进行求解：矩阵相乘公式： ![20181121202552877.png][] ![watermark_type_ZmFuZ3poZW5naGVpdGk_

古城微笑少年丶/ 2022年04月15日 04:56/ 0 赞/ 215 阅读

相关大数相乘

def fun(num1,num2): num1 type str num2 type str a = map(int,

落日映苍穹つ/ 2021年10月24日 01:48/ 0 赞/ 345 阅读