首页 > 编程语言 >用c++写一个高精度计算的除法运算

用c++写一个高精度计算的除法运算

时间:2023-10-30 13:01:03浏览次数:33  
标签:tmp 高精度 int 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;
}

代码分析

  1. 大整数的表示和转换:首先,代码需要将字符数组 a1 中的大整数(“1256”)转换为整数数组 a 中。这是因为大整数通常会超出内置整数类型的范围,所以需要以数组形式表示。这部分的难点在于正确地将字符数字转换为整数,这里通过 '0' 字符的 ASCII 值来实现。
  2. 逐位除法操作:代码中使用两个循环来实现逐位的除法操作,从高位到低位。每一位的除法操作都需要考虑上一位的余数(x),并且在商 c 中存储本位的商。
  3. 进位处理:在除法操作中,余数可能需要被传递到下一位进行处理。这就是 x 变量的作用,用于存储和传递余数。
  4. 商的长度管理:代码需要正确地管理商的长度,以去除高位的零。这部分的难点在于确定商的实际长度,然后使用一个 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;
}

详细步骤:

  1. 首先,函数会计算商 c 的长度,由 c[0] 表示,计算方式是被除数 a 的长度减去除数 b 的长度,再加1。这是因为商的位数可能比这个计算结果多一位,以容纳小数部分。
  2. 然后,使用 for 循环从商的最高位向最低位处理每一位。
  3. 在每次循环迭代中,首先清空 tmp 数组,用 memset 函数将其所有元素初始化为 0。tmp 数组用于存储除数 b,并且会在不断的迭代中右移,模拟手工长除法的过程。
  4. 使用 numcpy 函数将除数 b 复制到 tmp 数组中,并指定偏移量 i。这相当于将 b 放在正确的位置,以便与被除数 a 进行比较和减法操作。
  5. 进入内部循环,该循环会一直执行,直到无法再减去 tmp 为止。在每次迭代中,假设商 c 的当前位为1,然后从被除数 a 中减去 tmp。这模拟了手工长除法中的减法步骤。
  6. 最后,退出内部循环后,通过检查商 c 的最高位是否为0来去除可能存在的前导零。


标签:tmp,高精度,int,c++,整数,数组,除法,除数
From: https://blog.51cto.com/u_16065421/8087724

相关文章

  • c++ .h头文件和.cpp源文件关系(转)
    https://www.cnblogs.com/fengzhengfly/p/8884581.htmlhttps://blog.csdn.net/qq_35452533/article/details/77282326头文件是声明,源文件是定义在cpp里包含.h,就会包含该h文件的cpp定义,所以需要在cpp里使用别的.h文件中的函数只能包含该.h,或者已包含的.h中已经包含的改.h,也就......
  • c++同样结构体名冲突报错
    两个不同的头文件中有同名的结构体在编译项目文件的时候出现报错,结构体多次定义,其中一个头文件a的结构体是typedefstruct{doublex,y;}Point;另外一个头文件b是typedefstructPoint{ int16cardinality; uint8num_coords; /*Opendimensioncoordinatesa......
  • C++实验心得
    C++类文件写通讯录系统生成项目,创建类文件...调出工作区,manager属性类文件运用string型变量的找不到此数据类型问题,需要在对应.h文件定义上命名空间并引用<string>头文件类文件引用主函数全局变量main.cpp externinta; //导出 ...Class_one.cpp inta; //去ex......
  • C++小练习:字符串分割的高性能实现
    字符串分割是日常工作中比较常见的基础函数,通常大家会使用现成的基础库,基础库的性能是否是最佳的?本文基于一个周末小练习,研究如何最大限度的提升字符串分割的性能。  1、背景字符串按照分隔符拆成多个子串在日常工作中很常见,譬如:后台服务对配置的解析、模型服务对输入特征的......
  • C++基础(2)
    将数组传入函数禁止修改数组的值函数的地址与函数的指针函数的指针数组函数的static与inline引用左值和引用传参C++11的数组for循环64位Linux操作系统中C++中常见基本类型所占字节数C++11类成员变量的初始化默认成员初始化器成员变量初始化列表委......
  • C++基础(3)
    类的继承基类与派生类之间的构造行为在派生类中使用基类方法protected的访问权限多态公有继承关键字virtual示例抽象基类(ABC)私有继承和保护继承多重继承类的继承基类与派生类之间的构造行为派生类可以调用基类的公共成员,但无法调用基类的私有成员。所......
  • 简单c++构建第一人称
    本文内容为UE4.27的文档教程GameMode确定新建的项目会自动生成GameMode,如果有更改,而不是使用默认的GameMode类,就需要在引擎的设置中更改角色的实现前后左右移动//前后MoveForwardvoidAFPSCharacter::MoveForward(floatvalue){ //利用控制器方向寻找前进的方向就是角色......
  • C++多线程编程——线程的基本概念和使用方法
    什么是线程?在计算机科学中,线程是进程中的一个执行控制单元,也被称为执行路径。每个进程可以包含多个线程,每条线程并行执行不同的任务。线程是操作系统可识别的最小执行和调度单位。进程和线程的区别进程是程序在某个数据集合上的一次运行活动,也是操作系统进行资源分配和保护的......
  • 【C++】继承 ⑬ ( 虚继承原理 | 虚继承解决继承二义性问题 | 二义性产生的原因分析 )
    文章目录一、虚继承原理1、虚继承解决继承二义性问题2、二义性产生的原因分析3、虚继承原理二、代码示例-虚继承原理1、完整代码示例2、执行结果一、虚继承原理1、虚继承解决继承二义性问题继承的二义性:如果一个子类(派生类)继承多个父类(基类),这些父类都继......
  • 【C++】继承 ⑩ ( 继承机制中的 static 静态成员 | 子类中访问父类静态成员的方法 )
    文章目录一、继承机制中派生类中的static关键字1、子类继承父类静态成员2、父类静态成员访问控制权限的改变3、子类如何访问父类静态成员4、静态成员使用要点二、完整代码示例一、继承机制中派生类中的static关键字1、子类继承父类静态成员子类继承父类静态成员:父类(......