用c++写一个高精度计算的除法运算
高精度除以低精度
以下这段代码的主要作用是将一个大整数(以字符数组形式表示)除以一个整数,并输出结果。具体来说,代码将大整数 a1("1256")除以整数 b(3),并输出商。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
char a1[100]="1256";
int a[100],c[100],lena,i,x=0,lenc,b=3;//a 用于存储被除数,c 用于存储商,x 用于保存进位,lenc 用于记录商的长度,b 是除数。
//分别用于将数组 a 和 c 初始化为零。
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
lena = strlen(a1);
for(i=0;i<=lena-1;i++){//循环遍历被除数的字符,将其转换为整数并存储在数组 a 中。这是将字符数组形式的大整数转换为整数数组形式的关键步骤。
a[i+1]=a1[i]-'0';
}
//遍历数组 a 中的每个数字,逐位执行除法操作,同时考虑上一位的余数 x。商被存储在数组 c 中,余数被保存在 x 中。
for(i=1;i<=lena;i++){
c[i]=(x*10+a[i])/b;//计算当前位置的值
x=(x*10+a[i])%b;//取余,用于下一位的计算
}
lenc=1;//初始化商的长度。
while(c[lenc]==0 && lenc<lena){//去除商中高位的零,同时更新商的长度 lenc。
lenc++;
}
for(i=lenc;i<=lena;i++){
cout<<c[i];
}
cout<<endl;
return 0;
}
代码分析
大整数的表示和转换:首先,代码需要将字符数组
a1
中的大整数("1256")转换为整数数组a
中。这是因为大整数通常会超出内置整数类型的范围,所以需要以数组形式表示。这部分的难点在于正确地将字符数字转换为整数,这里通过'0'
字符的 ASCII 值来实现。逐位除法操作:代码中使用两个循环来实现逐位的除法操作,从高位到低位。每一位的除法操作都需要考虑上一位的余数(
x
),并且在商c
中存储本位的商。进位处理:在除法操作中,余数可能需要被传递到下一位进行处理。这就是
x
变量的作用,用于存储和传递余数。商的长度管理:代码需要正确地管理商的长度,以去除高位的零。这部分的难点在于确定商的实际长度,然后使用一个
while
循环来去除高位的零。
高精度除以高精度
在这种情况下,通常使用减法模拟来实现长除法。被除数的每一位都减去除数,一直减到当前位置的数字小于除数。然后,商的当前位增加1,然后继续减法操作。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[101],b[101],c[101],d,i;
void init(int a[],string s){
a[0]=s.length();
for(i=1;i<=a[0];i++){
a[i]=s[a[0]-i]-'0';
}
}
void print(int a[]){
int i;
if(a[0]==0 ){
cout<<0<<endl;
return;
}
for(i=a[0];i>0;i--){
cout<<a[i];
}
cout<<endl;
return;
}
int compare(int a[],int b[]){
int i;
if(a[0]>b[0]) {
return 1;
}
if(a[0]<b[0]) {
return -1;
}
for(i=a[0];i>0;i--){
if(a[i]>b[i]) {
return 1;
}
if(a[i]<b[i]) {
return -1;
}
}
return 0;
}
void jian(int a[],int b[]){
int flag,i;
flag=compare(a,b);
if(flag==0){
a[0]=0;
return;
}
if(flag==1){
for(i=1;i<=a[0];i++) {
if (a[i] < b[i]) {
a[i + 1]--;
a[i]+=10;
}
a[i] -= b[i];
}
while(a[0]>0 && a[a[0]]==0){
a[0]--;
}
return;
}
}
void numcpy(int p[],int q[],int det){
for (int i=1;i<=p[0];i++){
q[i+det-1]=p[i];
}
q[0]=p[0]+det-1;
}
void chugao(int a[],int b[],int c[]){
int i,tmp[101];
c[0]=a[0]-b[0]+1; // 设置商的长度,初始为被除数长度减去除数长度加1
for(i=c[0];i>0;i--){
memset(tmp,0,sizeof(tmp));
numcpy(b,tmp,i);// 复制除数 b 到 tmp 数组,同时指定偏移量 i
while(compare(a,tmp)>=0) {
c[i]++;
jian(a, tmp);
}
}
while(c[0]>0 && c[c[0]]==0){
c[0]--;
}
return;
}
int main(){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
init(a,"1000");
init(b,"3");
chugao(a,b,c);
print(c);
print(a);
return 0;
}
代码分析
这段代码是一个C++程序,它执行了大整数的除法操作。具体来说,它实现了两个大整数(可以超过标准整数范围)的相除,并输出结果。
chugao
函数的目的是执行大整数的除法操作,它使用循环来模拟手工的长除法过程,得到商(c 数组)和余数(a 数组)。
下面是 chugao
函数的详细分析:
void chugao(int a[], int b[], int c[]) {
int i, tmp[101];
c[0] = a[0] - b[0] + 1; // 设置商的长度,初始为被除数长度减去除数长度加1
for (i = c[0]; i > 0; i--) {
memset(tmp, 0, sizeof(tmp)); // 清空 tmp 数组
numcpy(b, tmp, i); // 复制除数 b 到 tmp 数组,同时指定偏移量 i
while (compare(a, tmp) >= 0) {
c[i]++; // 假设商的当前位为 1
jian(a, tmp); // 从被除数 a 中减去 tmp(相当于减去除数 b)
}
}
while (c[0] > 0 && c[c[0]] == 0) {
c[0]--; // 去除商中的前导零
}
return;
}
详细步骤:
首先,函数会计算商
c
的长度,由c[0]
表示,计算方式是被除数a
的长度减去除数b
的长度,再加1。这是因为商的位数可能比这个计算结果多一位,以容纳小数部分。然后,使用
for
循环从商的最高位向最低位处理每一位。在每次循环迭代中,首先清空
tmp
数组,用memset
函数将其所有元素初始化为 0。tmp
数组用于存储除数b
,并且会在不断的迭代中右移,模拟手工长除法的过程。使用
numcpy
函数将除数b
复制到tmp
数组中,并指定偏移量i
。这相当于将b
放在正确的位置,以便与被除数a
进行比较和减法操作。进入内部循环,该循环会一直执行,直到无法再减去
tmp
为止。在每次迭代中,假设商c
的当前位为1,然后从被除数a
中减去tmp
。这模拟了手工长除法中的减法步骤。最后,退出内部循环后,通过检查商
c
的最高位是否为0来去除可能存在的前导零。