戳一戳！和我一起走进信息学的世界
导读
信息学能够有助于孩子未来工作发展，提升孩子的综合能力。
这一节课是我们这一期课程的最后一节课，我们继续学习高精度算法，回顾如何高精度算法的定义，输出及加减法运算，并学习如何实现高精度的乘除法。
1 回顾
大家还记得我们前面使用结构体实现了高精度加法和高精度减法，我们先来回顾一下吧！
高精度算法就是当我们不能再用普通的数据类型来存放整数时，我们就要考虑用其他方式存放，并实现数据的运算。
当然，我们也可以把整数推广到小数，要注意的就是我们要用一位来存放小数点。高精度算法的实现方式不唯一。例如我们实现高精度，就是用结构体，然后数据是个位对齐：
我们就可以按照如下方式定义高精度结构体：
#include<iostream>
using namespace std;
#define MAX 100
struct HP {
int data[MAX] = {};
int len;
};
HP str2Arr(string s){
HP h;
int i = 0;
while(s[i] == '0' && i<s.size()-1) i++;
s = s.substr(i);
h.len = s.size();
for(int i = 0;i<h.len;i++) h.data[MAX-i-1] = s[h.len-i-1] - '0';
return h;
}
void print(HP h){
for(int i = MAX-h.len;i<MAX;i++) cout<<h.data[i];
cout<<endl;
}
int main(){
string s1 = "00045926",s2 = "123456";
HP h1 = str2Arr(s1),h2 = str2Arr(s2);
print(h1);
print(h2);
return 0;
}
有了高精度结构体，我们就可以实现高精度的加法和高精度的减法了。
//高精度加法
HP add(HP h1, HP h2){
HP h;
int jw = 0,t, max;
if(h1.len>h2.len) max = h1.len;
else max = h2.len;
for(int i = MAX-1;i>=MAX-1-max;i--){
t = h1.data[i]+h2.data[i]+jw;
h.data[i] = t%10;
jw = t/10;
}
if(h.data[MAX-1-max]) h.len = max+1;
else h.len = max;
return h;
}
//高精度减法
HP sub(HP h1, HP h2){
HP h;
int jw = 0,t, max;
max = h1.len;
for(int i = MAX-1;i>=MAX-max;i--){
t = h1.data[i]-h2.data[i]-jw;
if(t<0){
h.data[i] = t+10;
jw = 1;
}
else{
h.data[i] = t;
jw = 0;
}
}
if(h.data[MAX-max]) h.len = max;
else h.len = max-1;
return h;
}
对于加减法，我们都考虑了最简单的情况，上节课的题目中，我们提到，如果我们不确定被减数和减数谁更大的时候，就要分情况讨论了：
如果被减数≥减数，最高位存0，输出原数
如果被减数＜减数，最高位存1，在前面输出﹣号，然后再输出减数-被减数。
所以我们首先要写一个函数判断两个数谁更大：
如果位数不同，位数多的大；
如果位数相同，从第一位往后比,某一位大的，这个数更大。
下面的函数，如果被减数大，返回true，否则返回false：
bool Max(HP h1, HP h2){
int l1 = h1.len,l2 = h2.len;
if(l1>l2) return true;
if(l1==l2){
while(l1>0&&l2>0&&h1.data[MAX-l1] == h2.data[MAX-l2]){
l1--;
l2--;
}
return h1.data[MAX-l1] >= h2.data[MAX-l2];
}
return false;
}然后我们就可以重写减法了，如果被减数大，那就还是按照之前的做法，如果减数大，那就用减数减去被减数，然后最高位存负号：
HP sub(HP h1, HP h2){
HP h;
int jw = 0,t, max;
if(Max(h1,h2)) {
max = h1.len;
for(int i = MAX-1;i>=MAX-max;i--){
t = h1.data[i]-h2.data[i]-jw;
if(t<0){
h.data[i] = t+10;
jw = 1;
}
else{
h.data[i] = t;
jw = 0;
}
}
if(h.data[MAX-max]) h.len = max;
else h.len = max-1;
}
else{
h.data[0] = 1;
max = h2.len;
for(int i = MAX-1;i>=MAX-max;i--){
t = h2.data[i]-h1.data[i]-jw;
if(t<0){
h.data[i] = t+10;
jw = 1;
}
else{
h.data[i] = t;
jw = 0;
}
}
if(h.data[MAX-max]) h.len = max;
else h.len = max-1;
}
return h;
}我们还需要重写一下输出函数，因为这个时候，最高位表示符号了，我们需要判断一下最高位是否为0，如果不为0，说明该数是负数，要输出负号。代码如下：
void print(HP h){
if(h.data[0]) cout<<"-";
for(int i = MAX-h.len;i<MAX;i++) cout<<h.data[i];
cout<<endl;
}举个栗子：
int main(){
string s1 = "00045926",s2 = "123456";
HP h1 = str2Arr(s1),h2 = str2Arr(s2);
print(h1);
print(h2);
HP h = sub(h1, h2);
print(h);
return 0;
}执行结果如下：
接下来，就让我们走进乘除法的世界吧。
2 高精度乘除法
高精度乘除法要考虑的，跟我们小学学习的做法是一样的。让我们直接走进乘除法吧。
1 高精度乘法
首先我们先来看高精度的加法。高精度的加法思想就是我们小学数学加法的思想，我们以351×18为例说明：
这种做法就是只要有进位，我们就会进位。在具体实现过程中，如果我们频繁进位，算法复杂度相对较高，我们可以先统一计算，最后统一进位：
然后我们需要考虑，a的第i位和b的第j位相乘，得到的是c的第i+j-1位。即：
c[i+j-1] += a[i]*b[j];
这个时候的i和j是从后往前的。真正在数组中存放的时候，个位存放在索引为MAX-1上，十位存放在MAX-2上。这部分代码如下：
for(int i = 1;i<=h1.len;i++){
for(int j = 1;j<=h2.len;j++){
h.data[MAX-i-j+1] += h1.data[MAX-i]*h2.data[MAX-j];
}
}我们得到上面的数据之后，就要开始进位了，一个a位数和一个b位数相乘，如果最高位没有进位，乘积就是a+b-1位，如果最高位有进位，乘积就是a+b位。
我们默认最高位有进位，一直计算到最高位，然后再判断最高位是否为0，如果为0，则乘积就是a+b-1位，如果最高位不是0，乘积就是a+b位。代码如下：
for(int i = 1;i<h1.len+h2.len;i++){
h.data[MAX-i-1] += h.data[MAX-i]/10;
h.data[MAX-i] %= 10;
}
if(h.data[MAX-h1.len-h2.len]) h.len = h1.len+h2.len;
else h.len = h1.len+h2.len-1;完整代码如下：
HP mul(HP h1, HP h2){
HP h;
for(int i = 1;i<=h1.len;i++){
for(int j = 1;j<=h2.len;j++){
h.data[MAX-i-j+1] += h1.data[MAX-i]*h2.data[MAX-j];
}
}
for(int i = 1;i<h1.len+h2.len;i++){
h.data[MAX-i-1] += h.data[MAX-i]/10;
h.data[MAX-i] %= 10;
}
if(h.data[MAX-h1.len-h2.len]) h.len = h1.len+h2.len;
else h.len = h1.len+h2.len-1;
return h;
}我们写如下主函数：
int main(){
string s1 = "000999",s2 = "0000999";
HP h1 = str2Arr(s1),h2 = str2Arr(s2);
print(h1);
print(h2);
HP h = mul(h1, h2);
print(h);
return 0;
}执行结果为：
如果是最高位不进位，结果如下：
2 高精度除法
高精度除法一般我们考虑除数是非高精度数，即我们可以使用int类型进行存储。然后我们做高精度除法，不仅要得到商，还要得到余数。
例如我们计算 。我们要先找到商的最高位，我们发现3，36和366都比999小，所以最高位应该是
这个过程就是说，我们要先从最高位开始找起，直到找到的部分比除数大。当然，也存在被除数本身就比除数小，那么我们找到最后一个，也不会使得找的部分大于除数。所以我们需要两个判断条件，一个是找到的部分比除数小，另一个是找的位数不为0（最极端就是找到位数为1，也就是个位）。这部分代码如下：
int l = h1.len, t = 0;
while(t<b&&l){
t = t*10 + h1.data[MAX-l];
l--;
}
这个时候，如果l为0，那就说明被除数的位数已经找完，这个时候，商的位数为1位。如果l不为0，因为l多减了一次，l比商的位数小1。所以商的位数为l+1。商的最高位是目前的部分除以除数。
h2.len = l+1;
h2.data[MAX-l-1] = t/b;
然后，如果我们还没有计算到被除数的个位，也就是说l还不为0，那我们就要继续运算。每次运算，都要用上次计算的余数加上后面的一位数（这个加是附加，也就是余数*10+后一位数），然后商的对应位就是得到的数除以除数：
while(l){
t = t%b*10+h1.data[MAX-l];
h2.data[MAX-l] = t/b;
l--;
}当l为0的时候，就说明我们已经运算到最后一位了，我们就可以求余数了：
r = t%b;
完整代码如下：
#include<iostream>
using namespace std;
#define MAX 100
struct HP {
int data[MAX] = {};
int len;
};
HP str2Arr(string s){
HP h;
int i = 0;
while(s[i] == '0' && i<s.size()-1) i++;
s = s.substr(i);
h.len = s.size();
for(int i = 0;i<h.len;i++) h.data[MAX-i-1] = s[h.len-i-1] - '0';
return h;
}
void div(HP h1, int b, HP &h2, int &r){
int l = h1.len, t = 0;
while(t<b&&l){
t = t*10 + h1.data[MAX-l];
l--;
}
h2.len = l+1;
h2.data[MAX-l-1] = t/b;
while(l){
t = t%b*10+h1.data[MAX-l];
h2.data[MAX-l] = t/b;
l--;
}
r = t%b;
}
void print(HP h){
if(h.data[0]) cout<<"-";
for(int i = MAX-h.len;i<MAX;i++) cout<<h.data[i];
cout<<endl;
}
int main(){
string s1 = "000351";
HP h1 = str2Arr(s1),h2;
int b=18,r;
print(h1);
div(h1, b, h2, r);
cout<<h2.len<<endl;
print(h2);
cout<<r<<endl;
return 0;
}
执行结果如下：
3 作业
本节课的作业，就是复习上面的所有知识，能够默写出所有高精度代码。
AI与区块链技术
