网站内页百度不收录,营销型网站如何策划,宜春网站建设联系方式,小制作图片1. 简介
我们知道现代的计算机大多数都是64位的#xff0c;因此能处理最大整数为 2 64 − 1 2^{64}-1 264−1。那如果是超过了这个数怎么办呢#xff0c;那就需要我们自己手动模拟数的加减乘除了。
2. 思路
我们可以用一个数组来存储大数#xff0c;数组中的每一个位置表…1. 简介
我们知道现代的计算机大多数都是64位的因此能处理最大整数为 2 64 − 1 2^{64}-1 264−1。那如果是超过了这个数怎么办呢那就需要我们自己手动模拟数的加减乘除了。
2. 思路
我们可以用一个数组来存储大数数组中的每一个位置表示一个数位。为了方便我们直接用 S T L STL STL中的vector来存。
2.1 大数加法
我们需要把两个大数的最低位对齐然后再开始相加。唯一需要注意的是处理一下最高位置的进位置。
2.2 大数减法
大数减法跟加法不一样的是我们需要处理相减后的前导0因为有可能出现相减为0的情况。处理前导0只需要从最高位开始到第2位的连续0。
2.3 大数乘法
大数乘法与加法不同的是每次相乘后放到相应的位置而不是相乘的位次本身。
2.4 大数除法
大数除法是最难的我们用减法进行模拟。
假设两个大数为 a b a\ b a b a a a为除数 b b b为被除数。
我们每次需要找到最接近被除数的除数的进制次倍数 m m m D 0 : { d : a × 1 0 d ≤ b } d 0 max { D 0 } m 0 a × 1 0 d 0 D_0 : \{d: a\times 10^d \le b\}\\ d_0 \max \{D_0\}\\ m_0a \times 10^{d_0} D0:{d:a×10d≤b}d0max{D0}m0a×10d0 通过大数减法算出 t 0 ⌊ b / m 0 ⌋ t_0 \lfloor b/m_0 \rfloor t0⌊b/m0⌋, 因此商需要加上 a n s a n s t 0 1 0 d 0 ans ans t_010^{d_0} ansanst010d0。
此时余数为 b 1 b_1 b1如果 b 1 a b_1a b1a说明我们的除法做完了否则令 b b 1 bb_1 bb1, 继续重复上面的过程直到 b k a b_k a bka。
2.5 符号问题
我们在加减乘除的时候
可以将符号问题单独考虑。
因此可以写一个绝对值的大数相加还有一个版本
的一个大的大数减一个小的大数的大数减法。
而至于乘除法的符号问题比较容易处理因此可以
一同处理符号的问题。
3. 实现
放在gitee上了。
4. TODO
更加丰富的测试样例加减乘除未兼容普通整数大数除法中的负数的商不是最小非负余数
