算法 —— 高精度

目录

加法高精度

两个正整数相加

两个正小数相加

两正数相加

减法高精度

两个正整数相减

两个正小数相减

两正数相减

加减法总结

 乘法高精度

两个正整数相乘

两个正小数相乘

乘法总结

加法高精度

题目来源洛谷：P1601 A+B Problem（高精）

高精度：顾名思义，就是在很大的位数情况下进行运算，其基本思想就是用数组进行模拟加法进位，最后遍历数组输出。可以看到提示的a，b最大值达到10^18，而内置类型long long能接受数据的最大值在10^19，题目目的就是为了不让你内置类型来接收数据。

两个正整数相加

我们可以使用字符串来模拟高精度运算，本题要求很少：只需要正整数相加即可，以 83 + 2047 为例模拟一下加法过程，我们可以看一下下图：

按照加法原则，个位与个位相加，十位与十位相加……注意相加的过程中要加上前一位的进位，注意最高位相加后要看进位d是否为0，代码如下：

// 整数部分 // 全是正数
string add_int(string a, string b)
{
	string ret; //存放最终结果
	int d = 0;// 记录进位
	int na = a.size(), nb = b.size();
	int n = max(na, nb);// 统一个数
	// 位数不够前面补0
	if (na > nb)
		for (int i = 1; i <= na - nb; i++)
			b = "0" + b;
	else
		for (int i = 1; i <= nb - na; i++)
			a = "0" + a;
	for (int i = n - 1; i >= 0; i--)
	{
		int tmp = 0, tmp_a = a[i] - '0', tmp_b = b[i] - '0';
		tmp = tmp_a + tmp_b + d; //加前一次的进位
		d = tmp / 10;
		tmp %= 10;
		ret.push_back(tmp + '0');
	}
	if (d != 0)
		ret.push_back(d + '0');
	reverse(ret.begin(), ret.end());
	return ret;
}

两个正小数相加

 根据此题，我又试着把大于0的小数相加设计了出来，这样使得原本加法更加完善，可以对大于等于0的所有数进行加法运算，但是需要注意一点的是，小数部分靠近小数点的为高位，意味着我们要在数字后面补0，以 0.99 和 0.4721 为例子，看以下图示：

根据上图可以用代码将其实现：

// 小数部分  // 全是正数
string add_float(string a, string b)
{
	string ret;
	int d = 0;// 记录进位
	int na = a.size(), nb = b.size();
	int n = max(na, nb);// 统一个数
	// 位数不够后面补0
	if (na > nb)
		for (int i = 1; i <= na - nb; i++)
			b = b + "0";
	else
		for (int i = 1; i <= nb - na; i++)
			a = a + "0";
	for (int i = n - 1; i >= 0; i--)
	{
		int tmp = 0, tmp_a = a[i] - '0', tmp_b = b[i] - '0';
		tmp = tmp_a + tmp_b + d; //加前一次的进位
		d = tmp / 10;
		tmp %= 10;
		ret.push_back(tmp + '0');
	}
	if (d != 0)// 说明要进位到整数
		ret.push_back('x'); 
	reverse(ret.begin(), ret.end());//前导x说明要整数部分+1
	return ret;
}

两正数相加

通过上述两个函数合并可以试着实现正数的加法，这里说一下我的思路：

  1. 找到两个字符串中的小数点
  2. 将字符串分为两个子串：左半部分为正整数子串，右半部分为正小数子串
  3. 两个部分分别调用上述函数
  4. 结果合并成一个字符串，该字符串为最终结果

 为了提高代码的可读性，本蒟蒻在每行代码后面添加了注释，大家可以试着看一下：

bz：本人考虑到小数部分相加刚好为1的情况，那么可以试着不要后面一大串全是0的子串，直接输出整数部分即可，这样更加贴合大家生活中的加法习惯。以下为代码：

// 加法
string add(string a,string b)
{
	auto it_a = a.find('.'), it_b = b.find('.');
	string a_int = a, b_int = b, a_float, b_float; // 默认a b是整数
	if (it_a != -1)// 找到小数点了就要分成两部分
	{
		a_int = a.substr(0, it_a); // 把整数部分裁下来
		a_float = a.substr(it_a + 1, a.size() - it_a); // 把小数部分裁下来
	}
	if(it_b != -1)
	{
		b_int = b.substr(0, it_b);
		b_float = b.substr(it_b + 1, b.size() - it_b); // 同上
	}
	string ad_float = add_float(a_float, b_float);
	if (ad_float[0] == 'x')//看看有没有前导x，有就需要进位
	{
		ad_float = ad_float.substr(1, ad_float.size() - 1); //把前导x舍弃
		a_int = add_int(a_int, "1"); // 小数进位只会加1
	}
	int count = 0;
	for (auto e : ad_float) // 看看结尾是不是全是0
		if (e == '0')
			count++;
	if (count == ad_float.size()) // 说明全是0，ret可以不要了
		ad_float.clear(); //清空
	string ad_int = add_int(a_int, b_int);
	string ret = ad_int;
	if (ad_float.size() != 0) // 说明里面有小数
		ret = ret + "." + ad_float;
	return ret;
}

减法高精度

减法高精度与加法高精度略有不同，其区别在于进位，加法的进位是把进位值给高一级位，而减法进位需要向高一级位借一位（前数比后数小的前提下）

两个正整数相减

减法的难点在于：它不像加法那样可以一位一位顺位相加，在借位的情况下，可能出现越位减一的情况，例如100 - 9，要从百位借位，这样大大增加了难度。

注意以下两个特殊情况：

  1. 两个相同数相减为0
  2. 低位数不够，向高位借1

根据加法的代码，可以考虑在加法的基础上进行修改，并且通过两个正整数的相减可以实现一正一负的加法运算，提高了代码的复用性。看以下一下代码：

// 整数部分 // 全是正数 // 大 - 小
string sub_int(string a, string b)
{
	string ret; // 存放最终结果
	int d = 0;// 记录进位
	int na = a.size(), nb = b.size();
	int n = max(na, nb);// 统一个数
	// 位数不够前面补0
	if (na > nb)
		for (int i = 1; i <= na - nb; i++)
			b = "0" + b;
	else
		for (int i = 1; i <= nb - na; i++)
			a = "0" + a;
	string maxn = a, minn = b; // 重新搞两个字符串（提高可读性）
	for (int i = n - 1; i >= 0; i--)
	{
		int tmp = 0, tmp_max = maxn[i] - '0' + d, tmp_min = minn[i] - '0'; // 进位放初始化
		d = 0;// 注意用完 d 归零
		if (tmp_max < tmp_min) // 借位情况（大数该位不够减小数该位）
		{
			tmp_max += 10; //问前面一位要了一个1
			d = -1;
		}
		tmp = tmp_max - tmp_min;
		ret.push_back(tmp + '0');
	}
	for (int i = n - 1; i >= 1; i--) //一样的数相减全是0删掉（注意留最后一个0）
	{
		if (ret[i] == '0')
			ret.pop_back();
		else
			break;
	}
	reverse(ret.begin(), ret.end());
	return ret;
}

两个正小数相减

正小数相减和相加类似，最后返回的字符串如果要借个位的一位就存放一个x，两函数合并时判断是否有x（需要向个位借一位的情况）即可，代码如下：

// 小数部分 // 全是正数 // 大 - 小
string sub_float(string a, string b)
{
	string ret; // 存放最终结果
	int d = 0;// 记录进位
	int na = a.size(), nb = b.size();
	int n = max(na, nb);// 统一个数
	// 位数不够后面补0
	if (na > nb)
		for (int i = 1; i <= na - nb; i++)
			b = b + "0";
	else
		for (int i = 1; i <= nb - na; i++)
			a = a + "0";
	string maxn = a, minn = b; // 重新搞两个字符串（提高可读性）
	for (int i = n - 1; i >= 0; i--)
	{
		int tmp = 0, tmp_max = maxn[i] - '0' + d, tmp_min = minn[i] - '0'; // 进位放初始化
		d = 0;// 注意用完 d 归零
		if (tmp_max < tmp_min) // 借位情况（大数该位不够减小数该位）
		{
			tmp_max += 10; //问前面一位要了一个1
			d = -1;
		}
		tmp = tmp_max - tmp_min;
		ret.push_back(tmp + '0');
	} 
	if (d == -1)// 整数部分也要减1
		ret.push_back('x');
	reverse(ret.begin(), ret.end());
	return ret;
}

两正数相减

与加法相同，裁剪小数和整数两部分字符串依次调用各自的函数即可，代码如下：

// 减法  // 默认 大 - 小
string sub(string a, string b)
{
	auto it_a = a.find('.'), it_b = b.find('.');
	string a_int = a, b_int = b, a_float, b_float; // 默认a b是整数
	if (it_a != -1)// 找到小数点了就要分成两部分
	{
		a_int = a.substr(0, it_a); // 把整数部分裁下来
		a_float = a.substr(it_a + 1, a.size() - it_a); // 把小数部分裁下来
	}
	if (it_b != -1)
	{
		b_int = b.substr(0, it_b);
		b_float = b.substr(it_b + 1, b.size() - it_b); // 同上
	}
	string su_float = sub_float(a_float, b_float);
	if (su_float[0] == 'x')//看看有没有前导x，有就需要借位
	{
		su_float = su_float.substr(1, su_float.size() - 1); //把前导x舍弃
		a_int = sub_int(a_int, "1"); // 小数进位只会加1
	}
	int count = 0;
	for (auto e : su_float) // 看看结尾是不是全是0
		if (e == '0')
			count++;
	if (count == su_float.size()) // 说明全是0，ret可以不要了
		su_float.clear(); //清空
	string su_int = sub_int(a_int, b_int);
	string ret = su_int;
	if (su_float.size() != 0) // 说明里面有小数
		ret = ret + "." + su_float;
	return ret;
}

加减法总结

 通过减法可以利用该函数实现加法中的正数加负数，当然在面对小减大的情况时，需要通过一个比较函数来判断两数的绝对值大小，处理完之和直接在最终结果的字符串前头插一个” - " 即可，加减法无非以下几种情况：

                                                         加减法所有可能情况
式子形式大小比较结果大小
正数a + 正数b两者都大于0大于0
正数a + 负数b| a | >= | b |大于等于0
正数a + 负数b| a | < | b |小于0
负数a + 负数b两者都小于0小于0

正数a - 正数b

| a | >= | b |大于等于0
正数a - 负数ba >= 0    b < 0大于0
负数a - 正数ba < 0    b >= 0小于0
负数a - 负数b| a | >= | b |小于0

负数a - 负数b

| a | < | b |大于0

 以下代码为绝对值化处理和比较函数的内容，大家可以根据本蒟蒻上述代码尝试其他情况的代码编写。

// 绝对值化
if (a[0] == '-')
a = a.substr(1, a.size() - 1);
if (b[0] == '-')
b = b.substr(1, b.size() - 1);

// 比较函数
bool my_cmp(string a, string b) // 补0 且 绝对值化后进行比较
{
	// 默认 a > b
	for (int i = 0; i < a.size(); i++)
		if (a[i] < b[i])
			return false;
	return true;
}

 乘法高精度

本题来自洛谷题库：P1303 A*B Problem，相比加减法的高精度，乘法的高精度相对麻烦一些，但是归根结底还是运用字符串来实现位数的变化，其主要区别在于进位，加减法的进位只会是1，但是乘法的进位可以达到8（9 * 9 = 81），本文不探讨除法的高精度，个人认为除法的高精度不常见，接下来我们试着解决上题。

注意特殊情况：0和任何数相乘都为0！！！

两个正整数相乘

以 679 x 58 为例，看以下图片如何模拟该乘法过程：

 可以看到乘法内部实际为多个加法操作的求和，我们可以在上面的加法操作上进行修改：

// 整数部分 // 全是正数
string mul_int(string a, string b)
{
	if (a == "0" || b == "0")//处理特例
		return "0";
	string ret = "0"; // 存放最终结果
	int d = 0;// 记录进位
	string longer = a, shorter = b; // 假设法
	if (a.size() < b.size())
		swap(longer, shorter);
	int n = shorter.size(); // 乘的次数
	reverse(longer.begin(), longer.end()); reverse(shorter.begin(), shorter.end()); //逆置后位数顺序
	for (int i = 0; i < n; i++)
	{
		string str; // 临时存放数据
		for (int j = 0; j < longer.size(); j++)
		{
			int tmp = 0, tmp_longer = longer[j] - '0', tmp_shorter = shorter[i] - '0';
			tmp = tmp_longer * tmp_shorter + d; //加上进位
			d = tmp / 10;
			tmp %= 10;
			str.push_back(tmp + '0');
		}
		if (d != 0) //比原数多一位
			str.push_back(d + '0');
		reverse(str.begin(), str.end());
		for (int z = 1; z <= i; z++) // 从十位开始就要后面补0
			str.push_back('0');
		ret = add_int(ret, str);// 调用上述两整数相加运算
		d = 0; // 用完复位
	}
	return ret;
}

两个正小数相乘

小数相乘可以利用上面的正整数相乘，回想一下小学时期如何解决小数相乘问题的？

本蒟蒻总结了以下几个步骤：

  1. 计算两数小数点后几位之和
  2. 小数前面的0全部去掉
  3. 整数相乘
  4. 添加小数点

光看文字可能有些抽象，我们来看图片：

 根据上面图片是不是思路更加清晰了呢？下面我们来实现代码操作：

// 小数部分 // 全是正数
string mul(string a, string b)
{
	if (a == "0" || b == "0")//处理特例
		return "0";
	auto it_a = a.find('.'), it_b = b.find('.');
	string a_int = a, b_int = b, a_float, b_float; // 默认a b是整数
	if (it_a != -1)// 找到小数点了就要分成两部分
	{
		a_int = a.substr(0, it_a); // 把整数部分裁下来
		a_float = a.substr(it_a + 1, a.size() - it_a); // 把小数部分裁下来
	}
	if (it_b != -1)
	{
		b_int = b.substr(0, it_b);
		b_float = b.substr(it_b + 1, b.size() - it_b); // 同上
	}
	int n = a_float.size() + b_float.size();
	if (a_int == "0")
		a_int.clear();
	if (b_int == "0")
		b_int.clear();
	a = a_int + a_float, b = b_int + b_float; // 拼起来
	string ret = mul_int(a, b); int nret = ret.size();
	if (n >= nret)// 不够还要补0
	{
		//为什么不用insert？ 如果要头插大量0，insert时间复杂度太高
		reverse(ret.begin(), ret.end()); //逆置尾插0
		for (int i = 0; i <= n - nret; i++)
			ret.push_back('0');
		ret.insert(n, 1, '.'); //这里的insert只要挪一个0就行  好好思考为什么
		reverse(ret.begin(), ret.end());
	}
	else
		ret.insert(nret - n, 1, '.');
	return ret;
}

上述代码我将含有小数和整数的数字合并在一起，该函数可以处理各种正数相乘。

乘法总结

乘法一共有以下几种情况，需要注意以下两点：

  1. 两个小数相乘不会向整数位进位
  2. 0乘任何数都为0

乘法需要考虑以下所有情况： 

                                                     乘法所有可能情况
式子形式大小比较结果大小
0 x 任何数0
正数a x 正数b两者都大于0大于0
正数a x 负数ba > 0   b < 0小于0
负数a x 负数ba < 0   b < 0大于0
整数a x 小数b两者都大于0（相当于除法）大于0
小数a x 小数b两者都大于0大于0且小于1

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

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

相关文章

医疗器械FDA |FDA网络安全测试具体内容

医疗器械FDA |FDA网络安全测试具体内容

医疗器械FDA网络安全测试的具体内容涵盖了多个方面&#xff0c;以确保医疗器械在网络环境中的安全性和合规性。以下是根据权威来源归纳的FDA网络安全测试的具体内容&#xff1a; 一、技术文件审查 网络安全计划&#xff1a;制造商需要提交网络安全计划&#xff0c;详细描述产…
阅读更多...
循环结构(一)——for语句【互三互三】

循环结构(一)——for语句【互三互三】

文章目录 &#x1f341; 引言 &#x1f341; 一、语句格式 &#x1f341; 二、语句执行过程 &#x1f341; 三、语句格式举例 &#x1f341;四、例题 &#x1f449;【例1】 &#x1f680;示例代码: &#x1f449;【例2】 【方法1】 &#x1f680;示例代码: 【方法2】…
阅读更多...
转盘输入法

转盘输入法

简介 转盘输入法&#xff0c;给你的聊天加点新意。它不用常见的九宫格或全键盘&#xff0c;而是把字母摆在圆盘上&#xff0c;一滑一滑&#xff0c;字就出来了&#xff0c;新鲜又直接。 触摸屏版本 当触屏输入法启动时&#xff0c;与200X年流行的按键手机相比&#xff0c;两者…
阅读更多...
Profibus_DP转ModbusTCP网关模块连马保与上位机通讯

Profibus_DP转ModbusTCP网关模块连马保与上位机通讯

Profibus转ModbusTCP网关模块&#xff08;XD-ETHPB20&#xff09;广泛应用于工业自动化领域。例如&#xff0c;可以将Profibus网络中的传感器数据转换为ModbusTCP协议&#xff0c;实现数据的实时监控和远程控制。本文介绍了如何利用Profibus转ModbusTCP网关&#xff08;XD-ETHP…
阅读更多...
【安装记录】：安装破解 ideaIU-2024.1.4

【安装记录】：安装破解 ideaIU-2024.1.4

1、官网下载安装包&#xff1a; https://www.jetbrains.com/idea/download/?sectionwindows 2、按照下图操作&#xff1a; 然后&#xff0c;自定义重启即可 3、破解参考这篇文章&#xff1a;https://www.exception.site/article/1727
阅读更多...
java版的上门家政系统和PHP版的上门家政有什么区别？

java版的上门家政系统和PHP版的上门家政有什么区别？

Java版的上门家政系统和PHP版的上门家政系统主要在以下几个方面存在区别&#xff1a; 1. 开发语言和特性 Java版&#xff1a;基于Java语言开发&#xff0c;Java是一种编译型语言&#xff0c;具有面向对象、跨平台、高性能等特点。Java代码在编写后需要通过Java虚拟机&#xff…
阅读更多...
九盾安防：如何调控叉车限速器的报警速度呢

九盾安防：如何调控叉车限速器的报警速度呢

在繁忙的物流仓储和制造业环境中&#xff0c;叉车是不可或缺的搬运设备。然而&#xff0c;其高速行驶也带来了潜在的安全隐患。为了确保作业人员和货物的安全&#xff0c;又车限速器的设置显得尤为关键。那么&#xff0c;如何调控叉车限速器的报警速度呢? 叉车限速器的速度调整…
阅读更多...
Goland 通道

Goland 通道

channel通道 目录 channel通道 channel介绍 channel基本使用 有缓存通道和无缓存通道的区别 通道的初始化&#xff0c;写入数据到通道&#xff0c;从通道读取数据及基本的注意事项 channel的关闭和遍历 channel的关闭 为什么关闭 如何优雅地关闭通道 channel的遍历 chan…
阅读更多...
STM32智能仓储管理系统教程

STM32智能仓储管理系统教程

目录 引言环境准备晶智能仓储管理系统基础代码实现&#xff1a;实现智能仓储管理系统 4.1 数据采集模块 4.2 数据处理与决策模块 4.3 通信与网络系统实现 4.4 用户界面与数据可视化应用场景&#xff1a;仓储管理与优化问题解决方案与优化收尾与总结 1. 引言 智能仓储管理系统…
阅读更多...
通过git将文件push到github 远程仓库

通过git将文件push到github 远程仓库

1.先git clone 代码地址 git clone htttp://github.com/用户名/test.git 2. 添加文件 例如&#xff1a;touch 1.txt 3.将文件添加到暂存区 git add 1.txt 4.提交 git commit -m "commit 1.txt" 5.与远程仓库建立关联 git remote add 远程仓库名 远程仓库…
阅读更多...
uniapp内置组件scroll-view案例解析

uniapp内置组件scroll-view案例解析

参考资料 文档地址&#xff1a;https://uniapp.dcloud.net.cn/component/scroll-view.html 官方给的完整代码 <script>export default {data() {return {scrollTop: 0,old: {scrollTop: 0}}},methods: {upper: function(e) {console.log(e)},lower: function(e) {cons…
阅读更多...
computed计算属性用法及方法对比

computed计算属性用法及方法对比

模板中的插值表达式虽然方便&#xff0c;但当要写复杂逻辑时就会变得臃肿&#xff0c;难以维护&#xff0c;遇上复杂逻辑时&#xff0c;推荐使用计算属性来描述以响应式状态的复杂逻辑。这里我们做个对比&#xff0c;先用表达式的方法进行计算&#xff0c;先把页面写好&#xf…
阅读更多...
centos单机配置多个内网IP地址

centos单机配置多个内网IP地址

centos单机配置多个内网IP地址 引配置1. 查看当前网络IP配置2. 打开网络配置目录3. 设置静态IP4. 编辑ifcfg-eno1:15. 重启网络配置 引 同一个局域网&#xff0c;但是对接的多个子系统使用了不同的网段&#xff0c;如一个系统主机IP地址是192.168.10.1&#xff0c;另一个系统主…
阅读更多...
昇思25天学习打卡营第8天|模型权重保存与加载

昇思25天学习打卡营第8天|模型权重保存与加载

打卡 目录 打卡 模型的两种保存形式 Checkpoint 中间表示IR 模型保存与加载 模型权重保存-例1 模型权重加载-例1 模型权重保存-例2 模型权重加载-例2 模型权重文件的空间占用计算-例 模型的两种保存形式 Checkpoint 权重参数文件 中间表示IR 中间表示&#xff08;…
阅读更多...
罗技K380无线键盘及鼠标：智慧互联，一触即通

罗技K380无线键盘及鼠标：智慧互联，一触即通

目录 1. 背景2. K380无线键盘连接电脑2.1 键盘准备工作2.2 电脑配置键盘的连接 3. 无线鼠标的连接3.1 鼠标准备工作3.2 电脑配置鼠标的连接 1. 背景 有一阵子经常使用 ipad&#xff0c;但是对于我这个习惯于键盘打字的人来说&#xff0c;慢慢在 ipad 上打字&#xff0c;实在是…
阅读更多...
【人工智能】-- 迁移学习

【人工智能】-- 迁移学习

个人主页&#xff1a;欢迎来到 Papicatch的博客 课设专栏 &#xff1a;学生成绩管理系统 专业知识专栏&#xff1a; 专业知识 文章目录 &#x1f349;引言 &#x1f349;迁移学习 &#x1f348;基本概念 &#x1f34d;定义 &#x1f34c;归纳迁移学习&#xff08;Induct…
阅读更多...
jenkins系列-01.docker安装jenkins

jenkins系列-01.docker安装jenkins

进入官网&#xff1a;https://www.jenkins.io/ 使用LONG term support版本&#xff1a;2.387.1 docker pull jenkins/jenkins:2.387.1-lts 拉取镜像&#xff1a; 编写docker-compose文件&#xff1a; 启动jenkins: 查看启动日志&#xff1a; 默认生成的密码&#xff1a;…
阅读更多...
初阶数据结构速成

初阶数据结构速成

本篇文章算是对初阶数据结构的总结&#xff0c;内容较多&#xff0c;请耐心观看 基础概念部分 顺序表 线性表&#xff08; linear list &#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构&#xff0c;常⻅的线性表&#xff1a;…
阅读更多...
从概念到完成：Midjourney——设计思维与AI技术的完美结合

从概念到完成：Midjourney——设计思维与AI技术的完美结合

文章目录 本文来自 Python学研大本营 作者 学研君 去年 AI 爆火的时候&#xff0c;学研君也赶时髦用上了 Midjourney。平时用它生成图片&#xff0c;感觉生成的图片好看&#xff0c;比上网四处找图更省时省事&#xff0c;更合心意&#xff0c;还不用担心版权问题。 给大家看一下…
阅读更多...
Vue3 引入Vanta.js使用

Vue3 引入Vanta.js使用

能搜到这篇文章 想必一定看过demo效果图了吧 示例 Vanta.js - Animated 3D Backgrounds For Your Website (vantajs.com) 1. 引入 在根目录 index.html中引入依赖 <script src"https://cdnjs.cloudflare.com/ajax/libs/three.js/r134/three.min.js"></sc…
阅读更多...
最新文章

Copyright @ 2022~2023