高精度正整数除法 大整数除法

标签（空格分隔）： 算法竞赛 算法 编程错题 高精度

---

单词：    divident:被除数    divisor：除数    quotient：商

---

大整数除法 OpenJ_Bailian - 2737

题目要求：求两个大的正整数相除的商。    input：第1行是被除数，第2行是除数。每个数均不超过100位。    output：一行，相应的商的整数部分    Sample Input：    2376    24    Sample Output：    99

---

算法是这样的，我们以减法代替除法，计算能够减多少次。既然这样，第一个思路就是模拟减法了。但是做的时候发现，模拟减法慢的出奇，需要调用数组很多次，七位数除以一位数时时间就到1秒了。所以必须换思路。

第二种思路的时间复杂度是小的多的，但是思考起来很难，实现起来更加的难。

除法的模拟法是这样的：

1. 计算被除数与除数相差的位数t
2. 计算dividend-divisor*10^t
3. 重复计算2，直到结果小于0时，记录计算次数j，j*10^t作为商的一部分，计算j=j+j*10^t(初始j为0)。将t-1，继续计算2
4. 不断重复上述过程，每次的j[k++]循环相加，直到t=0，此时的j即为商。

实现起来很麻烦的。代码如下

#include 
    
     #include 
     
      #define N 101int dd[N],ds[N],qu[N];char str1[N],str2[N];int sub(int* dd,int* ds,int len1,int len2)  //这个函数是重点难点 {
        int i;    if (len1
      
       =0;i--)        {            if (dd[i]
       
        ds[i])                break;        }    for (i=0;i
        
         =0;i--)        if (dd[i])  break;    return i+1;}int main(){    int i,j,k;    gets(str1);    gets(str2);    int len1=strlen(str1),len2=strlen(str2);    for (k=0,i=len1-1;i>=0;i--)        dd[k++]=str1[i]-'0';    for (k=0,i=len2-1;i>=0;i--)        ds[k++]=str2[i]-'0';    len1=sub(dd,ds,len1,len2);    if (len1==-1)    {        printf("0\n");        return 0;    }    else if (len1==0)    {        printf("1\n");        return 0;    }    qu[0]=1;    int times=len1-len2;    for (i=len1-1;i>=0;i--)             //从这一行到72行是重点难点！     {        if (i>=times)            ds[i]=ds[i-times];        else            ds[i]=0;    }    len2=len1;    for (j=0;j<=times;j++)    {        int tmp;        while ((tmp=sub(dd,ds+j,len1,len2-j))>=0)        {
                len1=tmp;            qu[times-j]++;        }    }    for (i=0;i
         
          9) { qu[i+1]+=qu[i]/10; qu[i]%=10; } } for (i=N-1;qu[i]==0&&i>=0;i--); while (i>=0) printf("%d",qu[i--]); printf("\n"); return 0;}
         
        
       
      
     
    

---

先定义了sub函数，判断输入的高精度被除数和除数的大小关系，被除数小与除数，则返回-1，否则，计算被除数减除数，将结果赋给被除数，再计算被除数此时的位数，返回位数。

对于main函数，先是老套路，用字符串数组保存输入的高精度数，计算位数，之后用整型数组逆序存放每一位，之后执行一次sub，判断、排除被除数小于等于除数的情况。

由于已进行了一次减法，所以商（同样按位数逆序存储）要先+1。

之后line56~line72，就是重点和难点了。

先是line56~line62，是在模拟乘10的幂次运算。由于数据保存在数组中，所以直接向后移位即可。注意他的移位方法，这是最省时间的移位方法，比我原先的移位方法快的多

然后是更难的line63~line72。这一部分是同时在做减法和累加商。循环的计数器j，还是模拟10的幂次相乘的控制器和对商加和的控制器，ds+j控制除数数组的位数，也就相当于控制了乘10的次数；len-j控制了除数数组的长度，和ds-j结合起来，被sub()调用，就控制了算法中的2。之后，首先定义了tmp中间变量，判断每次运算之后被除数是否还大于等于除数，如果小于，就结束循环。每次计算后，将tmp赋值给len1，实现循环调用，并且将对应的商的位数（由高位加到低位，符合我们设置的规律）+1。这里尤其要注意思考，qu[times-j]++，这一步是如何通过循环来计算商的。

剩下的代码还是老套路，就不解释了。