avatar

目录
大数的加法与乘法

“大数”的意思就是理论上可以无限长,只要字符串存储的下就可以,远超过int、long、long long可以表示的范围的数。

两个大数的加法

基本思路:
两个大数用字符串的形式输入,将字符串对应修改为存放每一位数字的数组,注意是逆序的数组,方便后续进行加法操作。直接对所有位进行加法,然后遍历一遍,有超过9的数字就往前进1,最终再把数组逆序输出即可。

1、两个必要函数的准备

c
1
2
3
char C1(int x);//把0到9转换为'0'到'9'。
int C2(char x);//相反
//直接用switch就可以了

2、将两个字符数组转换为逆序的整型数组

c
1
2
3
4
5
6
7
8
void char_to_int(int *b,char *a,int t)
{//把长度为t的字符数组a逆序存储在整型数组b中,其余项初始化为0
for(int i=0;i<t;i++)
b[i]=C2(a[t-1-i]);
for(int i=t;i<N;i++)
b[i]=0;
return;
}

3、两个字符数组相加

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void add(int *c,int *a,int *b)
{
for(int i=0;i<N;i++)
{
c[i]=a[i]+b[i];
}//不考虑进位问题,全部加一遍
for(int i=0;i<N;i++)
{
if(c[i]>9)
{
if(i>=N-2)
cerr << "int[N] overflow" << endl;
else
{//哪一位进位了就把上一位加一,遍历的顺序是细节问题
c[i+1]++;
c[i]-=10;
}
}
}
}

4、将逆序整型数组转换为字符数组

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void int_to_char(char *b,int *a)
{
int t=0;
for(int i=N-1;i>=0;i--)
{
if(a[i]!=0)
{
t=i+1;
break;
}
}
for(int i=0;i<t;i++)
{
b[i]=C1(a[t-1-i]);
}
b[t]='\0';
}

两个大数的乘法

乘法的本质就是对加法的简化表达,那我们就把它“复杂”回去!

加法写了那么多代码,不能浪费嘛。

举例说明我的方法

987654321 * 12345

我们先计算,987654321 * 5,然后计算9876543210 * 4,然后是98765432100 * 3……

这个时候就会发现,计算大数加法的时候的逆序数组真是方便啊!

把数组”右移一位“就多了个零。

而这个乘以5、乘以4、乘以3…我们直接用循环几次的”大数加法“就行。

代码

c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void mul(int *c,int *a,int *b)
{//a乘以b,存储在c里面
for(int i=0;i<N;i++)
c[i]=0;//初始化,很重要!不然就会出现一堆莫名其妙的数字。
int size=0;
for(int i=N-1;i>=0;i--)
{//计算一下这个b有多长,长度是size
if(b[i]!=0)
{
size=i+1;
break;
}
}
for(int i=0;i<size;i++)
{//外面的大循环,把b分成一位一位的,分别去乘以a
int *aa=new int[N];
for(int j=0;j<i;j++)
aa[j]=0;
for(int j=i;j<N;j++)
aa[j]=a[j-i];
//这两个循环是把a”右移“,就是在a的低位增加几个零,具体个数要看下面要乘的是b的哪一位

int x=b[i];
for(int j=0;j<x;j++)
{//直接调用大数的加法,省事
add(c,c,aa);
}
free(aa);
}
return;
}

最后

减法与加法几乎是一样的,就不细说了。

大数的除法,我目前还不会,想一想感觉是比较麻烦的,因为”大数的乘法“我是想到了乘法与加法的关系才弄出来的,但除法的话感觉规律我还不懂,有机会我要学习一下,然后再水一篇文章(误)。

打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论