高精度除法的实现

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

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

主体过程

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

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

$12345\div 89$ 用高精度计算，先除百位，将 $123$ 减去 $89$ 一次后变为 $34$ ，小于 $89$ ，所以将 $1$ 存入百位，将 $34\times 10$ 存入十位；

再除十位，将 $34\times 10+4$ 减去 $89$ 三次后变为 $77$ ，小于 $89$ ，所以将 $3$ 存入十位，将 $77\times 10$ 存入个位；

最后除个位，将 $77\times 10+5$ 减去 $89$ 八次后变为 $63$ ，小于 $89$ ，所以将 $8$ 存入个位，将 $63$ 存入余数数组。

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

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

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

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

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]<b[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<la;i++) d[i]=a[i];for(int i=la-lb;i>=0;i--){while(big(d,b,i,lb)){for(int j=0;j<lb;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<L;i++)a[i]=0;
}
void read(int a[]){cin>>s;int L=s.size();for(int i=0;i<L;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<<a[i];cout<<endl;
}
void add(int a[],int b[],int c[]){clear(c);for(int i=0;i<L-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<L-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<L-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]<b[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<la;i++) d[i]=a[i];for(int i=la-lb;i>=0;i--){while(big(d,b,i,lb)){for(int j=0;j<lb;j++){d[i+j]-=b[j];if(d[i+j]<0){d[i+j+1]-=1;d[i+j]+=10;}}c[i]++;}}
}

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

点个赞，关注一下呗~

高精度除法的实现

主体过程

高精度计算器（总结）

最新新闻

热搜词