高精度

板块学术版
楼主封禁用户
当前回复15
已保存回复15
发布时间2021/6/5 09:24
上次更新2023/11/4 22:19:14

被骇客银狼阻止的越权访问保存失败

高精度

封禁用户楼主2021/6/5 09:24

高精度

一.定义一个大整数

1. 存放位数

我们定义大整数结构体类型，将用于存大整数的数组封装到结构体内，用 num [1] ,num[2] ……存放个位，十位……，并且增加一个成员变量：数组位数

代码:

struct BIG{
    static const int MR = 1e4 + 10;
    int l;//表示整数位数
    int num[MR];

    BIG(){
        memset(num, 0, sizeof(num));
        l = 1;
    }
};

变量l表示大整数的位数，num数组保存了大整数的每一位。其中static const int MR = 1010定义了一个静态成员，用来控制这个大整数类型可以表示的最大位数（这里是1000位）。接下来的BIG()叫构造函数，每当一个新的BIG类型变量被定义的时候，都会先调用构造函数，这里构造函数的作用是在定义新的BIG类型变量时将新的变量的初值设为0. 接下来我们将大整数的功能，都加入到结构体中

2.输入

我们要满足输入大整数，可以定义成员函数set,将int或string类型表示的整数化为大整数存入结构体。定义后可以使用a.set(n)或a.set("12345978410")的方式调用实现代码:

//单精度化高精度
void set(int n){
	memset(num, 0, sizeof(num));
	l = 0;
	while(n > 0){
		l++;
		num[l] = n % 10;
		n /= 10;
	}
	if (l == 0) l++;
}
//字符串化高精度
void set(string s){
	memset(num, 0, sizeof(num));
	l = s.length();
	for (int i = 1; i <= l; i++){
		num[i] = s[l - i] - '0';}
		//数组num的十进制写法是反过来储存的
    }
}

虽然定义了两个同名函数但是它们的参数列表不完全相同（一个是int，一个是string），所以不会出现歧义。程序会根据调用时的参数类型，选择对应的函数运行。

3.输出

在结构体内加入以下代码，定义成员函数print，输出大整数。

void print(){
	//从高位输出到低位
	for (int i = l; i >= 1; i--){
		printf("%d", num[i]);
	}
	printf("\n");//最后要输出一个换行
}

完整的大整数结构体代码:

struct BIG{
	static const int MR = 1010;
	int l;//表示整数位数
	int num[MR];
	//构造函数
	BIG(){
		memset(num, 0, sizeof(num));
		l = 1;
	}
	//单精度化高精度
	void set(int n){
		memset(num, 0, sizeof(num));
		l = 0;
		while(n > 0){
			l++;
			num[l] = n % 10;
			n /= 10;
		}
		if (l == 0) l++;
	}
	//字符串化高精度
	void set(string s){
		memset(num, 0, sizeof(num));
		l = s.length();
		for (int i = 1; i <= l; i++){
			num[i] = s[l - i] - '0';
		}
		//数组num的十进制写法是反过来储存的
	}
	void print(){
		//从高位输出到低位
		for (int i = l; i >= 1; i--){
			printf("%d", num[i]);
		}
		printf("\n");//最后要输出一个换行
	}
};

二.比较运算符

重定义小于号

把重载函数写在结构体外面：

bool operator< (const BIG& a, const BIG& b){
	if(a.l != b.l) return a.l < b.l;//位数少的较小
    //若位数相等从高位开始比较
	for (int i = a.l; i >= 1;i--){
		if(a.num[i] != b.num[i]) return a.num[i] < b.num[i];
	}
	return false;//如果运行到这一步，说明两个数完全相同
}

bool operator>(const BIG &a, const BIG &b) { return b < a; }
bool operator==(const BIG &a, const BIG &b) { return !(b < a) && !(a < b); }
bool operator!=(const BIG &a, const BIG &b) { return b < a || a < b; }
bool operator<=(const BIG &a, const BIG &b) { return !(b < a); }
bool operator>=(const BIG &a, const BIG &b) { return !(a < b); }

重载了小于号以后，不带cmp的sort函数就可以使用了，功能是将属猪排成从小到大的顺序。

三.算术运算符

1.重定义加法运算符

BIG operator+ (const BIG& a, const BIG& b){//高精度加高精度
	BIG c;
	c.l = max(a.l, b.l);
	int u = 0;//记录进位多少
	for (int i = 1; i <= c.l; i++){
		int t = a.num[i] + b.num[i] + u;
		c.num[i] = t % 10;
		u = t / 10;
	}
	if(u > 0){//如果最高位进了位，c会比a和b多一位
		c.l++;
		c.num[c.l] = u;
	}
	return c;
}

2.重定义减法运算符（大减小）

BIG operator- (const BIG& a, const BIG& b){//高精度减高精度
	BIG c;
	c.l = max(a.l, b.l);
	int u = 0;//记录借位
	for (int i = 1; i <= c.l; i++){
		int t = a.num[i] - b.num[i] - u;
		if(t < 0){//小于0说明不够减
			c.num[i] = t + 10;
			u = 1;
		}else{
			c.num[i] = t;
			u = 0;
		}
	}
	while (c.num[c.l] == 0 && c.l > 1)//找到最高的非零位
		c.l--;
	return c;
}

3.重定义乘法运算符

1.BIG乘int(高精度乘单精度)

BIG operator* (const BIG& a, const int& b){//高精度乘单精度
	BIG c;
	c.l = a.l;
	int u = 0;//记录进位多少
	for (int i = 1; i <= c.l; i++){
		int t = a.num[i] * b + u;
		c.num[i] = t % 10;
		u = t / 10;
	}
	while (u > 0){//若a的最高位乘完了之后还需要进位，c会比a位数多
		c.l++;
		c.num[c.l] = u % 10;
		u /= 10;
	}
	return c;
}

2.BIG乘BIG(高精度乘高精度)

BIG operator* (const BIG& a, const BIG& b){//高精度乘高精度
	BIG c;
	c.l = a.l + b.l - 1;
    for (int i = 1; i <= a.l; i++){
        for (int j = 1; j <= b.l; j++){
            c.num[i + j - 1] += a.num[i] * b.num[j];
            c.num[i + j] += c.num[i + j - 1] / 10;
            c.num[i + j - 1] %= 10;
        }
    }
    while (c.num[c.l + 1] > 0)
    { //若a的最高位乘完了之后还需要进位，c会比a位数多
        c.l++;
        c.num[c.l + 1] = c.num[c.l] / 10;
        c.num[c.l] %= 10;
    }
	return c;
}

4.重定义除法运算符(BIG除int)

BIG operator/ (const BIG& a, const int& b){//高精度除以单精度
	BIG c;
	c.l = a.l;
	int r = 0;//记录余数
	//从最高位开始除
	for (int i = c.l; i>= 1; i--){
		int t = r * 10 + a.num[i];
		c.num[i] = t / b;
		r = t % b;
	}
	
	while (c.num[c.l] == 0 && c.l > 1){//找到最高的非零位
		c.l--;
	}
	return c;
}

注意：重载后的乘法和除法运算符在使用时，必须是左边BIG类型右边int类型。

上面的代码只重载了BIG乘int的乘法运算，如果想要支持int乘BIG（左边int类型右边BIG类型），可以再加入一下的代码：

BIG operator* (const int& a, const BIG& b) {return b * a;}//单精度乘高精度

5.重定义mod运算符

BIG operator% (const BIG& a, const int& b){//高精度除以单精度的余数
	//余数 = 被除数 - 除数 × 商
	return a - (a / b * b);
}

四.完整代码

struct BIG{
	static const int MR = 1010;
	int l;//表示整数位数
	int num[MR];
	//构造函数
	BIG(){
		memset(num, 0, sizeof(num));
		l = 1;
	}
	//单精度化高精度
	void set(int n){
		memset(num, 0, sizeof(num));
		l = 0;
		while(n > 0){
			l++;
			num[l] = n % 10;
			n /= 10;
		}
		if (l == 0) l++;
	}
	//字符串化高精度
	void set(string s){
		memset(num, 0, sizeof(num));
		l = s.length();
		for (int i = 1; i <= l; i++){
			num[i] = s[l - i] - '0';
		}
		//数组num的十进制写法是反过来储存的
	}
	void print(){
		//从高位输出到低位
		for (int i = l; i >= 1; i--){
			printf("%d", num[i]);
		}
		printf("\n");//最后要输出一个换行
	}
};

bool operator< (const BIG& a, const BIG& b){
	if(a.l != b.l) return a.l < b.l;//位数少的较小
    //若位数相等从高位开始比较
	for (int i = a.l; i >= 1;i--){
		if(a.num[i] != b.num[i]) return a.num[i] < b.num[i];
	}
	return false;//如果运行到这一步，说明两个数完全相同
}

bool operator>(const BIG &a, const BIG &b) { return b < a; }
bool operator==(const BIG &a, const BIG &b) { return !(b < a) && !(a < b); }
bool operator!=(const BIG &a, const BIG &b) { return b < a || a < b; }
bool operator<=(const BIG &a, const BIG &b) { return !(b < a); }
bool operator>=(const BIG &a, const BIG &b) { return !(a < b); }

BIG operator+ (const BIG& a, const BIG& b){//高精度加高精度
	BIG c;
	c.l = max(a.l, b.l);
	int u = 0;//记录进位多少
	for (int i = 1; i <= c.l; i++){
		int t = a.num[i] + b.num[i] + u;
		c.num[i] = t % 10;
		u = t / 10;
	}
	if(u > 0){//如果最高位进了位，c会比a和b多一位
		c.l++;
		c.num[c.l] = u;
	}
	return c;
}

BIG operator- (const BIG& a, const BIG& b){//高精度减高精度
	BIG c;
	c.l = max(a.l, b.l);
	int u = 0;//记录借位
	for (int i = 1; i <= c.l; i++){
		int t = a.num[i] - b.num[i] - u;
		if(t < 0){//小于0说明不够减
			c.num[i] = t + 10;
			u = 1;
		}else{
			c.num[i] = t;
			u = 0;
		}
	}
	while (c.num[c.l] == 0 && c.l > 1)//找到最高的非零位
		c.l--;
	return c;
}

BIG operator* (const BIG& a, const BIG& b){//高精度乘高精度
	BIG c;
	c.l = a.l + b.l - 1;
    for (int i = 1; i <= a.l; i++){
        for (int j = 1; j <= b.l; j++){
            c.num[i + j - 1] += a.num[i] * b.num[j];
            c.num[i + j] += c.num[i + j - 1] / 10;
            c.num[i + j - 1] %= 10;
        }
    }
    while (c.num[c.l + 1] > 0)
    { //若a的最高位乘完了之后还需要进位，c会比a位数多
        c.l++;
        c.num[c.l + 1] = c.num[c.l] / 10;
        c.num[c.l] %= 10;
    }
	return c;
}

BIG operator* (const BIG& a, const int& b){//高精度乘单精度
	BIG c;
	c.l = a.l;
	int u = 0;//记录进位多少
	for (int i = 1; i <= c.l; i++){
		int t = a.num[i] * b + u;
		c.num[i] = t % 10;
		u = t / 10;
	}
	while (u > 0){//若a的最高位乘完了之后还需要进位，c会比a位数多
		c.l++;
		c.num[c.l] = u % 10;
		u /= 10;
	}
	return c;
}

BIG operator* (const int& a, const BIG& b) {return b * a;}//单精度乘高精度

BIG operator/ (const BIG& a, const int& b){//高精度除以单精度
	BIG c;
	c.l = a.l;
	int r = 0;//记录余数
	//从最高位开始除
	for (int i = c.l; i>= 1; i--){
		int t = r * 10 + a.num[i];
		c.num[i] = t / b;
		r = t % b;
	}
	
	while (c.num[c.l] == 0 && c.l > 1){//找到最高的非零位
		c.l--;
	}
	return c;
}

BIG operator% (const BIG& a, const int& b){//高精度除以单精度的余数
	//余数 = 被除数 - 除数 × 商
	return a - (a / b * b);
}

五.实例

例题

【题目描述】

小A有一个藏着宝物的箱子，为了让人无法打开这个箱子，他给箱子的密码锁进行了复杂的加密。加密会使用 +,-×,÷ 四种运算，经过复杂的加密之后他终于得到了加密之后的数字，但是他却忘记了原本的密码是什么？唯一值得庆幸的是他记录下来了加密的操作的整个操作序列，请你帮他还原最初的密码。

【输入格式】

输入共 n+1 行：

第 1 行，2 个正整数 n，num，分别表示操作次数和最终的密码数字；

接下来 n* 行，每行 22 个数据，操作符 op 和操作数 x。

例如：当 op = '+' 时，表示将当前数加上 x。

【输出格式】

输出共 1 行：

还原之后的密码。

【输入样例#1】

【输出样例#1】

【说明/提示】

1 ≤ n ≤ 100；1 ≤ x,num ≤ 100000000；

数据保证只要程序正确，运算中所有的运算结果均为正整数

2021/6/5 09:24