高精度除法（仅代码部分付费）

bangbang-ande · 发表于 2023-7-13 09:52:36

高精度除法的基本问题如下：

问题描述：已知两个数a，b，求两个数的商
数据输入：700 35
数据输出：20
数据范围： 1≤b,a≤10^1000

高精度除法是四种高精度中比较好理解，但不好写的算法，高精度除法总共有两种形式：
高精/低精；高精/高精

高精除以低精的难度比较简单，可以运用简单的除法进行。除法的方法相信大家很熟悉了，这里我们用表格呈现除法：

数组	0	1	2	3	4
a[]	0	0	7	0	0
b	35
c[]	0	0	0	0	0
余数	0

解释一下表格的内容：第二列是数组a[]，表示被除数，第三列是数组b变量，表示除数，第四列数组c[]，表示商。
那么我们首先就是除法，在没讲高精度除以高精度前，现在就可以直接进行除法运算
倒序取出第一个数，将7加入余数中，用余数除以除数，即7÷35=0……7，将这一位的商写入0，余数写入7；

数组	0	1	2	3	4
a[]	0	0	7	0	0
b	35
c[]	0	0	0	0	0
余数	0→7→7

（箭头是发生过的变化）
接着是下一步，此时将余数进行保留之后，乘10，也就是7×10=70，将数组a[]向后退一位到1的位置，然后加入这一位对应的数0，
同样地用余数进行除法运算，就是70÷35=2……0，然后将这一位置的商写入2，余数写入0；

数组	0	1	2	3	4
a[]	0	0	7	0	0
b	35
c[]	0	0	0	0	0
余数	7→70→0

接着继续按同样的步骤计算，就可以得到最后的结果了。

高精除以低精的除法的步骤就是一步一步相除，得到结果，没有任何的技巧，除法的核心代码如下（因为上文的存储是倒序的，所以这里也只能够写倒序的了，在写的时候可以正序写（不过得保证输入输出正序））：
（所有代码均要付费查看）

接着我们把其余的部分加入，最后的程序是这样的：
接下来就是比较难操作的高精度除以高精度了
我们知道，除法的本质是减法，多次的减法就是除法
所以高精度除以高精度的本质方法就是减法：
通过一次次的相减，得到最后的结果

但是——
我一个数除以另一个数的商太大怎么办？
这样会超时的啊，
所以减法就得精简起来
那么怎么精简呢？——高精除以低精的重要性就在这里了
在高精除以低精中，我们是除完一位再除下一位，
那减法，是不是沿用除法的方法就可以了

那么高精除以高精的整个步骤如下：

1. 判断是否能够除
2. 进行减法操作，每减一次，商+1，减到这一位的除数比商大为止。
3. 退位，将除数移至下一位再作除法。

接下来我们来逐步剖析这三个部分：

第一部分就是判断能否除，
那这部分啊-其实很简单，只有一步，就是判断目前退位到的被除数是否比除数大（相等也行）
比较的程序就很简单了：
先判断位数，再从最高位开始比起，以此往下比，比到最后一位，如果相等，那么也可以作除法
代码如下：
第二部分和第三部分本质上就是除法
高精除以低精的除法的程序我们按部就班，把中间的除法变成减法的程序然后再加上判断是否能除，然后余数的部分省略就好了：
代码如下：
剩下就是高精度输入-存储-输出代码。
接下来是完整代码：

购买主题 已有 1 人购买 本主题需向作者支付 5 鱼币 才能浏览

歌者文明清理员 · 发表于 2023-7-13 10:27:48

加油！但可惜限额没了

账号		自动登录	找回密码
密码			立即注册

[技术交流] 高精度除法（仅代码部分付费）