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

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

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

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

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

数组 0 1 2 34
a[]00700
b35
c[]00000
余数0

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

数组 0 1 2 34
a[]00700
b35
c[]00000
余数0→7→7

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

数组 0 1 2 34
a[]00700
b35


c[]00000
余数7→70→0

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

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

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

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

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

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


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

第一部分就是判断能否除,
那这部分啊-其实很简单,只有一步,就是判断目前退位到的被除数是否比除数大(相等也行)
比较的程序就很简单了:
先判断位数,再从最高位开始比起,以此往下比,比到最后一位,如果相等,那么也可以作除法
代码如下:
第二部分和第三部分本质上就是除法
高精除以低精的除法的程序我们按部就班,把中间的除法变成减法的程序然后再加上判断是否能除,然后余数的部分省略就好了:
代码如下:
剩下就是高精度输入-存储-输出代码。
接下来是完整代码:
已有 1 人购买  本主题需向作者支付 5 鱼币 才能浏览 购买主题

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

加油!但可惜限额没了
页: [1]
查看完整版本: 高精度除法(仅代码部分付费)