导读
信息学能够有助于孩子未来工作发展，提升孩子的综合能力。
这一节课我们开始走进高精度算法的世界，了解如何定义高精度算法，如何输出高精度算法，以及利用高精度算法进行加减法操作。
1 看个例子
我们尝试输出一下10的1次方到32次方，我们知道10的32次方特别大，并且都是正整数，所以我们使用unsigned long long 类型。
代码如下：
#include<iostream>
using namespace std;
int main(){
unsigned long long a = 10;
for(int i = 0;i<32;i++){
cout<<"a的"<<i+1<<"次方为："<<a<<endl;
a*=10;
}
return 0;
}
执行结果如下：
a的1次方为：10
a的2次方为：100
a的3次方为：1000
a的4次方为：10000
a的5次方为：100000
a的6次方为：1000000
a的7次方为：10000000
a的8次方为：100000000
a的9次方为：1000000000
a的10次方为：10000000000
a的11次方为：100000000000
a的12次方为：1000000000000
a的13次方为：10000000000000
a的14次方为：100000000000000
a的15次方为：1000000000000000
a的16次方为：10000000000000000
a的17次方为：100000000000000000
a的18次方为：1000000000000000000
a的19次方为：10000000000000000000
a的20次方为：7766279631452241920
a的21次方为：3875820019684212736
a的22次方为：1864712049423024128
a的23次方为：200376420520689664
a的24次方为：2003764205206896640
a的25次方为：1590897978359414784
a的26次方为：15908979783594147840
a的27次方为：11515845246265065472
a的28次方为：4477988020393345024
a的29次方为：7886392056514347008
a的30次方为：5076944270305263616
a的31次方为：13875954555633532928
a的32次方为：9632337040368467968
--------------------------------
Process exited after 2.367 seconds with return value 0
请按任意键继续. . .
我们发现，从10的20次方开始，数据就出问题了，这是因为unsigned long long 类型最多只能存19位数据。
但是在竞赛中或者实际情况中，我们的数据可能远超过19位。这个时候怎么办呢？我们引入高精度算法，来解决这类问题。
2 高精度算法理论
高精度算法就是当我们不能再用普通的数据类型来存放整数时，我们就要考虑用其他方式存放，并实现数据的运算。
我们读入数据，可以通过字符串或者数组读入，然后需要自己定义相关的运算算法。
如果我们是通过字符串读入的，我们就要将字符串转为数组，数组中每一个位置存放一个字符，即存放一个1位数并表示一个数位。例如：
我们采用从后往前存储的方式，即前面会有很多位置存放的数据是0。例如我们将一个字符串存到高精度数组如下：
代码如下：
int str2Arr(string s){
int len = s.size();
for(int i = 0;i<len;i++){
a[MAX - i - 1] = s[len-i-1] - '0';
}
return 0;
}
我们还要对高精度数据进行输出，输出的时候要注意，最前面的0不能输出，如果全都是0，要输入0。
void print(){
int i = 0;
while(a[i] == 0 && i<MAX){
i++;
}
if(i == MAX) cout<<a[i-1]<<endl;
else{
for(;i<MAX;i++){
cout<<a[i];
}
}
}
全部代码如下：
#include<iostream>
#include<string>
using namespace std;
#define MAX 100
int a[MAX];
int str2Arr(string s){
int len = s.size();
for(int i = 0;i<len;i++){
a[MAX - i - 1] = s[len-i-1] - '0';
}
return 0;
}
void print(){
int i = 0;
while(a[i] == 0 && i<MAX){
i++;
}
if(i == MAX) cout<<a[i-1]<<endl;
else{
for(;i<MAX;i++){
cout<<a[i];
}
}
}
int main(){
string s = "0000102345678912345678900";
str2Arr(s);
print();
return 0;
}
执行结果如下：
注：考虑到后面我们还会用到各种的运算，我们使用结构体会更加方便，全部代码如下：
#include<iostream>
using namespace std;
#define MAX 100
struct HP {
int data[MAX] = {};
int len;
// bool pos; //正负
};
int a[MAX],b[MAX],c[MAX];
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;
}
在这个代码中，我们的结构体内部对数组进行初始化，如果我们不想这么做，我们可以定义初始化函数来初始化结构体。
1 高精度加法
首先我们先来看高精度的加法。高精度的加法思想就是我们小学数学加法的思想：
代码如下：
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;
}
执行结果如下：
2 高精度减法（情况1）
高精度减法的第一种情况就是被减数大于或等于减数。也就是说，差是一个正数。
这个减法跟我们小学减法的过程是一致的，如果当前位被减数的值大于减数，那就直接相减，如果小于就需要借位。
代码如下：
#include<iostream>
using namespace std;
#define MAX 100
struct HP {
int data[MAX] = {};
int len;
// bool pos; //正负
};
int a[MAX],b[MAX],c[MAX];
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;
}
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;
}
int main(){
string s1 = "000145926",s2 = "123456";
HP h1 = str2Arr(s1),h2 = str2Arr(s2),h;
print(h1);
print(h2);
h = sub(h1, h2);
print(h);
return 0;
}
执行结果如下：
3 作业
本节课的作业，就是复习上面的所有知识，并完成下面两道题目！
1 高精度减法（情况2）
如果被减数小于减数，如何实现这个减法；
2 高精度减法（情况综合）
如果不确定被减数和减数的大小情况，如果在一个程序中实现两种情况。
AI与区块链技术
长按二维码关注
