这里是一些废话:
早在学习斐波那契数列兔子繁殖问题的时候,超过一定输入值的运算结果值会发生溢出,当时带我的于老师就有提了一句我的程序该如何处理大数据运算的问题,多年之后(?!你还好意思说),我终于又有了一个机会来学习这种运算方式。
由于是自己学习,在查阅资料的过程中遇到了一些困难,我发现有一些代码根本没有注释或者给的思路提示很少让我看不懂,或者是只写了一个加减运算就弃坑了。自己就下决心学会了高精度四则运算之后一定要写一个非常详细的思路和注释给初学者,但是我学会了以后就并不想写思考历程了(??),好吧好吧,为了让以后的自己看得懂自己的代码,就详细一点记录下来学习过程吧。
什么是高精度运算:
我们对一些数值的运算中可能会遇到这样的问题,运算数或者运算结果太大超出了int型甚至long long型的表示范围,这时我们需要手动按数位进行四则混合运算,也就是进行“高精度运算”。
高精度计算的基本步骤:
- 数据的接收:使用字符串进行需要运算的数据的接收;
- 数据的存储:获取字符串有效长度将这串数字存入整型数组中,字符串下标高下标(存放低数位)存入整型数组低下标;
- 数据的处理:按照对应法则进行运算;
- 数据输出:按照高下标(对应高数位)至低下标(对应低数位)进行输出,除法运算结果不一样,它是从低下标(对应高数位)至高下标(对应低数位)输出。
一、高精度加法:
和小学数学“列竖式”加法的过程相似,将两个数组进行从低位向高位的逐位相加、进位、求和。高精度加法就是在计算机内模拟这个运算过程。
// 高精加模板练习-注释版 自用
#include <iostream> // 标准输入输出头文件
#include <cstring> // 字符串头文件
using namespace std;
// 分别将要存放两个加数与结果,将它们定义在全局变量的位置可自动初始化为0
int a[1001], b[1001], c[1001];
int main(){
// 从控制台获取两个加数的值放进字符串中
string s1, s2;
cin >> s1 >> s2;
// 获取字符串的有效长度(不包括末尾'\0')
int L1 = s1.size();
int L2 = s2.size();
// 将字符串内容放进整型数组
// 整型数组低下标存放的是加数低位(对应字符串下标高位),还要将char转换为int
for(int i = 0; i < L1; i++) a[i] = s1[L1 - 1 - i] - '0';
for(int i = 0; i < L2; i++) b[i] = s2[L2 - 1 - i] - '0';
// 加法运算
int L = L1 > L2 ? L1 : L2; // 获取两加数中最大长度作为循环长度
for(int i = 0; i < L; i++){
c[i] += a[i] + b[i]; // 当前数位值等于之前运算的进位加当前两加数数位的和
if(c[i] >= 10){
c[i + 1] = 1; // 当前数位值大于10表明需要进位,给下一位值进一(最大也只能进一)
c[i] %= 10; // 计算进位之后当前数位值
}
}
// 判断最后结果的最高位(数组下标最末位)是否发生了进位,如果是则给结果长度加一
if(c[L] == 1) L++;
// 去掉结果前导零
int k = L--;
while(c[k] == 0 && k > 0) k--; // k此时指向数组最后一位下标
// 输出运算结果,从高位(对应高下标)至低位(对应低下标)输出
for(int i = k; i >= 0; i--) cout << c[i];
return 0;
}
二、高精度减法
类似于加法,也是使用模拟列竖式的方法进行运算。需要注意的一点是被减数一定要比减数大,否则要换两数的位置只能求绝对值,如何确定第一个数大于第二个数呢?两数不一样长的话长度长的比短的大,两数一样长的话直接用比较运算符进行比较,程序会按位比较两数 ASCII 码的值,从而得出两数的大小情况。还需要处理的问题是借位问题,不够减的话向高位借1当10。
// 高精减模板练习-注释版 自用
#include <iostream> // 输入输出头文件
#include <cstring> // 字符串头文件
using namespace std;
int a[1001], b[1001], c[1001];
int main(){
// 输入两个数字求差
string s1, s2;
cin >> s1 >> s2;
// size()计算字符串有效长度(不包括'\0')
int L1 = s1.size();
int L2 = s2.size();
// 第一个数比第二个数小的时候,需要交换两数位置
// ①第一个数比第二个数长度短
// ②第一个数和第二个数一样长,数值比第二个数少(string类型的比较是按位比较ASCII码)
if(L1 < L2 || L1 == L2 && s1 < s2){
string t = s1;
s1 = s2;
s2 = t;
swap(L1, L2); // s1,s2两个字符串进行交换时,它们对应的长度也要进行交换
}
// 字符串放进整型数组中,整型数组中低下标存放的是字符串高下标(数字低位)
for(int i = 0; i < L1; i++) a[i] = s1[L1 - 1 - i] - '0';
for(int i = 0; i < L2; i++) b[i] = s2[L2 - 1 - i] - '0';
// 减法运算
for(int i = 0; i < L1; i++){
if(a[i] < b[i]){ // 如果当前数位不够减,需要发生借位
a[i + 1]--;
c[i] = a[i] + 10 - b[i];
}else{
c[i] = a[i] - b[i];
}
}
// 去掉结果中的前导零
int k = L1--;
while(c[k] == 0 && k > 0) k--;
// 输出结果
for(int i = k; i >= 0; i--) cout << c[i];
return 0;
}
三、高精度乘法
同样采用竖式求值,采用for循环嵌套进行两个乘数之间的乘法运算,要记得进位问题。
// 高精乘模板练习-注释版 自用
#include <iostream> // 输入输出头文件
#include <cstring> // 字符串头文件
using namespace std;
// 分别存放两个乘数、积,定义在全局变量的位置可以自动初始化为零
int a[1001], b[1001], c[1001];
int main(){
// 以字符串形式输入两个乘数
string s1, s2;
cin >> s1 >> s2;
// size()获取两个字符串有效长度
int L1 = s1.size();
int L2 = s2.size();
// 将字符串中数字转入整型数组
for(int i = 0; i < L1; i++) a[i] = s1[L1 - 1 - i] - '0';
for(int i = 0; i < L2; i++) b[i] = s2[L2 - 1 - i] - '0';
// 乘法运算
for(int i = 0; i < L1; i++){
for(int j = 0; j < L2; j++){
c[i + j] += a[i] * b[j]; // 当前数位值是之前一次进位加本次乘法操作两加数的积
c[i + j + 1] += c[i + j] / 10; // 当前数值位的下一位,为它本身的值加本次进位的和
c[i + j] %= 10; // 进位操作后的当前数位
}
}
// 去除结果中的前导零,从高下标(高位)开始遍历
int k = L1 + L2; // 所得结果的最大长度不会超过 L1 + L2
while(c[k] == 0 && k > 0) k--;
// 输出结果,从高下标(高位)向低下标(低位)输出
for(int i = k; i >= 0; i--) cout << c[i];
return 0;
}
四、高精度除法
除法运算采用了按位相除法,需要注意的点是商的长度最大不会超过被除数的长度。每次除法运算过后,当前的余数乘以十加上下一位成为新的被除数继续运算。本程序中只做了关于高精度除以低精度的运算,高精度除以高精度还没来得及写,以后有时间补上(。
// 高精除(高精除以低精)模板练习-注释版 自用
#include <iostream>
#include <cstring>
using namespace std;
// 分别存放被除数、除数、商,声明在全局变量可使数组初始化为零
int a[1001], b[1001], c[1001];
int main(){
// 被除数和除数的获取
string s;
int b;
cin >> s;
cin >> b;
// 获取被除数长度并放进整型数组中,整型数组低下标(低位)存放字符串高下标(高位)
int L = s.size();
for(int i = 0; i < L; i++) a[i] = s[i] - '0';
// 除法运算
int x = 0; // 存放上次除法余下来的那个数
for(int i = 0; i < L; i++){
c[i] = (x * 10 + a[i]) / b; // 当前数位商等于 上次余数乘以十与本位被除数的和 除以除数
x = (x * 10 + a[i]) % b; // 计算当前余数
}
// 去除结果前导零,整型数组低下标存放高位,所以从低下标开始遍历去零
int k = 0;
while(c[k] == 0 && k < L) k++; // 此时k指向没有0的高位
// 输出结果,因为低下标存放高位,所以从低下标(高位)至高下标(低位)输出,商的长度最长不超过被除数长度
for(int i = k; i < L; i++) cout << c [i];
return 0;
}
参考来源:
C++中int、long、long long等数据类型的长度及范围:
int是short int的省略,占内存的2个字节,表示范围:-32768~32767;
long是long int的省略,占内存的4个字节,表示范围:-2147483648~2147483647;
long long 的字符长度是int型的两倍,现在int型一般为32位,所以long long是64位的,能支持的最大数为2^63 -1。
(参考来源:c++中 int, long long, double 等数据类型的长度及范围整理
c++中 int, long long, double 等数据类型的长度及范围整理_还我笑颜-CSDN博客_c++ long long范围)
strlen 是用来计算字符串的长度,遇到第一个NULL('\0')为止,不包括‘\0’。
sizeof 是用来计算变量或者对象、类型所占字节的多少。
(参考来源:strlen和sizeof的区别与总结
strlen和sizeof的区别与总结_follow_blast的博客-CSDN博客_strlen与sizeof)