操作分析讲解


<1>大数加法

高精度加法呢,简单来说就是:
  • 我们剖析出我们最基础的加法步骤:按位相加

按位求和:
  1. 按位求和最重要的一点就是我们知道每一位是不可能超过10的。
  2. 所以我们每次都将超过了10的部分加到下一位去。
  3. 我们在这里为了方便计算,将每一位数字倒序排列,我们就可以从左向右进行操作了。
  4. 得到了以后呢,我们有一个地方要注意:就是我们的最高位是不是多了一位。所以我们多了一个删除前导0的操作。
  5. 最后倒序返回就好了。

特殊形高精度加法:
  1. 这也不能叫特殊。我们上面的加法只适用于两个非负数相加。那么要是有负数咋办呢?
  2. 首先如果两个都是整数或负数,就不管符号直接相加就好啦,最后把符号给加上去(因为符号不变)。
  3. 那如果一正一负的话,我们就要考虑是否会变号
  4. 所以就要考虑四种情况,每一种情况我们是用较大的数进行高精度减去较小的数得到的,然后判别符号就行了。


代码

string add(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    int mx = len1 > len2 ? len1 : len2;
    for (int i = 0; i < mx; i++) {
        num1[i] += num2[i];
        num1[i + 1] += num1[i] / 10;
        num1[i] %= 10;
    }
    //按位相加
    while (!num1[mx]) mx--;
    //删除前导0(是否有最高位进位)
    string ans;
    for (int i = mx; i >= 0; i--) ans += num1[i] + '0';
    //倒序生成字符串
    return ans;
}


<2>大数减法

我们这里讲的高精度减法并不直接得到两个数直接相减的值
  • 我们将大数减小数的值输出,如果是负数我们就输出0
  • 但是按这个道理,计算出来也没问题,我们先判断两个数的大小就好了。

减法和加法其实非常类似
  1. 我们不过是从向下一个数进位变成了,找下一个数借位
  2. 所以我们先进行减法,如果小于0了,我们就将其变为0~9之间的数,并借位。
  3. 这里要注意!我们由于承载了上一位的借位,所以可能会小于-9,那么我们就要循环将其加回0~9的区间。
  4. 同样这里要注意的是,我们的高位是不是没了。比如4321-4300,最后就是21,高位没了。所以我们也有一个删前导0的操作。
  5. 然后如果现在的最高位被借了,小于0,就特判出去就好了。
  6. 然后就可以倒序返回了。


代码

string sub(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    int mx = len1 > len2 ? len1 : len2;
    for (int i = 0; i < mx; i++) {
        num1[i] -= num2[i];
        while (num1[i] < 0) {
            num1[i] += 10;
            num1[i + 1]--;
        }
    }
    //按位相减
    while (!num1[mx]) mx--;
    //删除前导0
    string ans;
    if (num1[mx] < 0) ans += '0';
    //特判负数
    else
        for (int i = mx; i >= 0; i--) ans += num1[i] + '0';
    //倒序生成字符串
    return ans;
}


<3>大数乘法

乘法也回归到我们的基础计算中:
  • 我们的每一次数位相乘,都是在这两个数位之积的地方产生数(看不懂没关系,下面举个栗子)。

我们先举个栗子吧:
  1. 假如用1234 * 53,我们按照正常操作当然就是先把3对着4,3,2,1一个一个乘,然后5也是一样。
  2. 但是他们和目标的数位有什么关系呢?我们不妨先不干进位的操作,留到最后干。
  3. 我们先来看3和1234,毫无疑问是在个十百千位上的。而5呢,当然是在十百千万位上。
  4. 也就是说,我们目标的数位 = 乘数的数位 + 被乘数的数位(为啥是加呢,因为幂次函数相乘就是指数相加嘛。栗子:5在十位,4在千位,10*1000=1e5,所以在万位)。
  5. 那么我们就清楚了,我们把每一位的数先求出来,最后再来进位就好了。
    for (int i = 0; i < len1; i++)
        for (int j = 0; j < len2; j++)
            digit[i + j] += num1[i] * num2[j];
    
    所以就是这样。
  6. 最后要注意,最大位数可以达到len1+len2,所以要从这一位删前导0。
  7. 倒序返回就好了。


代码

string mul(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    memset(digit, 0, sizeof digit);
    for (int i = 0; i < len1; i++)
        for (int j = 0; j < len2; j++)
            digit[i + j] += num1[i] * num2[j];
    //算出每一个数位上的值
    int mx = len1 + len2;
    for (int i = 0; i < mx; i++)
        if (digit[i] > 9) {
            digit[i + 1] += digit[i] / 10;
            digit[i] %= 10;
        }
    while (mx && !digit[mx]) mx--;
    if (!mx) return "0";
    string ans;
    for (int i = mx; i >= 0; i--)
        ans += digit[i] + '0';
    return ans;
}


<4>大数除法 + 取模

高精度除法和取模是相辅相成的,因为取模的过程中用到了除法,除法当然也要用到模。
首先我们知道法最基本的是什么
  • 就是被除数可以减去除数的次数。

我们这里的高精度除法其实就是模拟了这个过程:减法,所以我们可以看到我们上面已经讲过的减法内容。
  • 但是单纯的一个一个减过去也太浪费时间了,所以我们用了一种方法使其变得非常的简单快捷。

减法模拟:
  1. 我们直接举个栗子会更好理解:
  2. 假如我们是求7546 / 23。如果一个一个删过去,我们要删几百次。但是如果按照我们平常的思想,从最高位算过去该怎么模拟呢?
  3. 其实我们就可以先将23增大100倍,让23的数位变得和7456一样大。然后做减法,得到的商为3。所以我们就知道他可以对23除300次,余数是646。
  4. 然后将23以十倍的顺序逐渐缩小,每次对其求商取余
  5. 然后我们用上一次的余数646除230,又可以得到商为2,余数为186。我们知道他可以对23除20次,现在总计320次。
  6. 然后186对23求商为8,取余为2,可以对23除8次,总计328次。余数也自然而然的出来了就是2。
  7. 详细实现过程看代码~


代码

string div(string s1, string s2, char ch) {
    int len1 = s1.length(), len2 = s2.length();
    int mx = len1;
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    if (len1 < len2 || (len1 == len2 && s1 < s2))
        if ('/' == ch) return "0";
        else return s1;
    //判断s1数比s2小的情况
    int t = len1 - len2;
    for (int i = len1 - 1; i >= 0; i--)
        if (i >= t) num2[i] = num2[i - t];
        else num2[i] = 0;
    len2 = len1;
    //将num2增大数位差倍
    memset(digit, 0, sizeof digit);
    for (int i = 0; i <= t; i++) {
        int tmp = calc(num1, num2 + i, len1, len2 - i);
        while (tmp >= 0) {
            len1 = tmp;
            digit[t - i]++;
            tmp = calc(num1, num2 + i, len1, len2 - i);
        }
    }
    //求出每一位的数据
    int L = mx;
    for (int i = 0; i < L; i++) {
        digit[i + 1] += digit[i] / 10;
        digit[i] %= 10;
    }
    //处理进位
    string ans1, ans2;
    L = mx;
    while (L >= 0 && !digit[L]) L--;
    while (L >= 0) ans1 += digit[L--] + '0';
    //求商
    L = mx;
    while (L >= 0 && !num1[L]) L--;
    while (L >= 0) ans2 += num1[L--] + '0';
    if (ans2.empty()) ans2 = "0";
    //求余数
    if ('/' == ch) return ans1;
    else return ans2;
}
int calc(int* num1, int* num2, int len1, int len2) {
    if (len1 < len2) return -1;
    if (len1 == len2)
        for (int i = len1 - 1; i >= 0; i--)
            if (num1[i] > num2[i]) break;
            else if (num1[i] < num2[i]) return -1;
    for (int i = 0; i < len1; i++) {
        num1[i] -= num2[i];
        if (num1[i] < 0) {
            num1[i] += 10;
            num1[i + 1]--;
        }
    }
    //高精度减法
    for (int i = len1 - 1; i >= 0; i--)
        if (num1[i]) return i + 1;
    return 0;
    //num1大于num2时,返回相差的位数
}

高精度计算综合测试代码

#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e6 + 7;
string s1, s2;//输入字符串
int num1[MAX], num2[MAX], digit[MAX];//转换数组,进位数组
//全局变量区

string add(string s1, string s2);//加法
string sub(string s1, string s2);//减法
string mul(string s1, string s2);//乘法
string div(string s1, string s2, char ch);//除法or取模
int calc(int* num1, int* num2, int len1, int len2);//用于div:计算s1可以对s2满减的次数
//函数预定义区

int main() {
    IOS;
    cout << "请输入两个数:" << endl;
    while (cin >> s1 >> s2) {
        cout << "以下为该大数的基础运算:" << endl;
        cout << s1 << " + " << s2 << " = " << add(s1, s2) << endl;
        cout << s1 << " - " << s2 << " = " << sub(s1, s2) << endl;
        cout << s1 << " * " << s2 << " = " << mul(s1, s2) << endl;
        cout << s1 << " / " << s2 << " = " << div(s1, s2, '/') << endl;
        cout << s1 << " % " << s2 << " = " << div(s1, s2, '%') << endl;
        cout << endl << "----------分割线----------" << endl;
        cout << endl << "请输入两个数:" << endl;
    }
    return 0;
}
string add(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    int mx = len1 > len2 ? len1 : len2;
    for (int i = 0; i < mx; i++) {
        num1[i] += num2[i];
        num1[i + 1] += num1[i] / 10;
        num1[i] %= 10;
    }
    //按位相加
    while (mx >= 0 && !num1[mx]) mx--;
    //删除前导0(是否有最高位进位)
    if (mx < 0) return "0";
    string ans;
    for (int i = mx; i >= 0; i--) ans += num1[i] + '0';
    //倒序生成字符串
    return ans;
}
string sub(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    int mx = len1 > len2 ? len1 : len2;
    for (int i = 0; i < mx; i++) {
        num1[i] -= num2[i];
        while (num1[i] < 0) {
            num1[i] += 10;
            num1[i + 1]--;
        }
    }
    //按位相减
    while (mx >= 0 && !num1[mx]) mx--;
    //删除前导0
    string ans;
    if (mx < 0 || num1[mx] < 0) ans += '0';
    //特判负数
    else
        for (int i = mx; i >= 0; i--) ans += num1[i] + '0';
    //倒序生成字符串
    return ans;
}
string mul(string s1, string s2) {
    int len1 = s1.length(), len2 = s2.length();
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    memset(digit, 0, sizeof digit);
    for (int i = 0; i < len1; i++)
        for (int j = 0; j < len2; j++)
            digit[i + j] += num1[i] * num2[j];
    //算出每一个数位上的值
    int mx = len1 + len2;
    for (int i = 0; i < mx; i++)
        if (digit[i] > 9) {
            digit[i + 1] += digit[i] / 10;
            digit[i] %= 10;
        }
    while (mx && !digit[mx]) mx--;
    if (!mx) return "0";
    string ans;
    for (int i = mx; i >= 0; i--)
        ans += digit[i] + '0';
    return ans;
}
string div(string s1, string s2, char ch) {
    int len1 = s1.length(), len2 = s2.length();
    int mx = len1;
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    for (int i = 0; i < len1; i++)
        num1[i] = s1[len1 - i - 1] - '0';
    for (int i = 0; i < len2; i++)
        num2[i] = s2[len2 - i - 1] - '0';
    //翻转字符串为数组方便运算
    if (len1 < len2 || (len1 == len2 && s1 < s2))
        if ('/' == ch) return "0";
        else return s1;
    //判断s1数比s2小的情况
    int t = len1 - len2;
    for (int i = len1 - 1; i >= 0; i--)
        if (i >= t) num2[i] = num2[i - t];
        else num2[i] = 0;
    len2 = len1;
    //将num2增大数位差倍
    memset(digit, 0, sizeof digit);
    for (int i = 0; i <= t; i++) {
        int tmp = calc(num1, num2 + i, len1, len2 - i);
        while (tmp >= 0) {
            len1 = tmp;
            digit[t - i]++;
            tmp = calc(num1, num2 + i, len1, len2 - i);
        }
    }
    //求出每一位的数据
    int L = mx;
    for (int i = 0; i < L; i++) {
        digit[i + 1] += digit[i] / 10;
        digit[i] %= 10;
    }
    //处理进位
    string ans1, ans2;
    L = mx;
    while (L >= 0 && !digit[L]) L--;
    while (L >= 0) ans1 += digit[L--] + '0';
    //求商
    L = mx;
    while (L >= 0 && !num1[L]) L--;
    while (L >= 0) ans2 += num1[L--] + '0';
    if (ans2.empty()) ans2 = "0";
    //求余数
    if ('/' == ch) return ans1;
    else return ans2;
}
int calc(int* num1, int* num2, int len1, int len2) {
    if (len1 < len2) return -1;
    if (len1 == len2)
        for (int i = len1 - 1; i >= 0; i--)
            if (num1[i] > num2[i]) break;
            else if (num1[i] < num2[i]) return -1;
    for (int i = 0; i < len1; i++) {
        num1[i] -= num2[i];
        if (num1[i] < 0) {
            num1[i] += 10;
            num1[i + 1]--;
        }
    }
    //高精度减法
    for (int i = len1 - 1; i >= 0; i--)
        if (num1[i]) return i + 1;
    return 0;
    //num1大于num2时,返回相差的位数
}
//函数区

后话


<5>大数阶层

  • 大数的阶层,我们必然也是要用一个数组来保存答案数据的每一位的。

阶层的原理是啥呢?
  1. 我们的阶层就是从1一步一步的乘到n。
  2. 那我们上面将高精度乘法的时候是怎么讲的呢?就是将数放到两个数位之和的位置上面去。
  3. 同样的思路,我们可以换一个看法:就是用乘数的每一位去乘上被乘数,然后逐步进位到下一位。同时我们用一个变量digit标记最后一位的位置(用于识别答案当前长度)。

怎么操作呢?
  1. 先看个栗子:假如是50的阶层,我们最开始肯定是1,digit也是1。然后按位乘:1 * 2,答案是2,digit还是1。同理得到3时是6和digit=1。
    那接下来变成4就不一样了:我们用6 * 4 = 24,现在a[0]=24。我们知道每一位不能超过9。所以把超过个位的放到a[1]里面去(放24 / 10,存24 % 10),再标记digit = 2了。
    到了5之后呢,我们现在digit>1,按每一位来计算,先用个位:4 * 5 = 20,同理将0留下,2进位。然后十位:2 * 5 + 进位 = 12,所以留下2,进位1。这个1超过原来的长度了,digit就再加。
  2. 按上面这个道理,简单用语言描述是怎么弄呢?就是先按位进行计算,并进位,直到算到被乘数(当前答案数组)的最高位。然后将越界的进位放到后面的位置,并改变digit的位置。

打代码嘞:
  1. 先输入我们的阶层数,这个数很大,但我们定在1w以内,这样只要2s左右可以算出来,再大就难算了。
  2. 先定义1的情况,就是a[0] = 1,digit = 1。
  3. 然后从2循环乘到n。
  4. 循环内先将被乘数(当前答案数组)进行逐位乘法并进位。然后将超出最高位的进位放进数组,并标记digit。
  5. 最后倒序输出(要拿出来用也可以合并成String)。
  6. 看我代码~


代码

#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false);
//代码预处理区

const int MAX = 1e5 + 7;
int a[MAX];
//全局变量区

int main() {
    int n; cin >> n;
    a[0] = 1;
    int digit = 1;//表示最高数位位置
    for (int i = 2; i <= n; i++) {
        int plus = 0;//保存向下一位的进位
        for (int j = 0; j < digit; j++) {
            int temp = a[j] * i + plus;
            a[j] = temp % 10;
            plus = temp / 10;
        }
        //上一位的长度范围内进行乘法进位操作
        while (plus) {
            a[digit] = plus % 10;
            plus /= 10;
            digit++;
        }
        //超出上一位的长度范围的进位操作(同时标记这一位长度)
    }
    for (int k = digit - 1; k >= 0; k--)
        cout << a[k];
    cout << endl;
    //倒序输出
    return 0;
}
//函数区