前言

这种类型,在做题过程中多为观察所给数据可能造成的大小来选择是否使用。

属于模板类型,学习者理解其格式并记住大致框架即可熟练应用。

一、什么是大整数(高精度)

想知道什么是大整数,不如换一个解释的方法:什么时候需要用到大整数?

众所周知,int类型的范围是-2147483648~2147483647。long long类型的范围是 -2^63 ~
(2^63)-1。那当题目需要用到或需要输出比long
long类型的范围还要大的数字时,我们是不是就不能用常规办法去接收这些数字了。这个时候使用大整数就可以解决上述问题。即解决接收超出long
long范围数字的问题。

二、大整数的存储

原理很简单,使用数组。

例如定义Int类型数组d[1000],那么这个数组中的每一位就代表存放整数的每一位。比如将数字123456存储,则有d[0] = 6,d[1] =
5,d[2] = 4,d[3] = 3,d[4] = 2,d[5] = 1。整数的高位存在数组的高位,整数的低位存储在数组的低位。(为了契合加减乘除的思维)

这时候会产生一个需要注意的问题:把整数通过%s或者itoa的方式变成字符串的时候,一开始是逆位存储的,即d[0] = 1...,
因此读入的之后需要在另存为至d[i]数组的时候反转一下。

为了方便随时获取大整数的长度,一般定义len来记录长度,并与d数组组合成结构体。
struct bign{ int d[1000]; int len; };
<>bign是big number的缩写。

一般输入大整数时,都是先用字符串读入,然后再把字符串另存为至bign结构体
。由于使用char数组进行读入时,整数高位会变成数组地位,整数的地位会变成数组的高位。因此为了让整数在bign中是顺位存储,需要让字符串倒着赋值给d[]数组。
bign change(char str[])//将整数转换为bign { bign a; a.len =
strlen(str);//bign的长度就是字符串的长度 for(int i = 0; i < a.len; i++) { a.d[i] =
str[a.len-i-1] - '0'; } return a; }
 如果要比较两个bign变量的大小,也很简单:先判断len大小,若不相等,长的为大,若相等,则从高位至低位逐个比较,直到某一位不等,则可以判断两者大小。
int compare(bign a,bign b) { if(a.len > b.len) return 1;//a大 else if(a.len <
b.len) return -1;//a小 else { for(int i = a.len - 1; i >= 0; i--)//从高位到低位开始比较 {
if(a.d[i] > b.d[i]) return 1;//只要有一位a大,则a大 else if(a.d[i] < b.d[i]) return
-1;//只要有一位a小,则a小 } return 0;//两位相等 } }
最后如果需要输出bign变量的值,遍历一遍就可以实现了。 
void print(bign a) { for(int i = a.len - 1; i >= 0; i--) {
printf("%d",a.d[i]); } printf("\n"); }
三、大整数的四则运算

1、高精度加法

加法实现方式与我们以前学到的加法一样。对于某一位的运算:我们将该位上的两个数字与进位相加,得到的结果取个位数作为该结果,十位数作为新的进位。
bign add(bign a,bign b) { bign c; int carry = 0; //carry是进位 for(int i = 0; i <
a.len || i < b.len; i++) //以较长的为界限 { int temp = a.d[i] + b.d[i] + carry;
//两个对应位与进位相加 c.d[c.len++] = temp%10; //个位数为该位的结果 carry = temp/10; //十位数为新的进位 }
if(carry != 0) //如果最后进位不为0,则直接赋给结果的最高位 { c.d[c.len++] = carry; } return c; }
这里有一点需要注意,这样写法的条件是两个对象都是非负整数
。如果有一方是负的,可以在转换到数组这一步时去掉符号,再使用高精度减法;如果两个都是负的,都去掉负号后采用高精度加法,最后负号加回去即可。

2、 高精度减法

通过对减法步骤的拆分可以得到一个简练的步骤:对某一位,比较被减位和减位,如果不够减,则令被减位的高位减1,被减位加10再进行减法;如果够减,直接减。最后需要注意减法后高位可能有多余的0,要
去除他们,但也要保证结果至少有一位数。
bign sub(bign a,bign b) //a - b { bign c; for(int i = 0; i < a.len || i <
b.len; i++) //以较长的为界限 { if(a.d[i] < b.d[i]) //不够减 { a.d[i + 1]--; //向高位借位
a.d[i] += 10; //向前位借10 } c.d[c.len++] = a.d[i] - b.d[i]; //减法结果为当前位 }
while(c.len - 1 >= 1 && c.d[c.len - 1] == 0) { c.len--; //去除高位的0,同时至少保留一位最低位 }
return c; }
最后需要指出,使用sub函数前要比较两个数的大小,如果被减数小于减数,需要交换两个变量,然后输出负号,再用sub函数。

3、高精度与低精度的乘法

这里所谓的低精度就是基本数据类型存储的数据,如int。这里就是bign与int的乘法。

对某一位来说是这样的步骤:取bign的某位与int型整体相乘,再与进位相加,所得结果的个位数作为该结果,高位部分作为新的进位。
bign multi(bign a,int b) { bign c; int carry = 0; //进位 for(int i = 0; i <
a.len; i++) { int temp = a.d[i] * b + carry; c.d[c.len++] = temp % 10;
//个位作为该结果 carry = temp / 10; //高位部分作为新的进位 } while(carry != 0)
//和加法不一样,乘法的进位可能不止一位,因此用while { c.d[c.len++] = carry % 10; carry /= 10; }
return c; }
另外,如果a和b中存在负数,需要先记录下负号,然后取他们的绝对值带入函数。

4、高精度与低精度的除法 

归纳其中一位的步骤:上一步的余数乘以10加上该步的位,得到该步临时的被除数,将其与除数比较;如果不够除,则该位的商为0;如果够除,则商即为对应的商,余数即为对应的余数。最后一步要注意减法后高位可能有多余的0,要去除他们,但也要保证结果至少有一位数。
bign divide(bign a,int b,int& r) //r为余数 { bign c; c.len =
a.len;//被除数的每一位和商的每一位是一一对应的,因此先令长度相等 for(int i = a.len - 1; i >= 0; i--)
//从高位开始 { r = r * 10 + a.d[i]; //和上一位遗留的余数组合 if(r < b) c.d[i] = 0; //不够除,该位为0
else //够除 { c.d[i] = r / b; //商 r = r % b; //获得新的余数 } } while(c.len - 1 >= 1 &&
c.d[c.len - 1] == 0) { c.len--; //去除高位的0,同时至少保留一位最低位 } return c; }
考虑到很多题目会要求得到余数,因此把余数写成引用的形式直接作为参数传入,或者也可以把余数设成全局变量。 

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信