• C++
  • 高精度除以高精度模板

  • @ 2023-12-9 17:57:03
#include<bits/stdc++.h>
using namespace std;

//比较函数,比较两个可变数组A和B的大小
bool cmp(vector<int> &A, vector<int> &B){
	//如果两个可变数组长度不相等,返回A的长度是否大于B的长度
	if(A.size()!=B.size()) return A.size()>B.size();
	//从后往前遍历,比较A和B的每一个元素
	for(int i=A.size()-1;i>=0;i--){
		//如果A和B的元素不相等,返回A的元素是否大于B的元素
		if(A[i]!=B[i]) return A[i]>B[i]; 
	}
	//如果A和B完全相等,返回true
	return true;
}

//求两个可变数组A和B的差值
vector<int> sub(vector<int> &A,vector<int> &B){
	//定义一个可变数组C,用来存储A和B的差值
	vector<int> C;
	//定义一个变量t,用来存储A和B的差值
	int t=0;
	//从前往后遍历,计算A和B的差值
	for(int i=0;i<A.size()||t;i++){
		//计算A和B的差值
		t = A[i] - t;
		//如果B的长度大于A的长度,则减去B的元素
		if(i<B.size()) t -= B[i];
		//将A和B的差值放入C中
		C.push_back((t+10)%10);
		//如果A和B的差值为负数,则将t置为1
		if(t<0) t = 1;
		//否则将t置为0
		else t = 0;
	}
	//如果C的最后一个元素为0,则将其弹出
	while(C.size()>1&&C.back()==0) C.pop_back();
	//返回C
	return C;
}

//求两个可变数组A和B的商和余数
vector<int> div(vector<int> &A, vector<int> &B, vector<int> &r){
	//定义一个可变数组C,用来存储商
	vector<int> C;
	//如果A和B不相等,则商为0,余数为A
	if(!cmp(A,B)){ 
		C.push_back(0); 
		r.assign(A.begin(),A.end()); 
		return C; 
	}
	//定义一个变量j,用来记录B的长度
	int j = B.size();
	//将A剩余的元素赋值给r
	r.assign(A.end()-j,A.end());
	//当j小于A的长度时,循环计算商和余数
	while(j<=A.size()){
		//定义一个变量k,用来记录商
		int k=0;
		//当r和B不相等时,循环计算商
		while(cmp(r,B)){
			//计算r和B的差值
			vector<int> s = sub(r,B);
			//将r的差值赋值给r
			r.clear();
			r.assign(s.begin(),s.end());
			//k自增
			k++;
		}
		//将商放入C中
		C.push_back(k);
		//如果j小于A的长度,则将A剩余的元素放入r中
		if(j<A.size()) r.insert(r.begin(),A[A.size()-j-1]);
		//如果r的长度大于1,且r的最后一个元素为0,则将其弹出
		if(r.size()>1&&r.back()==0) r.pop_back();
		//j自增
		j++;
	}
	//将C反转
	reverse(C.begin(),C.end());
	//如果C的最后一个元素为0,则将其弹出
	while(C.size()>1&&C.back()==0) C.pop_back();
	//返回C
	return C;
}

int main(){
	//定义两个字符串a和b
	string a,b;
	//从标准输入中读取a和b
	cin>>a>>b;
	//定义两个可变数组A、B和r
	vector<int> A,B,r;
	//将a的每一个元素转换为数字,放入A中
	for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
	//将b的每一个元素转换为数字,放入B中
	for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
	
	//调用div函数,计算商和余数
	auto C = div(A,B,r);
	//将商放入标准输出中
	for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
	printf("\n");
	//将余数放入标准输出中
	for(int i=r.size()-1;i>=0;i--) printf("%d",r[i]);
	return 0;
}

0 条评论

目前还没有评论...