蓝桥杯备赛 week 3 —— 高精度（C/C++，零基础，配图）

目录

🌈前言：

📁 高精度的概念

📁 高精度加法和其模板

📁 高精度减法和其模板

📁 高精度乘法和其模板

📁 高精度除法和其模板

📁 总结

🌈前言：


        这篇文章主要是准备蓝桥杯竞赛同学所写，为你更好准备蓝桥杯比赛涉及的算法知识点。不知道你是否苦恼于不知算法从何学起，苦恼于网上资料稀少，或者复杂难懂，这篇文章就是帮助这部分同学的。

        下面整理了蓝桥杯考点大纲：
        蓝桥杯考点大纲

        如果你对vecto数组r有兴趣，也可以阅读下面这篇文章，当然没了解vector数组也不影响阅读本篇文章

和C++STL中vector的初次见面，vector常见用法和操作（零基础/小白）-CSDN博客

        上图是大学C组需要掌握的，对于B组的同学也是需要向下掌握的。本文主要是帮助蓝桥杯B/C为主体的大部分同学，所以讲解相对基础。本文是以C++为主要语言，但是C语言的同学也不需要担心，大部分语法是相通的，只不过是加了STL内容一个内容，也是会进行讲解的。

        因为语法特性，变量等原因，对于JAVA，Python同学来说是不需要掌握高精度的。

        同时本文将提供做题模板，方便你在考试中更好的做题，以及日常的刷题。

📁 高精度的概念

        我们用C/C++创建变量时，变量类型是有取值范围的，对于最常用unsigned int来说，它最多有-2147483648 ~ 2147483647,即-(2^31)~(2^31-1），也就是说最多有31位, 那我们想存长度为10^6的数呢，这是我们就不能用C/C++语法规定的变量来存储了，我们就必须用数组来存储。

        总结一下，高精度就是通过数组模拟四则运算来计算长度非常长的数字。

        本文只讲解比较常见的四种高精度算法，如两个高精度数相加，两个高精度数相间，高精度数乘低精度数，高精度数除以低精度数。

        通常来说，高精度灰常大，如10^6，低精度数10000以内。

        对于高精度数这么多位数来说，我们首先想到的是整数数组来存储，可是有一个问题是存储呢是从后往前存储，还是从前往后存储？比如123，下标0是在1的位置，还是3的位置呢？

        如果从1开始那么计算是否方便，很显然这是不方便的，如果感兴趣，可以自己尝试一下。可是对于从3开始存储，一开始我们怎么会知道他有多少位数呢？相信你一定知道数组还有一种叫做字符数组的，我们可以先将字符数字存储在字符数组中，再将字符数字逆序存储成整数数组中进行计算，这样大大减少了运算时进位的难度。（数组从前往后遍历如果遇到进位时，只需要下一个位置的数+1即可）

📁 高精度加法和其模板

        我们首先来看一下，普通的加法怎么计算。

        加法运算就是从个位开始相加，相加大于10就向前进1位，即向前一位+1。前面我们说了，高精度是通过数组来模拟计算的，如下图所示。

        通过上图我们就可以得出模板：

vector<int> add(vector<int> A,vector<int> B)
{
    vector<int> C;
    int t = 0;    //t是进位
    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(t);
    return C;

}

        这里为了更好照顾C语言同学，讲解一下什么是vector<int> , 可以理解为数组，每个元素类型是int，即整数数组。

        .size()可以理解为对数组的操作，求数组元素个数；.push_back()也是同理，向数组C插入元素的。

        整体通读一遍模板代码，先创建数组C存储结果，当然是从个位先开始存储的。t是进位，如果Ai，Bi在i位置上有数，就加到t中，t就是相加结果，如果大于10，保留个位数，向前+1，t%10。

最后判断最大位数相加是否向前进1位，就是判断t，这里t只能取到0或者1。

        以上，我们就对高精度加法模板有了了解，下面我们展示完整代码：

#include <iostream>
#include <vector>

using namespace std;

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(t);
	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 = add(A, B);
	for (int i = C.size() - 1;i >= 0;i--)
		cout << C[i];
	return 0;
}

        如果我们要使用vector数组的话，要引用头文件。

📁 高精度减法和其模板

        ​​​​​​

        A-B，我们要分两种情况，即A>=B,和 A < B；对于第1种情况，我们直接输出A-B即可，对于第二种情况我们输出 - (B - A);

        对于模板，我们只需要确保A>=B即可。

vector<int> sub(vector<int> A,vector<int> B)
{
    vector<int> C;
    int t = 0;        //借位
    for(int i=0;i<A.size();i++)
    {
        t = A[i] + t;
        if(i < B[i])
            t -= B[i];
        C.push_back((t + 10) % 10);
        if(t < 0)
            t = -1;
        else
            t = 0;    
    }
    while(C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}

       (t+10)%10,是为了保证减不开的情况，对于相减大于0的数不影响。

        最后的while循环是为了保证一种情况，例如，127-120，在数组C中存储的是300,最后打印007了，所以我们要将前面两个0删去，当然如果是127-127，是要保留1个0的。

        下面展示完整代码：

        当然，我们下面还写了一个函数check，作用就是判断A是否大于等于B的。

#include <iostream>
#include <vector>

using namespace std;

bool check(vector<int> A, vector<int> B)
{
	if (A.size() > B.size())
		return true;
	for (int i = 0;i < A.size();i++)
		if (A[i] != B[i])
			return A[i] > B[i];
	return true;
}

vector<int> sub(vector<int> A, vector<int> B)
{
	vector<int>	C;
	int t = 0;
	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);
		if (t < 0)
			t = -1;
		else
			t = 0;
	}
	while (C.size() > 1 && C.back() == 0)
		C.pop_back();
	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');
	
	if (check(A, B))
	{
		vector<int> C = sub(A, B);
		for (int i = C.size() - 1;i >= 0;i--)
			cout << C[i];
	}
	else
	{
		vector<int> C = sub(B, A);
		cout << '-';
		for (int i = C.size() - 1;i >= 0;i--)
			cout << C[i];
	}
	return 0;
}

📁 高精度乘法和其模板

        下图便是高精度与低精度整数想乘的运算方式，将每一位数乘低精度数b + 上一位的进位，余数就是这位上的数，进位等于相除的结果。

        得出模板为：

vector<int> mul(vector<int> A, int b)
{
	vector<int> C;
	int t = 0;
	for (int i = A.size() - 1;i >= 0 || t; i--)
	{
		if(i < A.size())
			t += A[i] * b;
		C.push_back(t % 10);
		t /= 10;
	}
	while (C.size() > 1 && C.back() == 0)
		C.pop_back();
	return C;
}

        当然最后还是要保证A*0的话只能有1个0。

        下面展示完整代码：

#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> A, int b)
{
	vector<int> C;
	int t = 0;
	for (int i = A.size() - 1;i >= 0 || t; i--)
	{
		if(i < A.size())
			t += A[i] * b;
		C.push_back(t % 10);
		t /= 10;
	}
	while (C.size() > 1 && C.back() == 0)
		C.pop_back();
	return C;
}

int main()
{
	string a;
	cin >> a;
	int b;
	cin >> b;
	vector<int> A;
	for (int i = a.size() - 1;i >= 0;i--)
		A.push_back(a[i] - '0');

	vector<int> C = mul(A, b);
	for (int i = C.size() - 1;i >= 0;i--)
		cout << C[i];
	return 0;
}

📁 高精度除法和其模板

        除法相对于上面三个有点不同，高精度数A是从最高位开始计算的，我们数组C存储也是从最高位开始存储，但是我们为了和上面保持一致，即输出都是从后往前输出，所以我们最后逆置数组。

        这里为什么从0开始计算呢，是从1开始计算的，上一位的补下来是0，所以1/3=1，余数是1,，依次类推。理解了这里，高精度除法也就懂了。

        下面展示模板：

vector<int> div(vector<int> A, int b, int& r)
{
	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());

	while (C.size() > 1 && C.back() == 0)
		C.pop_back();
	
	return C;
}

        reverse()函数就是将数组元素逆置，其中begin(),end()你可以先简单理解为首元素位置，尾元素位置，将这两个参数传给reverse函数。函数是包含在头文件<algorithm>中

        下面展示完整代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> div(vector<int> A, int b, int& r)
{
	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());

	while (C.size() > 1 && C.back() == 0)
		C.pop_back();
	
	return C;
}

int main()
{
	string a;
	cin >> a;
	int b;
	cin >> b;
	vector<int> A;
	for (int i = a.size() - 1;i >= 0;i--)
		A.push_back(a[i] - '0');

	int r = 0;
	vector<int> C = div(A,b,r);
	for (int i = C.size() - 1;i >= 0;i--)
		cout << C[i];
	cout << endl << r << endl;
	return 0;
}

        

📁 总结

        以上，我们就对高精度在蓝桥杯中的知识点进行了讲解，并针对性的讲解了例题，当然这也只是帮你更好的理解这些算法知识，想要学好算法，还需要不断地刷题练习，这里推荐到洛谷，acwing等网站进行练习，比如你看完了这篇文章，做回了例题习题，就可以上这些网站进行想应的练习。

        如果你有哪里疑惑，欢迎在评论区留言，也欢迎大家指出文中错误。最后，希望大家在评论区积极讨论，点赞，收藏，关注ヾ(✿ﾟ▽ﾟ)ノ

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

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

相关文章

电饼铛行业研究：中国市场规模整体上涨趋势明显

电饼铛行业研究：中国市场规模整体上涨趋势明显

电饼铛是一个烹饪食物的工具&#xff0c;单面或者上下两面同时加热使中间的食物经过高温加热&#xff0c;达到烹煮食物的目的。电饼铛也叫烤饼机&#xff0c;可以灵活进行烤、烙、煎等烹饪方法&#xff0c;有家用小款型和店面使用大款两种。 大型的电饼铛具有自动上下火控温…
阅读更多...
Python基础语法：代码规范、判断语句与循环语句

Python基础语法：代码规范、判断语句与循环语句

目录 一、代码规范 二、判断语句 三、循环语句 总结&#xff1a; Python是一种高级、动态类型的编程语言&#xff0c;其语法清晰、简洁&#xff0c;易于学习。本文将介绍Python基础语法中的代码规范、判断语句和循环语句。 一、代码规范 良好的代码规范可以提高代码的可读…
阅读更多...
谈谈ArrayList和LinkedList的区别

谈谈ArrayList和LinkedList的区别

目录 一、什么是数组 二、ArrayList 三、LinkedList 四、ArrayList和LinkedList的区别 一、什么是数组 在编程中&#xff0c;数组&#xff08;Array&#xff09;是一种用于存储多个相同类型数据元素的数据结构。它是一个有序的集合&#xff0c;其中每个元素都有一个唯一的…
阅读更多...
Windows11操作系统百科

Windows11操作系统百科

简介 Windows 11是由微软公司&#xff08;Microsoft&#xff09;开发的操作系统&#xff0c;应用于计算机和平板电脑等设备 [1]。于2021年6月24日发布 [3]&#xff0c;2021年10月5日发行 [29]。 Windows 11提供了许多创新功能&#xff0c;增加了新版开始菜单和输入逻辑等 [6]…
阅读更多...
Java 字符串 04 练习-用户登录

Java 字符串 04 练习-用户登录

自己写的代码&#xff1a; import java.util.Scanner; public class practice {static String rightUsername "zhangsan";static String rightPassword "123456";public static void main(String[] args) {//读题拆解法//1、定义两个变量&#xff0c;记…
阅读更多...
机器学习--jupyter使用

机器学习--jupyter使用

机器学习–jupyter notebook的使用 Jupyter项目是一个非盈利的开源项目&#xff0c;源于2014年的ipython项目&#xff0c;因为它逐渐发展为支持跨所有编程语言的交互式数据科学和科学计算 Jupyter Notebook&#xff0c;原名IPython Notbook&#xff0c;是IPython的加强网页版…
阅读更多...
NAS with RL（使用强化学习进行神经网络架构搜索，基于pytorch框架）

NAS with RL（使用强化学习进行神经网络架构搜索，基于pytorch框架）

目录 一、 原代码 二、 代码学习(修改后并加上详细注释&#xff09; 1. 控制器 2. NASModel 3. 初始化及训练过程 3.1 主要参数的初始化 3.2 数据集的准备与加载 3.3 搜索空间 3.4 训练、参数更新 4. 对搜索空间、搜索策略、性能评估策略的认识 4.1 搜索空间&#xf…
阅读更多...
PicGo+雨云ROS搭建自己的图床，可配合Typora使用

PicGo+雨云ROS搭建自己的图床，可配合Typora使用

本文将手把手带你使用PicGo雨云对象存储ROS(Rain Object Storage)搭建自己专属的免费图床&#xff0c;并且可以配合Typora使用。 雨云对象存储服务介绍和使用教程&#xff1a;https://forum.rainyun.com/t/topic/5573 目前雨云对象存储是公测阶段&#xff0c;暂时是免费的。 …
阅读更多...
杰卡德距离（Jaccard Distance）

杰卡德距离（Jaccard Distance）

杰卡德距离&#xff08;Jaccard Distance&#xff09;&#xff0c;是用于衡量两个集合差异性的一种指标&#xff0c;它是杰卡德相似系数的补集&#xff0c;可以用来区分集合&#xff08;如知识图谱&#xff09;。 杰卡德相似系数 杰卡德相似系数&#xff08;Jaccard similari…
阅读更多...
01-echarts如何绘制三维折线图

01-echarts如何绘制三维折线图

echarts如何绘制三维折线图 一、相关依赖包1、下载依赖2、引入依赖 二、创建图表盒子1、创建盒子2、定义数据3、编写方法1、初始化盒子2、设置配置项3、修改数据格式4、设置颜色数组4、设置name数组5、设置线三维和点三维6、添加配置项7、设置图表自适应 4、调用方法 三、整体代…
阅读更多...
【脑电信号处理与特征提取】P2-夏晓磊：脑电的神经起源与测量

【脑电信号处理与特征提取】P2-夏晓磊：脑电的神经起源与测量

夏晓磊&#xff1a;脑电的神经起源与测量 专业术语 electroencephalography(EEG) 脑电图 Excitatory Postsynaptic Potential(EPSP) 兴奋性突触后电位 Electrocorticography(ECoG) 皮层脑电图 什么是脑电/脑电图&#xff08;EEG&#xff09;&#xff1f; Electroencephalograp…
阅读更多...
C++ 关于静态成员对象、函数学习整理：

C++ 关于静态成员对象、函数学习整理：

类的静态成员为类创建的所有对象所共有的成员&#xff0c;不单独属于某一对象&#xff0c;而属于整个类&#xff0c;而静态成员分为静态成员变量、静态成员函数。 静态成员变量&#xff08;静态数据成员&#xff09;&#xff1a; 引入及解决问题的优势&#xff1a; 类创建了…
阅读更多...
Java中SimpleDateFormat时YYYY与yyyy以及HH和hh的区别注意踩坑

Java中SimpleDateFormat时YYYY与yyyy以及HH和hh的区别注意踩坑

场景 Java开发手册中为什么要求SimpleDateFormat时用y表示年&#xff0c;而不能用Y&#xff1a; Java开发手册中为什么要求SimpleDateFormat时用y表示年&#xff0c;而不能用Y_simpledateformat 怎么确定y就是年-CSDN博客 在使用SimpleDateFormat在获取当前日期时因使用了YY…
阅读更多...
[极客大挑战 2019]Secret File1

[极客大挑战 2019]Secret File1

上来就说看不到&#xff0c;先看看源码&#xff0c;发现./Archive_room.php 点secret直接跳到了end&#xff0c;抓包看看&#xff0c;找到了secr3t.php 过滤了很少的关键词&#xff0c;提示flag在flag.php&#xff0c;过去发现还是看不到 尝试用php伪协议读取flag.php的源码 …
阅读更多...
creo草绘3个实例学习笔记

creo草绘3个实例学习笔记

creo草绘3个实例 文章目录 creo草绘3个实例草绘01草绘02草绘03 草绘01 草绘02 草绘03
阅读更多...
Web08--JavaScript高级

Web08--JavaScript高级

1、BOM对象 BOM&#xff1a;browser object model 浏览器对象模型 BOM对象包括window对象、screen对象、history对象、location对象、navigator对象。 1.1 window对象 所有的浏览器都支持window对象。它表示的浏览器窗口 window对象是js中的顶层对象&#xff0c;所有的j…
阅读更多...
直播引流到微信，如何才算合规？-数灵通

直播引流到微信，如何才算合规？-数灵通

抖音直播如今越来越受到大众的关注&#xff0c;许多朋友都会准时守在直播前。不少人被直播带来的收益所吸引&#xff0c;纷纷加入到创作者的行列中。直播间巨大的流量背后&#xff0c;蕴藏着无法估量的经济效益和赚钱机会。 确实有人考虑将部分抖音直播的流量引入微信&#xff…
阅读更多...
TS基础知识点快速回顾(上)

TS基础知识点快速回顾(上)

基础介绍 什么是 TypeScript&#xff1f; TypeScript&#xff0c;简称 ts&#xff0c;是微软开发的一种静态的编程语言&#xff0c;它是 JavaScript 的超集。 那么它有什么特别之处呢? js 有的 ts 都有&#xff0c;所有js 代码都可以在 ts 里面运行。ts 支持类型支持&#…
阅读更多...
退货通知单下推销售退货单，无法下推问题排查

退货通知单下推销售退货单，无法下推问题排查

文章目录 退货通知单下推销售退货单&#xff0c;无法下推问题排查报错界面排查原因 退货通知单下推销售退货单&#xff0c;无法下推问题排查 报错界面 排查 检验单已做。 原因 合格未勾选判退。
阅读更多...
antv/g6绘制数据流向图

antv/g6绘制数据流向图

antv/g6绘制数据流向图 前言接口模拟数据htmlts页面效果 前言 在业务开发中需要绘制数据流向图&#xff0c;由于echarts关系图的限制以及需求的特殊要求&#xff0c;转而使用antv/g6实现&#xff0c;本文以代码的方式实现数据流向需求以及节点分组,版本"antv/g6": “…
阅读更多...
最新文章

Copyright @ 2022~2023