大数除法，哪个算法实现最好

问题描述

求两个大的正整数相除的商

输入数据

第1行是测试数据的组数n，每组测试数据占2行，第1行是被除数，第2行是除数。每组测试数据之间有一个空行，每行数据不超过100个字符

输出要求

n行，每组测试数据有一行输出是相应的整数商

输入样例

3

2405337312963373359009260457742057439230496493930355595797660791082739646

2987192585318701752584429931160870372907079248971095012509790550883793197894

10000000000000000000000000000000000000000

10000000000

5409656775097850895687056798068970934546546575676768678435435345

1

输出样例

0

1000000000000000000000000000000

5409656775097850895687056798068970934546546575676768678435435345

解题思路

基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以7546除以23为例来看一下：开始商为0。先减去23的100倍，就是2300，发现够减3次，余下646。于是商的值就增加300。然后用646减去230，发现够减2次，余下186，于是商的值增加20。最后用186减去23，够减8次，因此最终商就是328。

所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。

计算除数的10倍、100倍的时候，不用做乘法，直接在除数后面补0即可。

#include <stdio.h>

#include <string.h>

#define MAX_LEN 200

char szLine1[MAX_LEN + 10];

char szLine2[MAX_LEN + 10];

int an1[MAX_LEN + 10]; //被除数, an1[0]对应于个位

int an2[MAX_LEN + 10]; //除数, an2[0]对应于个位

int aResult[MAX_LEN + 10]; //存放商，aResult[0]对应于个位

/* Substract函数：长度为 nLen1的大整数p1减去长度为nLen2的大整数p2

减的结果放在p1里，返回值代表结果的长度

如不够减返回-1，正好减完返回 0

p1[0]、p2[0] 是个位 */

int Substract( int * p1, int * p2, int nLen1, int nLen2)

{

int i;

if( nLen1 < nLen2 )

return -1;

//下面判断p1是否比p2大，如果不是，返回-1

bool bLarger = false;

if( nLen1 == nLen2 ) {

for( i = nLen1-1; i >= 0; i -- ) {

if( p1[i] > p2[i] )

bLarger = true;

else if( p1[i] < p2[i] ) {

if ( ! bLarger )

return -1;

}

}

}

for( i = 0; i < nLen1; i ++ ) { //做减法

p1[i] -= p2[i]; //要求调用本函数时给的参数能确保当i>=nLen2时，p2[i] ＝ 0

if( p1[i] < 0 ) {

p1[i]+=10;

p1[i+1] --;

}

}

for( i = nLen1 -1 ; i >= 0 ; i-- )

if( p1[i] )

return i + 1;

return 0;

}

int main()

{

int t, n;

char szBlank[20];

scanf("%d", &n);

for( t = 0;

问题一、忘了针对每一组测试数据，都要先将an1, an2和aResult初始化成全0，而是一共只初始化了一次。这导致从第二组测试数据开始就都不对了。

问题二、减法处理借位的时候，容易忽略连续借位的情况，比如 10000 – 87，借位会一直进行到1。