(更新中)[C++]大整数算法

在各种语言中,很多东西都是不一样的,但是数字大小限制都是一样的。也就是说,溢出,是一个让所有程序员都头疼的东西。
大整数加减法,也就是为了解决过大的数字无法计算而生的。这里,我以一本通中的11681169题做例子,做一下C++中的大整数加减法。

大整数加法

1168:大整数加法

头文件引用以及定义等

#include <iostream>//绝不用万能头!
#include <cstdio>//No More cin&cout
#include <cstring>

#define MAX 10000

using namespace std;

Step One:输入

我们在这里用字符串进行输入储存,用gets()函数进行输入,并且获取其长度。
代码如下:

char in_a[MAX],in_b[MAX];
gets(in_a);
gets(in_b);

int lena = strlen(in_a),lenb = strlen(in_b);

Step Two:数据转存

由于希望直接加减计算,我们将字符串数组倒序转存到初始化为零的整型数组当中。
倒序转存是为了我们从个位算起更方便。
代码如下:

int a[MAX],b[MAX];
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));

for(int i = 0;i < lena;i++)
a[lena - i] = in_a[i];
for(int i = 0;i < lenb;i++)
b[lenb - i] = in_b[i];

要注意,我们转存后的ab是从a[1]b[1]开始的。

Step Three:加法主程序

首先,我们需要定义一个数组来储存结果、两个变量分别储存进位和结果的长度。
代码如下:

int c[MAX],flag = 0;lenc = 1;
memset(c,0,sizeof(c));

然后,开始加减。
代码如下:

while(lenc <= lena||lenc <= lenb)//循环条件是结果的长度不长于原数的长度
{
c[lenc] = a[lenc] + b[lenc] + flag;//加起来
flag = c[lenc]/10;//储存进位
c[lenc] %= 10;//储存本位
lenc++;//计数加一
}

完成加的操作后,最后第一位可能会再进一位,此时我们就需要判断是否需要进位。
代码如下:

if(flag)
c[lenc] = 1;
else
lenc--;

Step Four:输出

要注意,我们的数组是倒序的,所以需要倒序输出。
代码如下:

for(int i = lenc;i > 0;i--)
printf("%d",c[i]);
printf("\n");

完整程序

gayhub链接

#include <iostream>//绝不用万能头!
#include <cstdio>//No More cin&cout
#include <cmath>
#include <cstring>

#define MAX 10000

using namespace std;

int main(){
char in_a[MAX],in_b[MAX];
int a[MAX],b[MAX],c[MAX];
int lena,lenb,lenc;
int flag = 0;

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

gets(in_a);
gets(in_b);

lena = strlen(in_a);
lenb = strlen(in_b);

for(int i = 0;i < lena;i++)
a[lena-i] = in_a[i] - '0';
for(int i = 0;i < lenb;i++)
b[lenb-i] = in_b[i] - '0';

lenc = 1;
while (lenc <= lena || lenc <= lenb)
{
c[lenc] = a[lenc] + b[lenc] + flag;
flag = c[lenc]/10;
c[lenc] %= 10;
lenc++;
}

if(flag)
c[lenc] = 1;
else
lenc--;

for(int i = lenc;i > 0;i--)
printf("%d",c[lenc]);

printf("\n");
system("pause");
return 0;
}

到此,加法完成!

大整数减法

Step One:输入

文章作者: Tim
文章链接: http://itstim.xyz/2019/10/02/C-大整数算法/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Tim's Blog
支付宝恰饭打赏
微信恰饭打赏