【C++算法】——高精度（加，减，乘，除）

前言

高精度算法就是为了去解决一些比较大的数，这些数大到long long都存不下。，这里的主要思想就是用字符串来存。

下面的内容有很多用到c++的容器，不明白的可以先去学习stl。

一  高精度加法

首先第一步就是去模拟我们自己写的加法，，从我们自己写的加法上面来看，第一它是从个位开始加，如果大于10就会产生进位，这个进位要加到下一位去。

我们写加法是从个位开始，但是用代码去写，就需要倒过来，因为个位是不好去进位的，如果用个位去进位，那么就会导致整块的移动，这样效率就会很低了

图一是我们自己算，图二则是我们用代码去实现的过程

所以有了上面的准备，就可以写出下面代码

#include<iostream>
#include<vector>
using namespace std;

vector<int> add(const vector<int>& A, const vector<int>& B)//加法函数，这里传引用是为了提高效率
{
	int t = 0;
	vector<int>C;//用来返回
	for (int i = 0; i < A.size(); i++)//因为之前已经逆序了，所以这里直接从0开始遍历
	{
		t +=A[i];//首先把最长的数的最后一位加上
		if (i < B.size()) t += B[i];//因为B短，所以我们需要去判断B是否已经结束
		C.push_back(t % 10);//最后我们是插入t%10,如果大于就进位，小于就不进位
		t /= 10;//这里相当于是进位的过程
	}
	if (t) C.push_back(1);//还有A结束的时候，可能还有一个进位没有处理，这里把它尾插
	return C;
}


int main()
{
	string a, b;
	vector<int>A, B, C;
	cin >> a >> b;
	for (int i = a.size()-1; i >=0; i--)//逆置
	{
		A.push_back(a[i] - '0');//转换
	}
	for (int i = b.size() - 1; i >= 0; i--)
	{
		B.push_back(b[i] - '0');
	}

	if (A.size() > B.size()) C = add(A, B);//这里是调整A,B那个数长，长的放上面，比较好操作
	else C = add(B, A);

	for (int i = C.size()-1; i >= 0; i--)//因为是逆序相加的，所以这里需要再逆序倒过来输出
	{
		cout << C[i];
	}
	cout << endl;

	return 0;

}

 主函数里面的处理还是比较简单的，关键在于两个数的相加

二  高精度减法

其实减法也差不多，一样的反转，但是不同的就是我们需要用一个数去存一个借位，而不是进位，因为一个数减另外一个数不够我们就需要去借位，这样才能够减，第二就是我们在进行减法的时候需要的是去判断两个数的大小哪个更加大，而不是和加法一样去判断长度。

一样的，下面看代码理解

bool cmp(vector<int>& A, vector<int>& B)//比较函数
{
	if (A.size() != B.size())
		return A.size() > B.size();
	for (int i = A.size() - 1; i >= 0; i--)
	{
		if (A[i] != B[i])
			return A[i] > B[i];
	}
    return true;
}

vector<int> sub(vector<int>& A, vector<int>& B)//减法函数
{
	int t = 0;
	vector<int>C;
	for (int i = 0; i < A.size(); i++)
	{
		t = A[i] - t;//一开始没有借位
		if (i < B.size()) t -= B[i];
		C.push_back((t + 10) % 10);//这个是如果t>0,说明没有借位，如果小于0，就借位了
                                   //这里+10是先算它进位，然后再%10,如果没有进位，那就是它本身
                                   //如果进位了，那我们插入的就是10-t;
		if (t < 0) t = 1;//借位等于1，下次循环，A[i]就需要-1
		else t = 0;
	}
	while (C.size() > 1 && C.back() == 0)C.pop_back();//这里需要去掉前导零
	return C;
}
int main()
{
	string a, b;
	vector<int>A, B, C;
	cin >> a >> b;
	for (int i = a.size()-1; i >=0; i--)//这里操作和加法是一样的
	{
		A.push_back(a[i] - '0');
	}
	for (int i = b.size() - 1; i >= 0; i--)
	{
		B.push_back(b[i] - '0');
	}
	if (cmp(A, B)) C = sub(A, B);//这是判断大小
	else C = sub(B, A), cout << '-';//如果A小于B,那么我们可以换成-（B-A）
                                    //这里要多输出一个符号

	for (int i = C.size()-1; i >= 0; i--)
	{
		cout << C[i];
	}
	cout << endl;

	return 0;

}

三  高精度乘法

关于高精度乘法来说，就没有减法那么多处理了，甚至比加法还简单一点，这里的乘法是一个多位数和一个低位数的相乘

vector<int> mul(vector<int>& A, int b)
{
	int t = 0;
	vector<int>C;
	for (int i = 0; i < A.size(); i++)
	{
		t += A[i] * b;//t是进位
		C.push_back(t % 10);
		t /= 10;
	}
	if (t) C.push_back(t);//最后一位有进位就插入
	while (C.size() > 1 && C.back() == 0) C.pop_back();//处理前导零
	return C;
}

int main()
{
	string a;//这里直接正常操作就行
	int b;
	vector<int>A, C;
	cin >> a >> b;
	for (int i = a.size()-1; i >=0; i--)
	{
		A.push_back(a[i] - '0');
	}
	C = mul(A, b);
	for (int i = C.size()-1; i >= 0; i--)
	{
		cout << C[i];
	}
	cout << endl;

	return 0;

}

 

四  高精度除法

这里的除法和其他的又有点不一样，但是不一样的不会很多，第一就是我们除一个数可能除不尽，所以这里需要一个余数去存。

vector<int> div(vector<int>& A, int b,int &r)
{
	r = 0;
	vector<int>C;
	for (int i = A.size()-1; i >= 0; i--)//这里和其他的不一样，因为我们除法只能从个位开始除
	{
		r = r * 10 + A[i];//这里表示余数和下一个数的相加
		C.push_back(r / b);
		r %= b;
	}
	reverse(C.begin(), C.end());//这里因为上面的操作把C变为正序了，所以这里要反过来，因为
                                //后面打印是按逆序打印，这里就和上面同一了
	while (C.size() > 1 && C.back() == 0)C.pop_back();//去前导零
	return C;
}

int main()
{
	string a;
	int b;
	vector<int>A, C;
	cin >> a >> b;
	for (int i = a.size()-1; i >=0; i--)//这里操作和上面差不多
	{
		A.push_back(a[i] - '0');
	}
	int r;
	C = div(A, b,r);
	for (int i = C.size()-1; i >= 0; i--)
	{
		cout << C[i];
	}
	cout << endl;
	cout << r;
	

	return 0;

}

五 练习

a-b

这里直接用上面的代码就行

 

#include <iostream>
#include <vector>

using namespace std;
bool cmp(vector<int>& A, vector<int>& B)//比较函数
{
	if (A.size() != B.size())
		return A.size() > B.size();
	for (int i = A.size() - 1; i >= 0; i--)
	{
		if (A[i] != B[i])
			return A[i] > B[i];
	}
    return true;
}

vector<int> sub(vector<int>& A, vector<int>& B)//减法函数
{
	int t = 0;
	vector<int>C;
	for (int i = 0; i < A.size(); i++)
	{
		t = A[i] - t;//一开始没有借位
		if (i < B.size()) t -= B[i];
		C.push_back((t + 10) % 10);//这个是如果t>0,说明没有借位，如果小于0，就借位了
                                   //这里+10是先算它进位，然后再%10,如果没有进位，那就是它本身
                                   //如果进位了，那我们插入的就是10-t;
		if (t < 0) t = 1;//借位等于1，下次循环，A[i]就需要-1
		else t = 0;
	}
	while (C.size() > 1 && C.back() == 0)C.pop_back();//这里需要去掉前导零
	return C;
}
int main()
{
	string a, b;
	vector<int>A, B, C;
	cin >> a >> b;
	for (int i = a.size()-1; i >=0; i--)//这里操作和加法是一样的
	{
		A.push_back(a[i] - '0');
	}
	for (int i = b.size() - 1; i >= 0; i--)
	{
		B.push_back(b[i] - '0');
	}
	if (cmp(A, B)) C = sub(A, B);//这是判断大小
	else C = sub(B, A), cout << '-';//如果A小于B,那么我们可以换成-（B-A）
                                    //这里要多输出一个符号

	for (int i = C.size()-1; i >= 0; i--)
	{
		cout << C[i];
	}
	cout << endl;

	return 0;

}

a+b

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e6 + 10;
vector<int>add(vector<int>& A, vector<int>& B)
{
	vector<int>C;
	int t = 0;
	for (int i = 0; i < A.size() || i < B.size(); i++)
	{
		if (i < A.size()) t += A[i];
		if (i < B.size()) t += B[i];
		C.push_back(t % 10);
		t /= 10;
	}
	if (t)
	C.push_back(1);
	return C;

}
int main()
{
	string a, b;
	cin >> a >> b;
	vector<int>A, B;
	for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
	for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
	vector<int>C;
	C = add(A, B);
	for (int i = C.size() - 1; i >= 0; i--)
	{
		cout << C[i];
	}
	return 0;
}

 

六  总结

以上高精度算法，加法和乘法比较简单，除法和减法需要一点细节理解

加法没有去前导零的操作，其他都有，以上就是高精度的全部内容了，希望对你有所帮助

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

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

相关文章

活用变量，让Postman的使用飞起来

活用变量，让Postman的使用飞起来

在 Postman 中使用变量是一种非常强大的功能&#xff0c;它可以极大地增强 API 测试和开发的灵活性和效率。 Postman变量的类型 变量在 Postman 中可以在多个层次设置和使用&#xff0c;包括 全局变量环境变量集合变量局部变量&#xff08;如在脚本中暂时创建的变量&#xf…
阅读更多...
表驱动法 -优化逻辑分支

表驱动法 -优化逻辑分支

表驱动法 -优化逻辑分支 定义 表驱动法&#xff08;Table-Driven Approach&#xff09;是一种编程模式&#xff0c;可以将输入变量作为直接或间接索引在表里查找所需的结果或处理函数&#xff0c;而不使用逻辑语句&#xff08;if-else 和 switch-case&#xff09;。索引表可以…
阅读更多...
安卓中使用ttf字体文件

安卓中使用ttf字体文件

官方文档中提供的方法要设备能访问google&#xff1f; 官方方法 直接下载字体的fft文件 我要使用的是lexend 需要的格式可以在里面搜索 使用下载的ttf文件 解压出来 可以单独使用static里面的&#xff0c;里面是直接的lexend的各种格式 但是我这里直接使用Lexend-Vari…
阅读更多...
连接Huggingface报requests.exceptions.SSLError错误

连接Huggingface报requests.exceptions.SSLError错误

最近在学习使用 SHAP 算法解释 BERT 模型的输出结果&#xff0c;然而在从 Huggingface 上导入模型和数据集的过程中出现了网络连接相关的错误&#xff0c;本文用于记录错误类型和解决错误的方法。 1 代码示例 SHAP 官方展示的代码如下&#xff1a; import datasets import nu…
阅读更多...
Linux应急响应——知攻善防应急靶场-Linux(1)

Linux应急响应——知攻善防应急靶场-Linux(1)

文章目录 查看history历史指令查看开机自启动项异常连接和端口异常进程定时任务异常服务日志分析账户排查总结 靶场出处是知攻善防 Linux应急响应靶机 1 前景需要&#xff1a; 小王急匆匆地找到小张&#xff0c;小王说"李哥&#xff0c;我dev服务器被黑了",快救救我&…
阅读更多...
视频格式怎么转换？9 个免费视频转换工具

视频格式怎么转换？9 个免费视频转换工具

前 9 款免费视频转换器有哪些&#xff1f;在此视频转换器评论中&#xff0c;我们收集了一些有用的提示并列出了顶级免费视频转换器软件&#xff0c;还找出了适合所有级别&#xff08;从初学者到专家&#xff09;的最佳免费视频转换器。 1. Geekersoft免费在线视频转换 最好的免…
阅读更多...
【报错】JDBC SQL语句表名报错 解决办法

【报错】JDBC SQL语句表名报错 解决办法

解决办法 修改检测等级 不是检测有问题吗&#xff0c;那就将idea的检测问题取消掉或者修改检测问题等级&#xff0c;根本问题上我们写的sql语句是一个字符串传过去&#xff0c;只要在mysql查询语句能够正确执行&#xff0c;不要这种检测也罢。
阅读更多...
实际项目开发：Spring集成Redis，并实现短信登录功能

实际项目开发：Spring集成Redis，并实现短信登录功能

redis新手&#xff0c;学了几种基本数据类型&#xff0c;却不知道怎么使用&#xff1f; 总是一边学一边忘&#xff1f; 学会了Redis的大多数使用命令&#xff0c;却不知道如何在项目中使用&#xff1f; 本文将从实际出发&#xff0c;为大家解决这些问题。 我是蚊子码农&#xf…
阅读更多...
TikTok账号运营：静态住宅IP为什么可以防封？

TikTok账号运营：静态住宅IP为什么可以防封？

静态住宅IP代理服务是一种提供稳定、静态IP地址并可隐藏用户真实IP地址的网络代理服务。此类代理服务通常使用高速光纤网络来提供稳定、高速的互联网体验。与动态IP代理相比&#xff0c;静态住宅IP代理的IP地址更稳定&#xff0c;被封的可能性更小&#xff0c;因此更受用户欢迎…
阅读更多...
JAVA学习过程中遇到的问题

JAVA学习过程中遇到的问题

前言 记录学习过程中遇见的各种问题。希望对你有帮助。 目录 前言 1、新建maven项目时&#xff0c;archetype项目骨架加载慢 2、maven的pop.xml添加依赖项无法检测到 3、java: 无效的目标发行版: 20 4、idea添加maven依赖太慢 5、CTRLCV复制粘贴太慢 6、Swagger写接口文…
阅读更多...
20240621日志：大模型压缩-从闭源大模型蒸馏

20240621日志：大模型压缩-从闭源大模型蒸馏

目录 1. 核心内容2. 方法2.1 先验估计2.2 后验估计2.3 目标函数 3. 交叉熵损失函数与Kullback-Leibler&#xff08;KL&#xff09;损失函数 location&#xff1a;beijing 涉及知识&#xff1a;大模型压缩、知识蒸馏 Fig. 1 大模型压缩-知识蒸馏 1. 核心内容 本文提出在一个贝…
阅读更多...
(Amazing!) 通过 vfox 在 Windows 上安装管理多个 Erlang/OTP 和 Elixir 的版本

(Amazing!) 通过 vfox 在 Windows 上安装管理多个 Erlang/OTP 和 Elixir 的版本

大概一个多月前, 我写了篇关于如何使用跨平台版本管理工具 vfox 在 Linux 系统下安装管理多个 Erlang/OTP 版本的文章 -> 通过 vfox 安装管理多版本 Erlang 和 Elixir. 文章使用的示范操作系统是 Ubuntu 20.04 Linux 操作系统. 最近 vfox-erlang 和 vfox-elixir 插件的最新…
阅读更多...
如何关闭软件开机自启，提升电脑开机速度？

如何关闭软件开机自启，提升电脑开机速度？

如何关闭软件开机自启&#xff0c;提升电脑开机速度&#xff1f;大家知道&#xff0c;很多软件在安装时默认都会设置为开机自动启动。但是&#xff0c;有很多软件在我们开机之后并不是马上需要用到的&#xff0c;开机启动的软件过多会导致电脑开机变慢。那么&#xff0c;如何关…
阅读更多...
xshell使用vi命令：bash：vim：command not found

xshell使用vi命令：bash：vim：command not found

你们好&#xff0c;我是金金金。 场景 此时我通过xshell客户端连接到了远程的虚拟机。想用vi命令编辑一个文件时&#xff0c;显示&#xff1a;bash: vim: command not found 排查 看报错提示就可以知道&#xff0c;没找到vim命令 解决 使用包管理器 apt 来安装 vim 更新你的软…
阅读更多...
springboot+vue+mybatis旅游管理+PPT+论文+讲解+售后

springboot+vue+mybatis旅游管理+PPT+论文+讲解+售后

随着人民生活水平的提高,旅游业已经越来越大众化,而旅游业的核心是信息,不论是对旅游管理部门、对旅游企业,或是对旅游者而言,有效的获取旅游信息,都显得特别重要.旅游管理系统将使旅游相关信息管理工作规范化、信息化、程序化,提供旅游景点、旅游线路,旅游新闻等服务本文以jsp…
阅读更多...
ubuntu18.0.4安装gradio踩坑记

ubuntu18.0.4安装gradio踩坑记

Collecting pandas (from gradio) Downloading http://mirrors.cloud.aliyuncs.com/pypi/packages/c3/e2/00cacecafbab071c787019f00ad84ca3185952f6bb9bca9550ed83870d4d/pandas-1.1.5-cp36-cp36m-manylinux1_x86_64.whl (9.5MB) 100% |████████████████…
阅读更多...
Python学习打卡：day14

Python学习打卡：day14

day14 笔记来源于&#xff1a;黑马程序员python教程&#xff0c;8天python从入门到精通&#xff0c;学python看这套就够了 目录 day14102、封装三大特性对用户隐藏的属性和行为私有成员使用私有成员 103、封装的课后习题104、继承单继承多继承 105、复写父类成员和调用父类成…
阅读更多...
神经网络学习3-卷积层

神经网络学习3-卷积层

膨胀卷积&#xff0c;也被称为空洞卷积或扩张卷积&#xff0c;是一种特殊的卷积运算&#xff0c;它在标准卷积的基础上引入了一个额外的超参数&#xff0c;即膨胀率&#xff08;dilation rate&#xff09;。这个超参数决定了在卷积核的元素之间插入多少额外的空间。通过这种方式…
阅读更多...
图解注意力

图解注意力

图解注意力 Part #2: The Illustrated Self-Attention 在文章前面的部分&#xff0c;我们展示了这张图片来展示自注意力被应用于正在处理单词"it"的一层中&#xff1a; 在本节中&#xff0c;我们将看看这是如何完成的。请注意&#xff0c;我们将以一种试图理解单…
阅读更多...
Linux系统编程--软/硬连接

Linux系统编程--软/硬连接

真正找到磁盘上文件的并不是文件名&#xff0c;而是inode。 其实在linux中可以让多个文件名对应于同一个inode。 命令&#xff1a; 软连接&#xff1a;ln -s 原文件名 新文件名 硬链接&#xff1a;ln 原文件名 新文件名 删除链接文件&#xff1a;unlink 文件名执行上面两条命令…
阅读更多...
最新文章

Copyright @ 2022~2023