2020年7月13日 by HXuesong
大整数又称为高精度整数，其含义就是用基本数据类型无法存储其精度的整数
使用数组即可，即整数的高位存储在数组的高位，整数的低位存储在数组的低位 把整数按字符串%s读入的时候，实际上是逆位存储的，因此在读入之后需要在另存至数组的时候需要反转一下
为了方便随时获取大整数的长度，一般会定义一个int变量len来记录其长度，并和数组组合成结构体：
struct bign {
int d[1000];
int len;
};
//bign是big number的缩写使用构造函数对结构体自动进行初始化：
struct bign {
int d[1000];
int len;
bign() {
memset(d, 0, sizeof(d));
len = 0;
}
};输入大整数时，一般都是先用字符串读入，然后再把字符串另存至bign结构体：
bign change(char str[]) {
bign a;
a.len = strlen(str);
for(int i = 0; i < a.len; i++)
a.d[i] = str[a.len - i - 1] - '0'; //逆序赋值
return a;
}比较两个bign变量的大小：
//比较a和b大小，a大、相等、a小分别返回1、0、-1
int compare(bign a, bian b) {
if(a.len > b.len)
return 1;
else if(a.len < b.len)
return -;
else {
for(int i = a.len - 1; i >= 0; i--) { //从高位往低位比较
if(a.d[i] > b.d[i])
return 1;
else if(a.d[i] < b.d[i])
return -1;
}
}
return 0;
}对其中一位进行加法的步骤： 将该位上的两个数字同低位进位相加，得到的结果取个位数作为该位的结果，取十位数作为新的进位
#include <stdio.h>
#include <string.h>
struct bign {
int d[1000];
int len;
bign() {
memset(d, 0, sizeof(d));
len = 0;
}
};
bign change(char str[]) {
bign a;
a.len = strlen(str);
for(int i = 0; i < a.len; i++)
a.d[i] = str[a.len - i - 1] - '0'; //逆序赋值
return a;
}
bign add(bign a, bign b) {
bign c;
int carry = 0; //进位
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;
return c;
}
void myPrint(bign a) { //输出a
for(int i = a.len - 1; i >= 0; i--)
printf("%d", a.d[i]);
}
int main() {
char str1[100], str2[100];
scanf("%s%s", str1, str2);
bign a = change(str1);
bign b = change(str2);
bign c = add(a, b);
myPrint(c);
return 0;
}最后指出： 这样写法的条件是两个对象都是非负整数，如果有一方是负的，可以在转换到数组这一步时去掉其符号，然后采用高精度减法；如果两个都是负的，就都去掉负号后用高精度加法，最后再把负号加回去即可
对其中一位进行减法的步骤： 对某一位，比较被减位和减位，如果不够减，则令被减位的高位减1、被减位加10再进行减法；如果够减，则直接减。最后一步要注意减法后高位可能有多余的0，要忽视它们，但也要保证结果至少有一位数
#include <stdio.h>
#include <string.h>
struct bign {
int d[1000];
int len;
bign() {
memset(d, 0, sizeof(d));
len = 0;
}
};
bign change(char str[]) {
bign a;
a.len = strlen(str);
for(int i = 0; i < a.len; i++)
a.d[i] = str[a.len - i - 1] - '0'; //ÄæÐò¸³Öµ
return a;
}
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;
}
void myPrint(bign a) {
for(int i = a.len - 1; i >= 0; i--)
printf("%d", a.d[i]);
}
int main() {
char str1[100], str2[100];
scanf("%s%s", str1, str2);
bign a = change(str1);
bign b = change(str2);
bign c = sub(a, b);
myPrint(c);
return 0;
}最后指出： 使用sub函数要比较两个数的大小，如果被减数小于减数，需要交换两个变量，然后输出负号，再使用sub函数
对其中一位进行乘法的步骤： 取bign的某位与int型整体相乘，再与进位相加，所得结果的个数位作为该位结果，高位部分作为新的进位
#include <stdio.h>
#include <string.h>
struct bign {
int d[1000];
int len;
bign() {
memset(d, 0, sizeof(d));
len = 0;
}
};
bign change(char str[]) {
bign a;
a.len = strlen(str);
for(int i = 0; i < a.len; i++)
a.d[i] = str[a.len - i - 1] - '0'; //ÄæÐò¸³Öµ
return a;
}
bign mul(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 /= 10;
}
//和加法不同，乘法的进位可能不止一位
while(carry != 0) {
c.d[c.len++] = carry % 10;
carry /= 10;
}
return c;
}
void myPrint(bign a) {
for(int i = a.len - 1; i >= 0; i--)
printf("%d", a.d[i]);
}
int main() {
char str1[100];
int b;
scanf("%s%d", str1, &b);
bign a = change(str1);
bign c = mul(a, b);
myPrint(c);
return 0;
}对其中一位进行除法的步骤： 上一步的余数乘以10加上该步的位，得到该步临时的被除数，将其与除数比较： 如果不够除，则该位的商为0；如果够除，则商即为对应的商，余数即为对应的余数。 最后要注意高位可能有多余的0，要忽视它们，但也要保证结果至少有一位数
#include <stdio.h>
#include <string.h>
struct bign {
int d[1000];
int len;
bign() {
memset(d, 0, sizeof(d));
len = 0;
}
};
bign change(char str[]) {
bign a;
a.len = strlen(str);
for(int i = 0; i < a.len; i++)
a.d[i] = str[a.len - i - 1] - '0'; //ÄæÐò¸³Öµ
return a;
}
bign divide(bign a, int b, int &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;
else {
c.d[i] = r / b;
r %= b;
}
}
while(c.len - 1 >= 1 && c.d[c.len-1] == 0)
c.len--; //去除高位的0，同时至少保留一位最低位
return c;
}
void myPrint(bign a) {
for(int i = a.len - 1; i >= 0; i--)
printf("%d", a.d[i]);
}
int main() {
char str1[100];
int b, r = 0;
scanf("%s%d", str1, &b);
bign a = change(str1);
bign c = divide(a, b, r);
myPrint(c);
printf("\nr = %d", r);
return 0;
}