蓝桥杯备赛 day 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/329408.html

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

相关文章

C#中对浮点数NaN，PositiveInfinity，NegativeInfinity的特殊处理

C#中对浮点数NaN，PositiveInfinity，NegativeInfinity的特殊处理

NAN NAN 整体意思为Not a Number 不是一个数&#xff0c; NaN&#xff08;Not a Number&#xff0c;非数&#xff09;是计算机科学中数值数据类型的一类值&#xff0c;表示未定义或不可表示的值。常在浮点数运算中使用。首次引入NaN的是1985年的IEEE 754浮点数标准。 EEE 75…
阅读更多...
Linux Mii management/mdio子系统分析之六 fixed-mii_bus分析（mac2mac分析）

Linux Mii management/mdio子系统分析之六 fixed-mii_bus分析（mac2mac分析）

&#xff08;转载&#xff09;原文链接&#xff1a;[https://blog.csdn.net/u014044624/article/details/130674908] (https://blog.csdn.net/u014044624/article/details/130674908) 前面几章我们介绍了MDIO模块的大部分内容&#xff0c;针对mii_bus、mdio_bus、phy_device、p…
阅读更多...
学习鸿蒙先解决这几个是关键问题~

学习鸿蒙先解决这几个是关键问题~

HarmonyOS 是最近最火的操作系统&#xff0c;HarmonyOS 宣布删除 Android 代码之后&#xff0c;正式向世界上第三大操作系统有迈进了一步&#xff0c;HarmonyOS 前期为了完成从 Android 到 HarmonyOS 的过渡&#xff0c;在设计之初 HarmonyOS 采用了双框架架构设计。 从图中可以…
阅读更多...
【栈】【字符串和int类型转化】Leetcode 150 逆波兰表达式求值

【栈】【字符串和int类型转化】Leetcode 150 逆波兰表达式求值

【栈】【字符串和int类型转化】Leetcode 150 逆波兰表达式求值 解法1 栈 ---------------&#x1f388;&#x1f388;题目链接 Leetcode 150 逆波兰表达式求值 &#x1f388;&#x1f388;------------------- 解法1 栈 字符串转化为int类型数据: Integer.parseInt(s) Long.p…
阅读更多...
SpringBoot教程(十五) | SpringBoot集成RabbitMq

SpringBoot教程(十五) | SpringBoot集成RabbitMq

SpringBoot教程(十五) | SpringBoot集成RabbitMq RabbitMq是我们在开发过程中经常会使用的一种消息队列。今天我们来研究研究rabbitMq的使用。 rabbitMq的官网&#xff1a; rabbitmq.com/ rabbitMq的安装这里先略过&#xff0c;因为我尝试了几次都失败了&#xff0c;后面等我…
阅读更多...
FPGA时序分析与时序约束(四)——时序例外约束

FPGA时序分析与时序约束(四)——时序例外约束

目录 一、时序例外约束 1.1 为什么需要时序例外约束 1.2 时序例外约束分类 二、多周期约束 2.1 多周期约束语法 2.2 同频同相时钟的多周期约束 2.3 同频异相时钟的多周期约束 2.4 慢时钟域到快时钟域的多周期约束 2.5 快时钟域到慢时钟域的多周期约束 三、虚假路径约…
阅读更多...
网站SEO优化方案

网站SEO优化方案

1&#xff0c;去各类搜索引擎里面&#xff0c;注册你的站点 解决方案&#xff1a;注册地址&#xff1a;https://seo.chinaz.com/chinaz.com 2&#xff0c;网站地址使用 https 会增加搜索排名 解决方案&#xff1a;https:www.xxx.com 3&#xff0c;官网每个页面的 meta 里面&a…
阅读更多...
牛客周赛 Round 10 解题报告 | 珂学家 | 三分模板 + 计数DFS + 回文中心扩展

牛客周赛 Round 10 解题报告 | 珂学家 | 三分模板 + 计数DFS + 回文中心扩展

前言 整体评价 T2真是一个折磨人的小妖精&#xff0c;写了两版DFS&#xff0c;第二版计数DFS才过。T3是三分模板&#xff0c;感觉也可以求导数。T4的数据规模才n1000&#xff0c;因此中心扩展的 O ( n 2 ) O(n^2) O(n2)当仁不让。 A. 游游的最长稳定子数组 滑窗经典题 从某个…
阅读更多...
78、avx2 数据 load/store 向量化操作介绍

78、avx2 数据 load/store 向量化操作介绍

向量寄存器和一个最简单的寄存器-内存的存储器模型，查看上一节。 本节基于整个内存模型，介绍一下如何使用 avx2 向量指令集，来完成数据从内存到寄存器中的交互的。 load 操作 在改内存模型下，load 操作指将数据从内存中加载到寄存器中。 使用 C++ 代码实现如下： float…
阅读更多...
REVIT二次开发修改轴网

REVIT二次开发修改轴网

REVIT二次开发修改轴网 步骤1 步骤2 步骤3 功能实现在这 using System; using System.Collections.Generic; using System.Linq; using
阅读更多...
【实操】基于 GitHub Pages + Hexo 搭建个人博客

【实操】基于 GitHub Pages + Hexo 搭建个人博客

《开发工具系列》 【实操】基于 GitHub Pages Hexo 搭建个人博客 一、引言二、接入 Node.js2.1 下载并安装 Node.js2.2 环境变量配置 三、接入 Git3.1 下载并安装 Git3.2 环境变量配置 四、接入 Hexo4.1 安装 Hexo4.2 建站4.3 本地启动服务器 五、接入 GitHub Pages5.1 初识 G…
阅读更多...
大模型学习与实践笔记（七）

大模型学习与实践笔记（七）

一、环境配置 1.平台&#xff1a; Ubuntu Anaconda CUDA/CUDNN 8GB nvidia显卡 2.安装 # 构建虚拟环境 conda create --name xtuner0.1.9 python3.10 -y # 拉取 0.1.9 的版本源码 git clone -b v0.1.9 https://github.com/InternLM/xtuner# 从源码安装 XTuner pip insta…
阅读更多...
【Proteus仿真】【Arduino单片机】汽车车窗除霜系统设计

【Proteus仿真】【Arduino单片机】汽车车窗除霜系统设计

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用LCD1602显示模块、光线传感器、DS18B20温度传感器、PCF8691 ADC模块、继电器加热模块等。 主要功能&#xff1a; 系统运行后&#xff0c;LCD…
阅读更多...
常考SQL

常考SQL

1 思维导图 2 题目 mysql8版本 1. 连续问题♥♥♥ 问题描述&#xff1a;如下数据为蚂蚁森林中用户领取的减少碳排放量&#xff0c;找出连续3天及以上减少碳排量在100以上的用户。 iddtlowcarbon10012021-12-1212310022021-12-124510012021-12-134310012021-12-134510012021…
阅读更多...
pyqtgraph绘图类

pyqtgraph绘图类

pyqtgraph绘图类 pyqtgraph绘图有四种方法: 方法描述pyqtgraph.plot()创建一个新的QWindow用来绘制数据PlotWidget.plot()在已存在的QWidget上绘制数据PlotItem.plot()在已存在的QWidget上绘制数据GraphicsLayout.addPlot()在网格布局中添加一个绘图 上面四个方法都接收同样…
阅读更多...
Python爬虫实战：IP代理池助你突破限制，高效采集数据

Python爬虫实战：IP代理池助你突破限制，高效采集数据

当今互联网环境中&#xff0c;为了应对反爬虫、匿名访问或绕过某些地域限制等需求&#xff0c;IP代理池成为了一种常用的解决方案。IP代理池是一个包含多个可用代理IP地址的集合&#xff0c;可以通过该代理池随机选择可用IP地址来进行网络请求。 IP代理池是一组可用的代理IP地址…
阅读更多...
【Maven】008-Maven 私服搭建与使用

【Maven】008-Maven 私服搭建与使用

【Maven】008-Maven 私服搭建与使用 文章目录 【Maven】008-Maven 私服搭建与使用一、概述1、简介2、建立私服后依赖查找和下载逻辑第一步&#xff1a;请求本地仓库第二步&#xff1a;请求 Maven 私服第三步&#xff1a;请求外部远程仓库&#xff08;远程中央仓库等&#xff09…
阅读更多...
SpringBoot教程(三) | Spring Boot初体验

SpringBoot教程(三) | Spring Boot初体验

SpringBoot教程(三) | Spring Boot初体验 上篇文章我们创建了SpringBoot 项目&#xff0c;并且进行了简单的启动。整个项目了里其实我们就动了两个文件&#xff0c;一个是pom.xml负责管理springboot的相关依赖&#xff0c;一个是springBoot的启动类。 pom文件中通过starter的…
阅读更多...
Linux环境变量配置全攻略

Linux环境变量配置全攻略

热门IT课程【视频教程】-华为/思科/红帽/oraclehttps://xmws-it.blog.csdn.net/article/details/134398330?spm1001.2014.3001.5502 Linux环境变量配置 在自定义安装软件的时候&#xff0c;经常需要配置环境变量&#xff0c;下面列举出各种对环境变量的配置方法。 下面所有例…
阅读更多...
HTML-鼠标悬浮文案效果

HTML-鼠标悬浮文案效果

文章目录 前言一、 hover属性实现二、title属性 简单实现总结 前言 有时候&#xff0c;我们浏览网站时&#xff0c;鼠标停留在某处后鼠标会提示一些文案。 一、 hover属性实现 HTML 中可以使用 CSS 来实现鼠标悬浮文案效果。 首先&#xff0c;在 HTML 文件中添加需要显示悬浮…
阅读更多...
最新文章

Copyright @ 2022~2023