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

高精度算法

  • 1.导论
  • 2.高精度+低精度
  • 3.高精度+高精度
  • 4.高精度减法

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

在这里插入图片描述

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

高精度+高精度完整代码：

#include<iostream>
#include<string>
using namespace std;
//12345647899513131515656
//54213213
string s; // 大数 
int a[10000],b; // b代表小数 
int main(){
//	1.输入值
	cin>>s>>b;
//	2.如何把s转为整数存到数组
	int len = s.size(); //字符串长度
//	3.分别把每一个字符存到整数数组里面！
	for(int i=0;i<len;i++){
		//a[0]存最低位(个位数),把字符转为数字 
		a[i] = s[len-i-1]-'0'; 
	}	
//	4.两个数相加，a[0]+b
	a[0] += b; //9+1111 a[0]=1120 
	//5.进位 
	for(int i=0;i<len;i++){
		a[i+1] += a[i] / 10; //进位 
		a[i] %= 10; //本位 
	}
	//6.考虑到数字溢出 
	if(a[len]){
		len++;
	} 
	//7.反向输出 
	for(int i=len-1;i>=0;i--){
		cout<<a[i];
	}
	return 0;
}

在这里插入图片描述

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

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/16.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

「Vue面试题」动态给vue的data添加一个新的属性时会发生什么？怎样去解决的？

「Vue面试题」动态给vue的data添加一个新的属性时会发生什么？怎样去解决的？

一、直接添加属性的问题 我们从一个例子开始 定义一个p标签&#xff0c;通过v-for指令进行遍历 然后给botton标签绑定点击事件&#xff0c;我们预期点击按钮时&#xff0c;数据新增一个属性&#xff0c;界面也 新增一行 <p v-for"(value,key) in item" :key&q…
阅读更多...
学习 Python 之 Pygame 开发坦克大战（一）

学习 Python 之 Pygame 开发坦克大战（一）

学习 Python 之 Pygame 开发坦克大战&#xff08;一&#xff09;Pygame什么是Pygame?初识pygame1. 使用pygame创建窗口2. 设置窗口背景颜色3. 获取窗口中的事件4. 在窗口中展示图片(1). pygame中的直角坐标系(2). 展示图片(3). 给部分区域设置颜色5. 在窗口中显示文字6. 播放音…
阅读更多...
如何在CSDN中使用ChatGPT

如何在CSDN中使用ChatGPT

本篇文章致力于帮助大家理解和使用ChatGPT&#xff08;现在CSDN改成”C知道“了&#xff09;。简介ChatGPT是OpenAI公司开发的一种大型语言模型。它是一种基于Transformer架构的深度学习模型&#xff0c;可以对语言进行建模和生成。它可以处理问答、对话生成、文本生成等多种任…
阅读更多...
1.认识网络爬虫

1.认识网络爬虫

1.认识网络爬虫网络爬虫爬虫的合法性HTTP协议请求与响应(重点)网络爬虫 爬虫的全名叫网络爬虫&#xff0c;简称爬虫。他还有其他的名字&#xff0c;比如网络机器人&#xff0c;网络蜘蛛等等。爬虫就好像一个探测机器&#xff0c;它的基本操作就是模拟人的行为去各个网站溜达&am…
阅读更多...
TCP/IP协议

TCP/IP协议

✏️作者&#xff1a;银河罐头 &#x1f4cb;系列专栏&#xff1a;JavaEE &#x1f332;“种一棵树最好的时间是十年前&#xff0c;其次是现在” 目录TCP/IP协议应用层协议自定义应用层协议DNS传输层协议端口号UDP协议UDP协议端格式TCP协议TCP协议段格式TCP工作机制确认应答(安…
阅读更多...
单片机怎么实现真正的多线程？

单片机怎么实现真正的多线程？

所谓多线程都是模拟的&#xff0c;本质都是单线程&#xff0c;因为cpu同一时刻只能执行一段代码。模拟的多线程就是任务之间快速切换&#xff0c;看起来像同时执行的样子。据说最近有多核的单片机&#xff0c;不过成本应该会高很多。对于模拟的多线程&#xff0c;我知道的有两种…
阅读更多...
html实现浪漫的爱情日记（附源码）

html实现浪漫的爱情日记（附源码）

文章目录1.设计来源1.1 主界面1.2 遇见1.3 相熟1.4 相知1.5 相念2.效果和源码2.1 动态效果2.2 源代码2.3 代码结构源码下载更多爱情表白源码作者&#xff1a;xcLeigh 文章地址&#xff1a;https://blog.csdn.net/weixin_43151418/article/details/129264757 html实现浪漫的爱情…
阅读更多...
【C++】红黑树

【C++】红黑树

文章目录红黑树的概念红黑树的性质特征红黑树结点的定义红黑树的插入操作情况1情况2情况3特殊情况代码实现红黑树的验证红黑树的删除红黑树和AVL树的比较红黑树的应用红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但是每一个结点都增加一个存储位表示结点的颜…
阅读更多...
把C#代码上传到NuGet，大佬竟是我自己！！！

把C#代码上传到NuGet，大佬竟是我自己！！！

背景 刚发表完一篇博客总结自己写标准化C#代码的心历路程&#xff0c;立马就产生一个问题&#xff0c;就是我写好标准化代码后&#xff0c;一直存放磁盘的话&#xff0c;随着年月增加&#xff0c;代码越来越多&#xff0c;项目和版本的管理就会成为一个令我十分头疼的难题&…
阅读更多...
可路由计算引擎实现前置数据库

可路由计算引擎实现前置数据库

很多大机构都会有个中央数据仓库负责向应用提供数据服务。随着业务的发展&#xff0c;中央数据仓库的负载在持续增加。一方面&#xff0c;数仓是前端应用的数据后台&#xff0c;而前端应用不断增多&#xff0c;用户访问的并发数也不断增长。另一方面&#xff0c;数仓还要承担原…
阅读更多...
ChatGPT在工业领域的用法

ChatGPT在工业领域的用法

在工业数字化时代&#xff0c;我们需要怎么样的ChatGPT&#xff1f; 近日&#xff0c;ChatGPT热度高居不下&#xff0c;强大的人机交互能力令人咋舌&#xff0c;在国内更是掀起一股讨论热潮。一时间&#xff0c;这场由ChatGPT引起的科技飓风&#xff0c;使得全球最顶尖科技力量…
阅读更多...
C++回顾（一）——从C到C++

C++回顾（一）——从C到C++

前言 在学习了C语言的基础上&#xff0c;C到底和C有什么区别呢&#xff1f; 1.1 第一个C程序 #include <iostream>// 使用名为std的命名空间 using namespace std;int main() {// printf ("hello world\n");// cout 标准输出 往屏幕打印内容 相当于C语言的…
阅读更多...
【AI作画】使用stable-diffusion-webui搭建AI作画平台

【AI作画】使用stable-diffusion-webui搭建AI作画平台

一、安装配置Anaconda 进入官网下载安装包https://www.anaconda.com/并安装&#xff0c;然后将Anaconda配置到环境变量中。 打开命令行&#xff0c;依次通过如下命令创建Python运行虚拟环境。 conda env create novelai python3.10.6E:\workspace\02_Python\novalai>conda…
阅读更多...
最新文章

Copyright @ 2022~2023