一起学习交流~

大整数计算-05-除法(重点)

算法 laomuji 11个月前 (11-06) 1144次浏览 已收录 1个评论

一、原理

除法没办法直接实现,需要把除法转变为减法,

比如:

123/21 转化为

123-21 = 102

102-21 = 81

81 – 21 = 60

60 – 21 = 39

39 – 21 = 18

18< 21 所以18为余数

21出现了5次,余数为18,所以123/21=5余18

这样就可以写出简单的除法了,请先去写代码实践,做完后再接着往下看

其中用到的加减乘法 可以用之前写的,等优化的时候再替换

二、优化1

当极端情况,比如一个很大的数字减一个很小的数字,需要的次数会很多

比如:999999…一百万个9,除5,需要减非常非常多次,并且需要把除的次数加起来,非常的浪费时间

就需要对这个减法运算进行优化了

把除数的长度和被除数对齐,再进行减法,可以有效提高运算的次数,看懂原理后请再写代码实践

123456 / 666
将除数对齐至被除数:666*1000
123456<666000,不成立,除数/10,666*100
123456-66600=56856,记录:100
56856<66600,不成立,除数/10,666*10
56856-6660=50196,记录:10
50196-6660=43536,记录:10
43536-6660=36876,记录:10
36876-6660=30216,记录:10
30216-6660=23556,记录:10
23556-6660=16896,记录:10
16896-6660=10236,记录:10
10236-6660=3576,记录:10
3576<6660,不成立,除数/10,666*1
3576-666=2910,记录:1
2910-666=2244,记录:1
2244-666=1578,记录:1
1578-666=912,记录:1
912-666=246,记录:1
246<666,余数为246
将记录的数字加起来
100+
10+10+10+10+10+10+10+10+
1+1+1+1+1
=185
验算,185*666+246=123456

三、优化2

发现再数字很大时还是很慢,再进一步的优化

比如这个1000,100,10,1之类的,都是10的n次方,所以可以利用这个特点,对乘法进行优化

比如左边第一个是1,后面直接增加n个0即可

   static string multiplyTenPower(string str, int power)
    {
        for (int i = 0; i < power; i++)str.push_back(0);
        return str;
    }

乘法优化后,再对对应的除法,如1000变成100,100变成10,10变成1,

只需要把后面的0去掉一个即可

请先实践后,再接着往下看吧

四、优化3

发现数字很大时还是很慢,再进一步的优化

比如:123456-66600,发现后面的00可以无视掉,因为减0还是0

   static void subTenPower(string& data1, string& data2, int n)
    {

        int size1 = data1.size() - 1 - n;
        int size2 = data2.size() - 1 - n;

        //循环设置结果
        for (; size2 >= 0; size2--, size1--)
        {
            char tempNum = data1[size1] - data2[size2];
            if (tempNum < 0)
            {
                data1[size1 - 1] -= 1;
                tempNum += 10;
            }
            data1[size1] = tempNum;
        }

        //去掉前面无用的0
        size_t zero = 0;
        for (size_t i = 0; i < data1.size(); i++)
        {
            if (data1[i] != 0)break;
            zero++;
        }
        data1 = data1.substr(zero);
    }

记录的值加法,也可以进行优化

只需要找到需要+1的位置,比如1200+100,只需要在1200的左边第二位2的位置加上1,就可以变成1300

   static string addTenPower(string data1, string& data2)
    {
        //如果data1的位数比data2小,显然data1为空
        if (data1.size() < data2.size())return data2;
        //不用担心越界,因为被除数 / 除数 结果不可能大于被除数
        int pos = data1.size() - data2.size();
        data1[pos] += 1;
        if (data1[pos] > 9)
        {
            data1[pos - 1] += 1;
            data1[pos] -= 10;
        }
        if (data1[0] == 0)return data1.substr(1);
        return data1;
    }

五、代码

   //返回data1/data2的结果和data1%data2的结果
    static pair<string, string>divide(string& data1, string& data2)
    {
        auto result = m_divide(strToNum(data1), strToNum(data2));
        return pair<string, string>(numToStr(result.first), numToStr(result.second));
    }
    static pair<string, string>m_divide(string str1, string str2)
    {
        //如果有一个数为0,返回0
        if (str1[0] == 0)return pair<string, string>(str1, str1);
        if (str2[0] == 0)return pair<string, string>(str2, str2);

        //除法的思想就是把除法转变减法
        int equal = maxNum(str1, str2);
        //相等,如:5/5=1余0,直接返回1,0
        if (equal == 0)return pair<string, string>(strToNum("1"), strToNum("0"));
        //1小于2,如:4/5=0余4,直接返回0,4
        if (equal == -1)return pair<string, string>(strToNum("0"), str1);
        string result;//结果
        result.push_back(0);
        size_t len = (str1).size() - (str2).size();
        //用于加法
        string str3;
        str3.push_back(1);
        for (size_t i = 0; i < len; i++)str3.push_back(0);
        //把str2提升到str1一样的位数
        string temp = multiplyTenPower((str2), len);
        while (1)
        {
            //当位数过大,需要/10
            if (str3.size() > len + 1)
            {
                //str3和temp都是扩大的,后面补的是0,把0直接去掉就行
                str3.pop_back();
                temp.pop_back();
            }
            int max = maxNum(str1, temp);
            if (max == 1)
            {
                //result = add(result, str3); 
                result = addTenPower(result, str3);
                //如果str1大,表示需要更新数字
                //str1 = subtract(str1, temp, 1).first;;
                subTenPower(str1, temp, len);
            }
            else if (max == -1)
            {
                //如果str2大,表示位数过大
                //若len=0表示两个数字剩下的长度已经相等了
                if (len == 0)break;
                //减少位数
                len -= 1;
            }
            else
            {
                //如果剩下的两个数相等,表示没有余数,可以除尽
                result = addTenPower(result, str3);
                str1 = "0";
                (str1)[0] = 0;
                break;
            }
        }
        return pair<string, string>(result, str1);
    }

    static string strToNum(string str)
    {
        for (size_t i = 0; i < str.length(); i++)
        {
            if (str[i] >= '0' && str[i] <= '9')str[i] -= 48;
        }
        return str;
    }

    static string numToStr(string str)
    {
        for (size_t i = 0; i < str.length(); i++)
        {
            if (str[i] >= 0 && str[i] <= 9)str[i] += 48;
        }
        return str;
    }

    static string multiplyTenPower(string str, int power)
    {
        for (int i = 0; i < power; i++)str.push_back(0);
        return str;
    }

    static string addTenPower(string data1, string& data2)
    {
        //如果data1的位数比data2小,显然data1为空
        if (data1.size() < data2.size())return data2;
        //不用担心越界,因为被除数 / 除数 结果不可能大于被除数
        int pos = data1.size() - data2.size();
        data1[pos] += 1;
        if (data1[pos] > 9)
        {
            data1[pos - 1] += 1;
            data1[pos] -= 10;
        }
        if (data1[0] == 0)return data1.substr(1);
        return data1;
    }

    static void subTenPower(string& data1, string& data2, int n)
    {

        int size1 = data1.size() - 1 - n;
        int size2 = data2.size() - 1 - n;

        //循环设置结果
        for (; size2 >= 0; size2--, size1--)
        {
            char tempNum = data1[size1] - data2[size2];
            if (tempNum < 0)
            {
                data1[size1 - 1] -= 1;
                tempNum += 10;
            }
            data1[size1] = tempNum;
        }

        //去掉前面无用的0
        size_t zero = 0;
        for (size_t i = 0; i < data1.size(); i++)
        {
            if (data1[i] != 0)break;
            zero++;
        }
        data1 = data1.substr(zero);
    }

六、想说的话

此时用来计算大数字除法已经非常快了,当然 还有更好的写法,如果有什么想法,可以评论或者联系我

喜欢 (8)
订阅评论
提醒
guest
1 评论
最旧
最新 最多投票
内联反馈
查看所有评论
疾风剑豪
疾风剑豪
8 月 前

讲的很详细,一步步的优化,看懂了