大数除法-白红宇

大数除法

阅读量：5308 次

发布时间：2019-06-14

本文共 4757 字，大约阅读时间需要 15 分钟。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define MaxSize 10000bool _DividendIsLarger(int *Dividend,int *Divisor,int DividendLen,int DivisorLen){    int DivisorLenEnd;    if(DividendLen < DivisorLen)    {        return false;    }    else if(DividendLen == DivisorLen)    {        for(DivisorLenEnd = DividendLen - 1;DivisorLenEnd >= 0;DivisorLenEnd --)        {            if(Dividend[DivisorLenEnd] < Divisor[DivisorLenEnd])            {                return false;            }        }    }    return true;}//sub's result store in Dividend[],return the length of Dividend[]int _TwoBigNumSub(int *Dividend,int *Divisor,int DividendLen,int DivisorLen){    //judge if Dividend > Divisor,else return -1    bool Judger = _DividendIsLarger(Dividend,Divisor,DividendLen,DivisorLen);    if(! Judger)    {        return -1;    }        //do the Sub    int DivisorEnd;    for(DivisorEnd = 0;DivisorEnd < DividendLen;DivisorEnd ++)    {        Dividend[DivisorEnd] -= Divisor[DivisorEnd];        if(Dividend[DivisorEnd] < 0)        {            Dividend[DivisorEnd] += 10;            Dividend[DivisorEnd+1] --;        }    }        for(DivisorEnd = DividendLen-1;DivisorEnd >= 0;DivisorEnd --)    {        if(Dividend[DivisorEnd])        {            return (DivisorEnd + 1);        }    }    return 0;}char *TwoBigNumDivision(char *InputDividend,char *InputDivisor){    int *TempResult = malloc(MaxSize*sizeof(int));    memset(TempResult,0,MaxSize*sizeof(int));    char *Result = malloc(MaxSize*sizeof(char));    memset(Result,0,MaxSize*sizeof(char));    int ResultEnd = 0;        int DividendLen = strlen(InputDividend);    int DivisorLen = strlen(InputDivisor);        int Dividend[MaxSize];    int Divisor[MaxSize];    memset(Dividend,0,sizeof(Dividend));    memset(Divisor,0,sizeof(Divisor));        //reverse to store    int InputDivisorEnd,DivisorEnd;    for(InputDivisorEnd = DividendLen-1,DivisorEnd = 0;InputDivisorEnd >= 0;InputDivisorEnd --)    {        Dividend[DivisorEnd ++] = InputDividend[InputDivisorEnd] - '0';    }    for(InputDivisorEnd = DivisorLen-1,DivisorEnd = 0;InputDivisorEnd >= 0;InputDivisorEnd --)    {        Divisor[DivisorEnd ++] = InputDivisor[InputDivisorEnd] - '0';    }        //special discuss for zero && one time sub    if(! _DividendIsLarger(Dividend,Divisor,DividendLen,DivisorLen))    {        Result[ResultEnd++] = '0';        Result[ResultEnd++] = '\0';        return Result;    }        DividendLen = _TwoBigNumSub(Dividend,Divisor,DividendLen,DivisorLen);    if(DividendLen == -1)    {        Result[ResultEnd++] = '0';        Result[ResultEnd++] = '\0';        return Result;    }    else if(DividendLen == 0)    {        Result[ResultEnd++] = '1';        Result[ResultEnd++] = '\0';        return Result;    }    TempResult[0] ++;        int ZeroCompletion = DividendLen - DivisorLen;        if(ZeroCompletion < 0)    {        Result[ResultEnd++] = '1';        Result[ResultEnd++] = '\0';        return Result;    }    else if(ZeroCompletion > 0)    {        for(DivisorEnd = DividendLen - 1;DivisorEnd >= 0;DivisorEnd --)        {            if(DivisorEnd >= ZeroCompletion)            {                Divisor[DivisorEnd] = Divisor[DivisorEnd - ZeroCompletion];            }            else            {                Divisor[DivisorEnd] = 0;            }        }    }        int Temp;    DivisorLen = DividendLen;    for(DivisorEnd = 0;DivisorEnd <= ZeroCompletion;DivisorEnd ++)    {        while( (Temp = _TwoBigNumSub(Dividend,Divisor+DivisorEnd,DividendLen,DivisorLen-DivisorEnd)) >= 0)        {            DividendLen = Temp;            TempResult[ZeroCompletion-DivisorEnd] ++;        }    }        //output    for(DivisorEnd = 0;DivisorEnd < MaxSize;DivisorEnd ++)    {        if(TempResult[DivisorEnd] >= 10)        {            TempResult[DivisorEnd+1] +=  TempResult[DivisorEnd]/10;            TempResult[DivisorEnd] %= 10;        }    }    for(DivisorEnd = MaxSize-1;DivisorEnd >= 0;DivisorEnd --)    {        if(TempResult[DivisorEnd] != 0)        {            break;        }        else if(DivisorEnd == 0 && TempResult[DivisorEnd] == 0)        {            Result[ResultEnd++] = '0';            Result[ResultEnd++] = '\0';            return Result;        }    }        for(;DivisorEnd >= 0;DivisorEnd --)    {        Result[ResultEnd++] = TempResult[DivisorEnd] + '0';    }    Result[ResultEnd]= '\0';    return Result;}int main(){    char InputDividend[MaxSize] = "5409656775097850895687056798068970934546546575676768678435435345";    char InputDivisor[MaxSize] = "1";    char *Result = TwoBigNumDivision(InputDividend,InputDivisor);    puts(Result);    return 0;}