【算法学习笔记】34.高精度除法 SJTU OJ 1026/1016

高精度除法，这个和加减乘一样，我们都要从手算的角度入手。举一个例子，比如 524134 除以 123。结果是4261

第一位4的来源是我们把 524和123对齐，然后进行循环减法，循环了4次，余32，将32134的前三位321继续和123对齐，循环减法2次，余75，把7534的前三位753和123对齐，循环减法6次，余15，将154和123对齐，只能减1次，所以结果是4 2 6 1。

把上述过程程序化

1.把A,B两个数存入char数组 0下标表示的是最高位
2.把A的前lenB位和B对齐进行大小比较
　　3.如果2的比较结果里A的前lenB位大,那么就进行循环减法,直到它比B小,循环的次数记作s[0]表示最终结果的最高位
　　4.如果2的比较结果里A的前lenB位小,什么也不做.
5.把B整体向后以一位,和A的最高位对齐(最高位可能暂时是0) 把s的下标迭代+1 表示进行下一位的计算
6.不断地比较,直到当B的尾部和A的尾部对齐时,说明A的最后lenB位也进行了循环减法算数,所以得到了结果.终止程序
//以上提到的lenB都是最开始的B的长度,后来由于移位会导致增大

过程如下

A:524134/

B:123/

循环4次减法

A:032134/

B:0123/ -----循环错位前方补0

循环2次减法

A:007534/

B:00123/

循环6次减法

A:000154/

B:000123/

循环1次减法

源代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX 10001
using namespace std;
 
char A[MAX]={'0'},B[MAX]={'0'};
int lenA=0,lenB=0;
int res[MAX]={0};
bool isGreater(){
    return strncmp(A,B,lenB)>=0;//注意 lenB会因为移位而增大,所以不必担心
}
//把A当前的最高位和B的最高位对齐后相减
void sub(){
    //首先要找到A的最高位 和B进行对齐,由于在while循环里已经进行了大小的判断,此时最高位指的就是真正的最高位
    int i, begin = 0;
    for (i = 0; A[i]=='0'; ++i)
        begin = i;
    //此时begin和i都是最高位的下标 已经是和B对齐的了
    for (; i < lenB; ++i)
        A[i] = A[i] - B[i] +'0'; //注意 如果用 -= 的话 应该是 A[i] -= B[i] - '0'
    //开始借位 把负数补全 从右向左借
    for (int i = lenB-1; i >0; --i) if(A[i]<'0')
    {
        A[i]+=10;
        A[i-1]--;
    }
}
 
int main(int argc, char const *argv[])
{
    cin>>A>>B;
    lenA = strlen(A);    
    lenB = strlen(B);
    //若A小于B 直接输出0结束.
    if(lenA<lenB or (lenA==lenB and !isGreater())){
        cout<<0<<endl;return 0;
    }
    int res_i = 0; //标记res数组正在处理的下标 0是最高位
    while(1){ //当最后对齐时break
        //开始对A和B的前lenB位进行循环减法
        
        while(isGreater()){
            sub();
            ++res[res_i];
        }
        ++res_i;
        //若上一次的余数小于B的位数,则cot为0没有问题
        if(lenA==lenB)    //必须在减法循环结束之后立刻检验 因为移位之后lenB发生了变化 而且也没有必要
            break;
        //对B进行向右移动 注意lenB要增加1
        int j;
        for ( j = lenB++; j > 0 ; --j)
            B[j]=B[j-1];
        B[j]='0';
    }
    bool flag = true;//表示以后有0不输出
    for (int i = 0; i < res_i; ++i)
    {
        if(flag and res[i]!=0)
            flag = false;//已经遇到了 第一个不是0的数 表示以后有0输出
        if(res[i]==0){
            if(!flag)
                cout<<0;
        }else
            cout<<res[i];
 
    }
    cout<<endl;
    return 0;
}

View Code