高精度除法（模拟自然除法，依赖于高精度乘法和减法）

/*
    模拟自然除法（需要大整数乘法和大整数减法，商可精确到小数点后5位，可修改） 
    特殊参数说明:
    result为int型表示商的数组，商的每个数字占一个单元，用-1表示小数点。
    flag余数标志。为1时表示余数不为0，为0表示余数为0
    mid为试探的数字，乘以除数str2可得到curre。 
    curre当前结果。表示试探的mid乘以除数 str2的结果，用于和curstr比较
    curstr当前字符串，余数extra与str1中添加到extra后的数字串，用于计算上商
    lend当前上商的位置
    extra为余数
    c数组为char类型，为试商数组，c[0]为mid，c[1]为'\0'
    succ用于判断是否成功
    count用于表示curstr位数不够在商位置填0的标记
    
    思路：
    S1. 判断除数与被除数的长度,除数长则到S2,否则到S3
    S2.    将被除数的前len1个数字给curstr。 到S4 
    S3.    将被除数的前len2个数字给curstr。 到S4
    S4. 如果curstr小于除数并且被除数还能添加数字到curstr后面，则添加数字，如果添加超过两位或者上一步余数为0，则每一步添加都要在result数组里加入0
        直到curstr不小于除数或者没有位数可以添加，到S5、S6 
    S5. 当前串小于除数且没有数字可以添加，succ==0，就做个标记succ==1；在被除数后加6个0；做响应处理。 到S6
    S6. 和S5就是succ条件不同,再次就没必要添加6个0,直接将result数组转换成字符存到str3中最后一位四舍五入并退出函数，否则转S7
    S7.     二分法试探0-9的数字。以2为底的10的对数为3，再加1是4。最多试探四次就可以找到。其中需要用到高精度乘法和减法。找到的判断条件是当前结果curre必须小于当前串curstr且余数必须小于除数str2。二分直到找到结果。转S8
    S8.    当前上商的位置小于了被除数的长度，转 S4.
*/ 

void Div2(char *str1, char *str2, char *str3)
{
    int i, j, ir, l, h, mid, t;
    int len1 = strlen(str1), len2 = strlen(str2), lend, succ=0, count;
    int result[MAX], flag;    //flag表示余数不为0
    char curre[MAX], extra[MAX], curstr[MAX], c[2];
    ir = i = 0;
    t = len1 >= len2 ? len2: len1;
    strncpy(curstr, str1, t);
    lend = t, curstr[lend] = '\0';
    while(lend <= len1){
        l = 0, h = 9, c[1] = '\0', count = 0;
        while(check(curstr, str2)<0 && str1[lend]!='\0'){
            strncat(curstr, str1+lend, 1);
            count++, lend++;
            if(count > 1 || flag == 0){        //此处的flag为上一步的余数是否为0标记
                result[ir++] = 0;
            }
        }flag = 0;
        if(check(curstr, str2)<0 && str1[lend] == '\0' && 0 == succ){
            succ = 1;
            if(ir == 0){
                result[ir++] = 0;
            }
            result[ir++] = -1;        //表示小数点
            strcat(str1, "000000");    //添加6个0，可精确到后5位
            len1 += 6;
            strncat(curstr, str1+lend, 1);
            lend++;
        }
        if(check(curstr, str2)<0 && str1[lend] == '\0' && succ){    //成功
            for(i=0; i                 if(result[i] != -1){
                    str3[i] = result[i] + '0';
                }else{
                    str3[i] = '.';
                 }
            }
            if(str3[i-1] >= '5'){
                str3[i-2]++;
            }
            str3[i-1] = '\0';
            return ;
        }
        while(l <= h){//二分
            mid = (l+h) / 2,c[0] = mid + '0';
            memset(curre, '0', sizeof(curre));
            Mul(str2, c, curre);            //试探的数字mid乘以除数的结果放入当前结果串
            if((j = check(curre, curstr)) < 0){    //当前结果串小于当前串
                memset(extra, '0', sizeof(extra));
                Minus(curstr, curre, extra);    //当前串-当前结果串 存入 余数extra中
                if(check(extra, str2) < 0){
                    result[ir++] = mid;
                    flag = 1;
                    break;
                }else{
                    l = mid + 1;
                    continue;
                 }
            }else if(j > 0){
                h = mid - 1;
                continue;
             }else{
                result[ir++] = mid;
                break;
              }
        }//while
        if(!flag){    //余数为0
            strcpy(curstr, "");
        }else{
            strcpy(curstr, extra);
         }
    }
}
int check(char *str1, char *str2)
{
    int i = 0, len1, len2;
    len1 = strlen(str1);
    len2 = strlen(str2);
    if(len1 < len2){
        return -1;
    }else if (len1 == len2){
        while((str1[i] == str2[i]) && (i < len1)){
            i++;
        }
        if(i == len1){
            return 0;
        }
        if(str1[i] > str2[i]){
            return 1;
        }else{
            return -1;
         }
     }else{
        return 1;
      }
}

 

2011-05-14 21:23 发表于百度空间，今搬至CU。