C++基础算法①——高精度加减法计算

这篇具有很好参考价值的文章主要介绍了C++基础算法①——高精度加减法计算。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.导论

当我们利用计算机进行数值计算,有时候会遇到这样的问题: n!的精确结果是多少?
当n小于30的时候,我们当然可以通过电脑自带的计算器计算出来。但是当我们遇到 100! 的时候就没有办法直接计算出精确的结果。再比如,求两个20000位的数的和。

那怎么解决精度缺失的问题?
高精度算法(High Accuracy Algorithm) 是处理大数字的数学计算方法。

  • 在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算。对于非常庞大的数字无法在计算机中正常存储。
  • 于是,将这个数字拆开,拆成一位一位的,或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字,这样这个数字就被称为是高精度数。
  • 高精度算法就是能处理高精度数各种运算的算法,但又因其特殊性,故从普通数的算法中分离,自成一家。
  • 高精度处理,实际上就是模拟法,模拟手算,它的原理与我们用竖式计算时一样的,不过在处理过程中要注意高精度数据的读入、转换储存、数据的计算、结果位数的计算、输出等几个问题。

2.高精度+低精度

有一个很大的数,例如 99999999999999999;一个小的数6666。如何把这两个数加起来呢?

高精度的加法思想

  1. 把大数存到字符串;

  2. 字符串的每个字符数字都通过ASCII转换存到数组,
    注意的是要低位存在数组开头:a[i] = s[len-i-1]-‘0’;

  3. 加法进位的算式:
    ① a[i+1] += a[i]/10;
    ② a[i] %= 10;

  4. 数字溢出,长度+1;

  5. 反向输出结果;

来看下我们怎么做的,以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];
	}
} 

c++高精度减法,算法,C++,算法,c++,数据结构,青少年编程


3.高精度+高精度

跟上面步骤相似。

高精度的加法思想:

  1. 把大数存到字符串;
  2. 字符串的每个字符数字都通过ASCII转换存到数组,
    注意的是要低位存在数组开头:a[i] = s[len-i-1]-‘0’;
  3. 获取最大的数长度:max(len1,len2) ;
  4. 加法进位的算式:
    ① a[i+1] += a[i]/10;
    ② a[i] %= 10;
  5. 数字溢出,长度+1;
  6. 反向输出结果;
#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;
} 

c++高精度减法,算法,C++,算法,c++,数据结构,青少年编程


4.高精度减法

减法是这样要求的,当两数相减<0,要输出带负 ‘-’ 号!

高精度减法的思想:

  1. 输入两个大数;

  2. 判断大小,固定s1恒大于s2:

  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. 去除前导零;

  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';
	} 

转为整数存到数组里面后,进行减法运算,根据减法规则,不够减的要借位+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];
	} 

高精度减法完整代码:

/*
高精度减法的思想
	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;
} 

c++高精度减法,算法,C++,算法,c++,数据结构,青少年编程文章来源地址https://www.toymoban.com/news/detail-599102.html

到了这里,关于C++基础算法①——高精度加减法计算的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C/C++ 高精度(加减乘除)算法二进制优化

    第一章 简单实现 第二章 压位优化 第三章 二进制优化(本章) 上一章《C/C++ 高精度(加减乘除)算法压位优化》实现了优化的高精度计算,采用int32的整型数组每个元素可以储存9个10进制数字,想要再进一步优化计算速度,可以改变数据存储方式,采用二进制存储数字。依然采

    2024年02月11日
    浏览(41)
  • 通过类实现矩阵加减法、乘法、转置(C++))

    定义一个二维方阵类 matrix 通过重载二元运算符“+”、“-”、“*”和一元运算符“~”, 来实现矩阵加、矩阵减、矩阵乘以及矩阵转置。 1.由于矩阵的行与列都是未知的,首先需要通过 动态分配内存 实现创建任意大小的矩阵,由于类中默认的构造函数无法满足我们的需求,

    2024年02月06日
    浏览(58)
  • 高精度减法

    要实现两个高精度数的减法,和高精度加法一样都是模拟竖式计算的过程,主要就是解决以下两个问题。 谁大谁小? 由于这两个数字都很大,但是不知道谁更大,所以要先判断哪个数更大,思路如下: 判断这两个数谁的位数更大,位数更大的自然更大。 如果位数不相同,从

    2024年02月08日
    浏览(55)
  • 高精度减法(C语言实现)

    众所周知,整数在C和C++中以 int , long , long long 三种不同大小的数据存储,数据大小最大可达 2^64 ,但是在实际使用中,我们仍不可避免的会遇到爆 long long 的超大数运算,这个时候,就需要我们使用高精度算法,来实现巨大数的运算。 高精度的本质是将数字以字符串的形

    2024年02月05日
    浏览(51)
  • 高精度加法,减法,乘法,除法(下)(C语言)

    前言 上一篇博客我们分享了高精度加法,减法,这一期我将为大家讲解高精度乘法和高精度除法。那让我们开始吧! 对加法和减法感兴趣的话就点我 让我们想想我们平时做数学时遇见乘法是怎么做的。以下图为例。 高精度乘法也是这样的一个思路,首先我们先把a和b的值储存

    2024年02月04日
    浏览(71)
  • 高精度加法,减法,乘法,除法(上)(C语言)

    前言 本篇内容介绍加法和减法,如果想看乘法和除法就点这里-高精度乘法,除法 加,减,乘,除这些运算我们自然信手捏来,就拿加法来说,我们要用c语言编程算a+b的和,只需让sum = a+b即可,可是这是局限的,我们都知道int的表示的最大值为2147483647(32位和64位机器)。但

    2024年02月03日
    浏览(44)
  • 高精度(加减乘除)

    高精度的核心思想就是利用数组去储存大数,然后通过模拟手动计算的方式,来进行计算。 主要分三个模块: 1.读入数据并转换为(int)类型储存 核心思想:将每个位上的数字都+起来,如果大于10就进位。 核心代码如下: 完整代码及解析如下: 减法核心:只使用大数减小数

    2024年02月08日
    浏览(49)
  • C++高精度算法

    目录 前言:  思路: 高精度加法: 高精度减法: 高精度乘法: 高精度除法:  代码: 一、高精度加法 二、高精度减法  三、高精度乘法  四、高精度除法 最后         计算机最初、也是最重要的应用就是数值运算。在编程进行数值运算时,有时会遇到运算的精度要求特

    2024年02月14日
    浏览(54)
  • C++ 算法 高精度(较详细.)

            在我们进行计算的过程中,经常会遇到 几十位,甚至几百位的数字 的计算问题,也有可能会遇到小数点后几十位,几百位的情况,而我们面对这样的情况下,   和 的数据范围显然是 不够使用 的了。因此这时,我们就需要引入一个新的算法,叫做 高精度算法

    2023年04月10日
    浏览(39)
  • C语言 加减乘除模 的 高精度计算 (超详细)

    目录 高精度加法 高精度乘法 高精度减法          高精度除法 高精度模法   高精度计算 是模拟算法的一种,通过字符串和整型数组的使用,将加减乘除的竖式运算 模拟 出来,达到计算的目的。其步骤大致分为:一,将字符串数据存到整型数组中,二,模拟算法,不同的

    2023年04月24日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包