1.导论
当我们利用计算机进行数值计算,有时候会遇到这样的问题: n!的精确结果是多少?
当n小于30的时候,我们当然可以通过电脑自带的计算器计算出来。但是当我们遇到 100! 的时候就没有办法直接计算出精确的结果。再比如,求两个20000位的数的和。
那怎么解决精度缺失的问题?
高精度算法(High Accuracy Algorithm) 是处理大数字的数学计算方法。
- 在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算。对于非常庞大的数字无法在计算机中正常存储。
- 于是,将这个数字拆开,拆成一位一位的,或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字,这样这个数字就被称为是高精度数。
- 高精度算法就是能处理高精度数各种运算的算法,但又因其特殊性,故从普通数的算法中分离,自成一家。
- 高精度处理,实际上就是模拟法,模拟手算,它的原理与我们用竖式计算时一样的,不过在处理过程中要注意高精度数据的读入、转换储存、数据的计算、结果位数的计算、输出等几个问题。
2.高精度+低精度
有一个很大的数,例如 99999999999999999;一个小的数6666。如何把这两个数加起来呢?
高精度的加法思想
-
把大数存到字符串;
-
字符串的每个字符数字都通过ASCII转换存到数组,
注意的是要低位存在数组开头:a[i] = s[len-i-1]-‘0’; -
加法进位的算式:
① a[i+1] += a[i]/10;
② a[i] %= 10; -
数字溢出,长度+1;
-
反向输出结果;
来看下我们怎么做的,以C++语言编程为例子。
#include<iostream>
#include<string>
using namespace std;
string s1;
int a[1000],b;
int main(){
cin>>s1>>b; // 1.输入数值
代码中,s1数组存的是大数,b整数存小数。
① 1234 + 66
② 123456 + 99
按照数学加法运算,是先个位数与个位数相加,也就是
① s1[3] + 6
② s1[5] + 9
由上面可知,个位数+个位数的索引下标不一致,会增加编程难度。那可以考虑把数组倒序存储!个位数放到数组开头位置也就是s1[0],那无论数值多大,数组下标都是s1[0] 开始进行加法的。
// s1存到数组a里面,记得转为整数
int len1 = s1.size(); //获取长度
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
因为s1是字符串要通过ASCII码表转成整数,所以要减掉 -‘0’。
好,上面我们已经完成把大数存到数组里了,接着要进行加法运算。
- 把小数先加到a[0]位置:
a[0] +=b;
例如 1234 + 89 =》a[0] = 1323; - 接着把新的个位数留在a[0],其他位数进行 进位操作。
a[0+1] += a[0] /10; // a[1] = 3+132 = 135
a[0] = a[0] % 10; // a[0] = 3
- 以此类推,更新十位数,其他位数进位操作。
//3.进行加法运算。
a[0]+=b; // 5+9999 10004
//4.进位操作
for(int i=0;i<len1;i++){
a[i+1] += a[i] / 10;
a[i] = a[i] % 10;
}
加法运算后,要考虑到数子溢出的情况; 例如 999 +11 == 1010 多出来了千位数。解决这个问题简单,判断最高位是否不为0,满足条件就再一次进行进位操作!
//5.考虑到数字溢出
while(a[len1]){
a[len1+1] += a[len1]/10;
a[len1] %= 10;
len1++;
}
最后输出结果,记得要反向,因为前面我们a[0] 是最低位,输出从左到右是高位到低位的。
//6.反向输出
for(int i=len1-1;i>=0;i--){
cout<<a[i];
}
高精度+低精度完整代码如下:
#include<iostream>
#include<string>
using namespace std;
string s1;
int a[1000],b;
int main(){
cin>>s1>>b;
// s1存到数组a里面,记得转为整数
int len1 = s1.size();
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
//3.进行加法运算。
a[0]+=b; // 5+9999 10004
//4.进位操作
for(int i=0;i<len1;i++){
a[i+1] += a[i] / 10;
a[i] = a[i] % 10;
}
//5.考虑到数字溢出
if(a[len]){
len++;
}
//6.反向输出
for(int i=len1-1;i>=0;i--){
cout<<a[i];
}
}
3.高精度+高精度
跟上面步骤相似。
高精度的加法思想:
- 把大数存到字符串;
- 字符串的每个字符数字都通过ASCII转换存到数组,
注意的是要低位存在数组开头:a[i] = s[len-i-1]-‘0’; - 获取最大的数长度:max(len1,len2) ;
- 加法进位的算式:
① a[i+1] += a[i]/10;
② a[i] %= 10; - 数字溢出,长度+1;
- 反向输出结果;
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int a[10000],b[10000],c[100001];
int main(){
// 1.输入值,长度
cin>>s1>>s2;
int len1 = s1.size();
int len2 = s2.size();
// 2.把字符转为整数存到数组
// 注意要个位存到数组开头
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
for(int i=0;i<len2;i++){
b[i] = s2[len2-i-1]-'0';
}
两个大数都要存到字符串,再转为整数。然后按照位数,数组下标依次相加,也就是a[i]+b[i]。加到什么时候停止是由长度最大的数决定的,所以我们要求最大的数长度,再进行加法。
// 3.获取最大的数。
int len = max(len1,len2);
// 对各个位数进行相加并把最新的值存到输出C里面。
for(int i=0;i<len;i++){
c[i]=a[i]+b[i];
}
通过c[i] = a[i]+b[i]; 可能会出现例如 c[0] = 11,大于10的情况,需要进位!
//4.进位
for(int i=0;i<len;i++){
c[i+1] += c[i]/10;
c[i] %= 10;
}
还是一样的,进位后考虑到溢出问题,然后反向输出
//6.考虑到数字溢出
if(a[len]){
len++;
}
//7.反向输出
for(int i=len-1;i>=0;i--){
cout<<a[i];
}
高精度+高精度完整代码:
/*
高精度的加法思想
1.把大数存到字符串;
2.字符串的每个字符数字都通过ASCII转换存到数组,
注意的是要低位存在数组开头:a[i] = s[len-i-1]-'0';
3.获取最大的数长度:max(len1,len2) ;
4.把a,b值加入到c数组: c[i] = a[i]+b[i];
5.c数组加法进位的算式:
① c[i+1] += c[i]/10;
② c[i] %= 10;
6.数字溢出,长度+1;
7.反向输出结果;
*/
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int a[10000],b[10000],c[100001];
int main(){
// 1.输入值,长度
cin>>s1>>s2;
int len1 = s1.size();
int len2 = s2.size();
// 2.把字符转为整数存到数组
// 注意要个位存到数组开头
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
for(int i=0;i<len2;i++){
b[i] = s2[len2-i-1]-'0';
}
// 3.获取最大的数。
int len = max(len1,len2);
// 对各个位数进行相加
for(int i=0;i<len;i++){
c[i]=a[i]+b[i];
}
//4.进位
for(int i=0;i<len;i++){
c[i+1] += c[i]/10;
c[i] %= 10;
}
//5.溢出
while(c[len]==0 && len>0){
len--;
}
if(c[len]>0){
len++;
}
//6.反向输出
for(int i=len-1;i>=0;i--){
cout<<c[i];
}
return 0;
}
4.高精度减法
减法是这样要求的,当两数相减<0,要输出带负 ‘-’ 号!
高精度减法的思想:
-
输入两个大数;
-
判断大小,固定s1恒大于s2:
-
获取长度;
-
字符变整数:a[i] = s1[len1-i-1]-‘0’;
-
减法运算:
① if(a[i]<b[i]){
a[i+1]–; //上位–
a[i]+=10; // 本位+10
}
② c[i] = a[i]-b[i]; -
去除前导零;
-
反向输出;
看下,输入值,输入第一个代表减数,第二个代表被减数;我们知道减法是会有负数情况的,所以要考虑到减数<被减数情况。也就是 减数长度 < 被减数长度 或者 长度相等情况 减数值 < 被减数值。那我们就输出 ‘-’ 号,和交换两个的值。永久实现减数 恒大于 被减数!!!
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int a[10000],b[10000],c[10000];
int main(){
// 1.输入值
cin>>s1>>s2;
// 2.判断大小,固定s1恒大于s2
if(s1.size()<s2.size() || s1.size()==s2.size() && s1<s2){
swap(s1,s2); //交换值
cout<<"-";
}
// 3.获取长度
int len1 = s1.size();
int len2 = s2.size();
// 4.字符变整数
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
for(int i=0;i<len2;i++){
b[i] = s2[len2-i-1]-'0';
}
转为整数存到数组里面后,进行减法运算,根据减法规则,不够减的要借位+10,被借位的要减1。例如 1234 - 66。 如果 a[0] - b[0] < 0,就要借位+10,也就是 a[0] + 10 后再减 b[0];然后被借位 a[0+1]–;
//5.减法运算
for(int i=0;i<len1;i++){
if(a[i]<b[i]){
a[i+1]--; //被借位--
a[i]+=10; // 本位+10
}
c[i] = a[i]-b[i]; //相减结果存到数组c
}
要注意的是:123 -120 = 003,前面的零要消除掉。然后再反向输出。
//6.去除前导零
while(c[len1-1]==0 && len1>1){
len1--;
}
//7.反向输出
for(int i=len1-1;i>=0;i--){
cout<<c[i];
}
高精度减法完整代码:文章来源:https://www.toymoban.com/news/detail-599102.html
/*
高精度减法的思想
1.输入大数;
2.判断大小,固定s1恒大于s2:
if(s1.size()<s2.size() || s1.size()==s2.size() && s1<s2){
swap(s1,s2); //交换值
cout<<"-";
}
3.获取长度;
4.字符变整数:a[i] = s1[len1-i-1]-'0';
5.减法运算:
if(a[i]<b[i]){
a[i+1]--; //上位--
a[i]+=10; // 本位+10
}
c[i] = a[i]-b[i];
6.去除前导零;
while(c[len1-1]==0 && len1>1){
len1--;
}
7.反向输出;
*/
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int a[10000],b[10000],c[10000];
int main(){
// 1.输入值
cin>>s1>>s2;
// 2.判断大小,固定s1恒大于s2
if(s1.size()<s2.size() || s1.size()==s2.size() && s1<s2){
swap(s1,s2); //交换值
cout<<"-";
}
// 3.获取长度
int len1 = s1.size();
int len2 = s2.size();
// 4.字符变整数
for(int i=0;i<len1;i++){
a[i] = s1[len1-i-1]-'0';
}
for(int i=0;i<len2;i++){
b[i] = s2[len2-i-1]-'0';
}
//5.减法运算
for(int i=0;i<len1;i++){
if(a[i]<b[i]){
a[i+1]--; //上位--
a[i]+=10; // 本位+10
}
c[i] = a[i]-b[i];
}
//6去除前导零
while(c[len1-1]==0 && len1>1){
len1--;
}
//7.反向输出
for(int i=len1-1;i>=0;i--){
cout<<c[i];
}
return 0;
}
文章来源地址https://www.toymoban.com/news/detail-599102.html
到了这里,关于C++基础算法①——高精度加减法计算的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!