大整数的除法_浮点数除法和整数除法

大整数的除法_浮点数除法和整数除法高精度正整数除法大整数除法标签(空格分隔):算法竞赛算法编程错题高精度单词:divident:被除数divisor:除数quotient:商大整数除法OpenJ_Bailian-2737题目要求:

大整数的除法_浮点数除法和整数除法"

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

标签(空格分隔): 算法竞赛 算法 编程错题 高精度


单词:
    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 <stdio.h>
#include <string.h>
#define N 101
int 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<len2)  return -1;
    else if (len1==len2)
        for (i=len1-1;i>=0;i--)
        {
            if (dd[i]<ds[i])
                    return -1;
            else if (dd[i]>ds[i])
                break;
        }
    for (i=0;i<len1;i++)
    {
        dd[i]-=ds[i];
        if (dd[i]<0)
        {
            dd[i]+=10;
            dd[i+1]--;
        }
    }
    for (i=len1-1;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<N;i++)
    {
        if (qu[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]++,这一步是如何通过循环来计算商的。
剩下的代码还是老套路,就不解释了。

今天的文章大整数的除法_浮点数除法和整数除法分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/89533.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注