Chinaunix首页 | 论坛 | 博客
  • 博客访问: 475262
  • 博文数量: 59
  • 博客积分: 345
  • 博客等级: 二等列兵
  • 技术积分: 1380
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-18 22:44
个人简介

to be myself

文章分类

全部博文(59)

文章存档

2017年(5)

2013年(47)

2012年(3)

2011年(4)

分类: C/C++

2013-03-03 11:49:43

/*
    模拟自然除法(需要大整数乘法和大整数减法,商可精确到小数点后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。

 

阅读(3194) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~