高精度除法的实现

        这是C++算法基础-基础算法专栏的第十篇文章，专栏详情请见此处。

---

引入

        上次我们学习了高精度乘法的实现，这次我们要学习高精度除法的实现。

        高精度除法与高精度加法的定义、前置过程都是大致相同的，如果想了解具体内容，可以移步至我的这篇博客：高精度加法计算的实现

        在这里就不再详细讲解，只讲解主体过程qwq

主体过程

        高精度除法的原理和小学学习的竖式除法是一样的。

        

        概括来说，假如被除数长度为，除数长度为，为了减少冗余运算，我们从从后往前开始计算，将被除数与除数相对应的每一位相（整）除，实际上这一步可以看作一个逐次减法的过程，然后存进商的对应位置上，再将余数乘并放进下一位。

          用高精度计算，先除百位，将减去一次后变为，小于，所以将存入百位，将存入十位；

        再除十位，将减去三次后变为，小于，所以将存入十位，将存入个位；

        最后除个位，将减去八次后变为，小于，所以将存入个位，将存入余数数组。

        其实，高精度除法按理来说不需要反转存储，正序存储会更方便，但大部分题目，如果需要高精度除法去做，那么很有可能也需要其他的高精度计算，为了统一，我们还是使用反转存储。

        接下来，我们这里实现一个函数，它判断了被除数以下标为最低位，是否可以再减去除数而保持非负。这个函数分为三部分：

1. 被除数剩余的部分比除数长，这个情况下最多多出 1 位，函数返回真。
2. 如第一步判断为假，就说明被除数与除数一样长，那我们就从高位到低位，逐位比较：如果被除数当前位比除数当前位大，函数返回真；反之，函数返回假。
3. 如第二步也判断为假，就说明被除数与除数相等，相等的情形下也是可行的，函数返回真。

        下面给出高精度除法的代码：

bool big(int a[],int b[],int low,int L){
	if(a[low+L]!=0) return 1;
	for(int i=L-1;i>=0;--i){
		if(a[low+i]>b[i]) 
			return 1;
		if(a[low+i]
			return 0;
	}
	return 1;
}
void div(int a[],int b[],int c[],int d[]){
	clear(c);
	clear(d);
	int la,lb;
	for(la=L-1;la>0;la--){
		if(a[la-1]!=0)
			break;
	}
	for(lb=L-1;lb>0;lb--){
		if(b[lb-1]!=0)
			break;
	}
	if(lb==0) return;
	for(int i=0;i
	for(int i=la-lb;i>=0;i--){
		while(big(d,b,i,lb)){
			for(int j=0;j
				d[i+j]-=b[j];
				if(d[i+j]<0){
					d[i+j+1]-=1;
					d[i+j]+=10;
				}
			}
			c[i]++;
		}
	}
}

高精度计算器（总结）

        到这里，我们的高精度计算就全部完成了。

        下面给出高精度计算器的代码：

const int L=10000;
string s;
int a[L],b[L],c[L],d[L];
void clear(int a[]){
	for(int i=0;i
		a[i]=0;
}
void read(int a[]){
	cin>>s;
	int L=s.size();
	for(int i=0;i
		a[i]=s[L-1-i]-'0';
}
void print(int a[]){
	int i;
	for(i=L-1;i>=1;i--){
		if(a[i]!=0)
			break;
	}
	for(;i>=0;i--)
		cout<
	cout<
}
void add(int a[],int b[],int c[]){
	clear(c);
	for(int i=0;i-1;++i){
		c[i]+=a[i]+b[i];
		if(c[i]>=10){
			c[i+1]+=1;
			c[i]-=10;
		}
	}
}
void sub(int a[],int b[],int c[]){
	clear(c);
	for(int i=0;i-1;++i){
		c[i]+=a[i]-b[i];
		if(c[i]<0){
			c[i+1]-=1;
			c[i]+=10;
		}
	}
}
void mul(int a[],int b[],int c[]){
	clear(c);
	for(int i=0;i-1;i++){
		for(int j=0;j<=i;j++)
			c[i]+=a[j]*b[i-j];
		if(c[i]>=10){
			c[i+1]+=c[i]/10;
			c[i]%=10;
		}
	}
}
bool big(int a[],int b[],int low,int L){
	if(a[low+L]!=0) return 1;
	for(int i=L-1;i>=0;--i){
		if(a[low+i]>b[i]) 
			return 1;
		if(a[low+i]
			return 0;
	}
	return 1;
}
void div(int a[],int b[],int c[],int d[]){
	clear(c);
	clear(d);
	int la,lb;
	for(la=L-1;la>0;la--){
		if(a[la-1]!=0)
			break;
	}
	for(lb=L-1;lb>0;lb--){
		if(b[lb-1]!=0)
			break;
	}
	if(lb==0) return;
	for(int i=0;i
	for(int i=la-lb;i>=0;i--){
		while(big(d,b,i,lb)){
			for(int j=0;j
				d[i+j]-=b[j];
				if(d[i+j]<0){
					d[i+j+1]-=1;
					d[i+j]+=10;
				}
			}
			c[i]++;
		}
	}
}

---

上一篇-高精度乘法的实现    C++算法基础专栏文章    下一篇-一维前缀和的实现

---

每周六更新一篇文章，内容一般是自己总结的经验或是在其他网站上整理的优质内容

点个赞，关注一下呗~