当需要计算的整数或计算结果可能会超出 long long 所能表示的范围时, 应该用大整数来存储和计算 (Java 里面有 BigInteger 来存储大整数, 这里讨论的是 C++ 语言).
大整数的存储形式是下面这个结构体 (包含了构造函数):
- // 大整数结构体
- struct bign{
- int d[1000];
- int len;
- bign(){
- memset(d, 0, sizeof(d));
- len = 0;
- }
- };
首先以字符串的形式读去数据, 然后将字符串逐个逆序字符存入 d[] 数组 (可以采用用 reverse 函数将字符串进行反转, 然后正序逐个赋值),len 记录整数的长度.
change() 转换函数 (完成字符串到 bign 结构体的转换)
- // 将整数的字符串形式转换成 bign 结构体形式
- 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;
- }
在对两个大整数进行减法时要先比较减数和被减数的大小, 如果减数大于被减数, 则两个整数交换位置, 所以还需要一个比较函数
compare() 比较函数 (比较两个数的大小 如果 a> b, 那么返回 1, 如果 a <b, 返回 - 1, 否则返回 0)
- // 比较两个数的大小 如果 a> b, 那么返回 1, 如果 a <b, 返回 - 1, 否则返回 0
- int compare(bign a, bign b){
- if (a.len> b.len)
- return 1; // a 更大
- else if (a.len <b.len)
- return -1;
- else{
- for (int i = a.len - 1; i>= 0; i--){
- if (a.d[i]> b.d[i]) // 只要有一位 a 大, 则 a 更大
- return 1;
- else if (a.d[i] <b.d[i])
- return -1;
- }
- return 0; // 两数相等
- }
- }
1. 大整数的加法:
将该位上的两个数字以及来自低位的进位相加, 得到的结果的个位表示该位结果, 十位数作为新的进位
- bign add(bign a, bign b){ // 高精度 a + 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){
- c.d[c.len++] = carry; // 如果最后进位不为 0, 则直接赋给结果的最高位
- }
- return c;
- }
2. 大整数之间的减法:
使用下面这个函数前要先比较两数绝对值大小, 如果被减数小于减数, 需要交换两个变量, 然后输出符号, 再使用 sub 函数
- bign sub(bign a, bign 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;
- }
3. 大整数和整数的乘法 (一个大整数乘以一个整数):
用从大整数 a 的低位开始, 用大整数的每一位乘以给定的整数, 然后加上进位, 每一次的结果对 10 取余就是结果变量 c 在当前索引的数值, 每一次的结果除以 10 作为新的进位, 遍历完 a 的所有数位后, 如果表示进位的变量不为零, 则应该将这个变量逐位的加到 c 的最高位, 直到这个进位变量为 0
- 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){
- c.d[c.len++] = carry % 10;
- carry /= 10;
- }
- return c;
- }
如果两个整数刚好一正一负, 那么先输出符号, 然后将绝对值带入函数计算.
4. 大整数和整数的除法 (一个大整数除以一个整数):
- 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;
- }
练习题: PAT B1017 PAT A1023
本博客大部分取自胡凡的《算法笔记》和《算法笔记上机训练》
来源: http://www.bubuko.com/infodetail-3394435.html