操作分析讲解
<1>大数加法
高精度加法呢,简单来说就是:
- 我们剖析出我们最基础的加法步骤:按位相加。
按位求和:
- 按位求和最重要的一点就是我们知道每一位是不可能超过10的。
- 所以我们每次都将超过了10的部分加到下一位去。
- 我们在这里为了方便计算,将每一位数字倒序排列,我们就可以从左向右进行操作了。
- 得到了以后呢,我们有一个地方要注意:就是我们的最高位是不是多了一位。所以我们多了一个删除前导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 (!num1[mx]) mx--; //删除前导0(是否有最高位进位) string ans; for (int i = mx; i >= 0; i--) ans += num1[i] + '0'; //倒序生成字符串 return ans; }
<2>大数减法
我们这里讲的高精度减法并不直接得到两个数直接相减的值:
- 我们将大数减小数的值输出,如果是负数我们就输出0。
- 但是按这个道理,计算出来也没问题,我们先判断两个数的大小就好了。
减法和加法其实非常类似:
- 我们不过是从向下一个数进位变成了,找下一个数借位。
- 所以我们先进行减法,如果小于0了,我们就将其变为0~9之间的数,并借位。
- 这里要注意!我们由于承载了上一位的借位,所以可能会小于-9,那么我们就要循环将其加回0~9的区间。
- 同样这里要注意的是,我们的高位是不是没了。比如4321-4300,最后就是21,高位没了。所以我们也有一个删前导0的操作。
- 然后如果现在的最高位被借了,小于0,就特判出去就好了。
- 然后就可以倒序返回了。
代码
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>大数乘法
乘法也回归到我们的基础计算中:
- 我们的每一次数位相乘,都是在这两个数位之积的地方产生数(看不懂没关系,下面举个栗子)。
我们先举个栗子吧:
- 假如用1234 * 53,我们按照正常操作当然就是先把3对着4,3,2,1一个一个乘,然后5也是一样。
- 但是他们和目标的数位有什么关系呢?我们不妨先不干进位的操作,留到最后干。
- 我们先来看3和1234,毫无疑问是在个十百千位上的。而5呢,当然是在十百千万位上。
- 也就是说,我们目标的数位 = 乘数的数位 + 被乘数的数位(为啥是加呢,因为幂次函数相乘就是指数相加嘛。栗子:5在十位,4在千位,10*1000=1e5,所以在万位)。
- 那么我们就清楚了,我们把每一位的数先求出来,最后再来进位就好了。
for (int i = 0; i < len1; i++) for (int j = 0; j < len2; j++) digit[i + j] += num1[i] * num2[j];
所以就是这样。 - 最后要注意,最大位数可以达到len1+len2,所以要从这一位删前导0。
- 倒序返回就好了。
代码
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>大数除法 + 取模
高精度除法和取模是相辅相成的,因为取模的过程中用到了除法,除法当然也要用到模。
首先我们知道除法最基本的是什么:
- 就是被除数可以减去除数的次数。
我们这里的高精度除法其实就是模拟了这个过程:减法,所以我们可以看到我们上面已经讲过的减法内容。
- 但是单纯的一个一个减过去也太浪费时间了,所以我们用了一种方法使其变得非常的简单快捷。
减法模拟:
- 我们直接举个栗子会更好理解:
- 假如我们是求7546 / 23。如果一个一个删过去,我们要删几百次。但是如果按照我们平常的思想,从最高位算过去该怎么模拟呢?
- 其实我们就可以先将23增大100倍,让23的数位变得和7456一样大。然后做减法,得到的商为3。所以我们就知道他可以对23除300次,余数是646。
- 然后将23以十倍的顺序逐渐缩小,每次对其求商取余。
- 然后我们用上一次的余数646除230,又可以得到商为2,余数为186。我们知道他可以对23除20次,现在总计320次。
- 然后186对23求商为8,取余为2,可以对23除8次,总计328次。余数也自然而然的出来了就是2。
- 详细实现过程看代码~
代码
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一步一步的乘到n。
- 那我们上面将高精度乘法的时候是怎么讲的呢?就是将数放到两个数位之和的位置上面去。
- 同样的思路,我们可以换一个看法:就是用乘数的每一位去乘上被乘数,然后逐步进位到下一位。同时我们用一个变量digit标记最后一位的位置(用于识别答案当前长度)。
那怎么操作呢?
- 先看个栗子:假如是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就再加。 - 按上面这个道理,简单用语言描述是怎么弄呢?就是先按位进行计算,并进位,直到算到被乘数(当前答案数组)的最高位。然后将越界的进位放到后面的位置,并改变digit的位置。
打代码嘞:
- 先输入我们的阶层数,这个数很大,但我们定在1w以内,这样只要2s左右可以算出来,再大就难算了。
- 先定义1的情况,就是a[0] = 1,digit = 1。
- 然后从2循环乘到n。
- 循环内先将被乘数(当前答案数组)进行逐位乘法并进位。然后将超出最高位的进位放进数组,并标记digit。
- 最后倒序输出(要拿出来用也可以合并成String)。
- 看我代码~
代码
#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; } //函数区