算法之高精度（七）

前一篇内容简单描述了：高精度数字和常规数字相乘
相对于乘法，高精度除法在高精度算法中比较难的部分。原因是不论加减乘的内容，我们始终只需要去计算，而除法就会涉及到判断。我们必须了解到被除数÷除数=商…余数。余数不能大于除数，也不能小于0。这是我们需要控制的。
这篇我们将详细介绍两个高精度数字相除。首先，我想我还是需要提醒一下大家。

除法的原理是什么？

我常常称除法是减法的快速运算。如何理解这句话呢？我们设想，一个盘子里有10个苹果，需要分给3位小朋友，请问每位小朋友能分到几个？你会很快反应出来，3个。你的结果基于除法，10÷3=3...1。结果会剩下一个苹果。在学习除法之前，当你被问及这个问题时，我们常常会如此解释，每位同学每人拿一个，10-3=7，剩下7个，显然每位同学还可以拿。7-3=4，剩下4个，很显然还是可以拿。4-3=1，结果为1个，不够每位同学拿一个了。到这里就计算结束了。每位同学拿的次数就是分到的苹果数。剩下的苹果数量就是余数。
按照这样的道理，高精度数字相除也可以使用减法模拟出来，只不过需要一直使用被除数减去除数，直到余数小于除数。这是一个好方法。但对于两个高精度数字相差太大的话，减去的次数就有些不可控了。例如：346,334,834,985,792÷32,782,321,649——15位数除以11位数，使用减法模拟除法的方式，我们需要减10000多次，甚至不止如此。这是非常庞大的计算量。我有时会很担心使用这种方法计算，我的电脑能不能坚持运行完这个程序。
我们尝试使用一个新的方法。我们在数学书里很少简单，但生活中却运用自如的方式。我们假设1600÷13，你会怎么想？1600会分解成1300+300，其中1300÷13=100，剩下的300才继续运算。使用这种方法计算便会简单许多，但这个方法可能会因数字而异，对于一个难拆分的数字，我们就会犯难了。比如说12340÷234，你会想到怎么拆分？
我们采用补0的方式会更好。我们使234变成2340，然后在将12340÷2340 = 5，计算速度快了许多，5将作为十位数，剩下的余数再次对234求解。当然，这里的除法我们仍然使用减法进行模拟，也就是说，使12340减去2340，减去5次，就可以得到余数小于除数的情况。本来应该减去50次的量，转变成了5次，这样的改变我们将为之欢喜。
文字的描述总没有表格直观，我们使用表格将文字内容转换出来。这样更简洁。

表格中被除数减去第一次转换的除数，得到结果作为百位数字，结果为0，减去之后结果为余数。余数减去第二次转换的除数，得到结果作为十位数字，结果为5，减去之后的结果为余数。再次使用新产生的余数减去第三次转换的除数，得到结果作为个位数字。这里的减去指的是减到余数小于除数。
这是我们用作两个高精度数字相除的方式。下面我们将尝试使用程序描述这一过程。

//假设a1,a2为两个高精度数字，a1为被除数，a2为除数
//假设a1,a2都已定义，且逆向存放
//length1, length2 分别表示a1,a2的位数//判断余数是否小于除数
//false 表示余数大于等于除数，此时应继续使用减法
//true 表示余数小于除数，不应继续使用减法
bool isSmall(int a1[], int tmp[], int length1, int length2)
{if(length1 > length2)	//余数位数大于除数位数return false;if(length1 < length2)	//余数位数小于除数位数return true;//两个位数相同，从高到低比较每一位，某一位越大，数字越大for(int i = length1 - 1; i >= 0; --i){if(a1[i] > tmp[i])	//余数数字大于除数数字return false;if(a1[i] < tmp[i])	//余数数字小于除数数字return true;}return false;	//余数与除数完全相同，应继续使用减法
}//减法，被除数减去除数得到余数
//计算结果存放在a1中，由于a1的位数可能发生变化，因此使用 &length 引用传参
void sub(int a1[], int tmp[], int &length1, int length2)
{for(int i = 0;i < length1; ++i){a1[i] -= tmp[i];	//对应数位相减if(a1[i] < 0)	//结果可能需要借位{a1[i + 1] -= 1;	//借位，高位减少1a1[i] += 10;	//本位转换为正数}}//计算最终a1中有效位数//去前导0int k = length1 - 1;while(a1[k] == 0 && k >= 0)--k;//经过循环得到的k为高位第一个不为0的数字对应的下标，并不是位数length1 = k + 1;	//将结果位数调整至实际情况
}//两个高精度整数相除
void division(int a1[], int a2[], int length1, int length2)
{int result[100] = {};	//假设a1,a2的商不超过100位数，result用来存放商//商的位数，商的位数不超过被除数的位数减去除数的位数 + 1int length = length1 - length2 + 1;	for(int i = length; i > 0; --i){//i表示每次转换时的总位数int tmp[100] = {};	//临时保存转换后的除数//转换除数for(int j = 0; j < length2; ++j)tmp[j + i - length2] = a2[j];while(isSmall(a1, tmp, length1, i) == 0){sub(a1, tmp, length1, i);++result[i];}}//经过多轮计算，得到的商存放在result数组中，并逆向存放//余数存放在a1中int k = length;while(result[k] == 0 && k > 0)--k;for(int i = k; i > 0; --i)cout << result[i];		//输出商cout << endl;//输出余数for(int i = length1 - 1; i >= 0; --i)cout << a1[i];	//输出余数
}

按照这样的方式，两个高精度数字相除的程序我们总算描述结束了。其中还是有一些需要提醒的地方。例如，参数中使用了引用传参的方式，使用多个函数辅助等等。
我觉得，对于上述描述的求解方式应该是大家关注的点。至于代码描述，每一个人都可能实现出不同的版本。当然，代码中每一处细节，我还是希望各位能够钻研。这是有益的。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！