蓝桥杯备赛系列 高精度 acwing版

                                        前言

hello，好久不见。元旦玩过后该收心了，我也倒计时一下蓝桥杯考试时间，大家一起复习，一起登顶。今天讲解高精度算法。

这个算法其实是给学c++同学讲的，因为python自带高精度所以不需要，且我讲到所有内容都是c++版本，今年就要报考c++，今年学好了Java可以上Java内容。

不多bb了上正文

                                        正文

         先介绍一下为什么要用高精度。

  1. int：通常，int 类型的大小是依赖于特定平台的，常见的有 16 位（2 字节）、32 位（4 字节）和 64 位（8 字节）等。在某些平台上，int 可能只有 16 位，能够存储的最大值是 32767；而在其他平台上，int 可能有 32 位或 64 位，能够存储的最大值分别是 2147483647 和 9223372036854775807。
  2. long long：long long 类型通常至少有 64 位，并且能够存储的最大值是 9223372036854775807。实际上，long long 的大小和能够存储的最大值也是依赖于特定平台和编译器的。

所以由此看来如果输入的数过大int 和longlong类型都会爆掉，那我要是硬使用

会怎么样呢，下面这个照片给大家展示一下。

 很明显是不行的，所以要引入高精度这个算法。

高精度如何存数字呢，很明显就是数组。

高精度加法
主要思想：用字符数组进行接收数字，将数字逐一逆序存储到数组中，对应位置依次相加。
在此之前，我们回忆一下小学加法的做法：
1.对应位置相加
2.逢十进一

（1）8+9=17,逢十进一，17%10得到个位存储的数字为7。
（2）4+5+1=10,逢十进一，10%10得到个位存储的数字为0。
（3）两个数字百位都没有数字了，所以百位存储的数字就为1。
（4）得到答案107。

高精度加法步骤：
(1):字符数组存储大数字
(2):逆序插入整形数组
(3):对应位置数字相加，并进行%10运算存储到数组中，逢十进一
(4):将数组数字逆序输出

#include <iostream>
#include <vector>

using namespace std;

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);

    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);//t=a+b eg：t=12,t%10=2 push back  放入c的最后一位
        t /= 10;//eg：x=12，x/10=1
    }

    if (t) C.push_back(t);
    return C;
}

int main()
{
    string a, b;
    vector<int> A, B;
    cin >> a >> b;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');//读入的话是把小数放入a[0]以此类推
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');

    auto C = add(A, B);//auto相当于一种定义类型，这里计算机可以直接判断定义类型

    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];//输出的话我们习惯于把高位放在第一个跟读入的方式相反
    cout << endl;

    return 0;
}

(1)设置一个足够大的数N，用于标识数组的长度
(2)创建两个字符数组用于存储高精度数字
(3)创建整形数组
(4)(5)求两个高精度数字的位数
(6)(7)将两个高精度数字逆序存储到整形数组中
(8)存储两个数字中长度更长的
(9)计算新数组的长度
(10)(11)将两个数字对应位置进行相加
(12)将相加得到的数字%10存储到数组中
(13)判断是否需要进1
(14)判断最后是否还需要进1
(15)逆序打印
 

高精度减法
主要思想：用字符数组进行接收数字，将数字逐一逆序存储到数组中，对应位置依次相减。做法和高精度加法类似。
小学减法的做法：
1.对应位置相减，不够相减就向后一位借1

高精度减法步骤：
(1):字符数组存储大数字
(2):逆序插入整形数组
(3):对应位置数字相减，并判断当前所在位的被减数是否需要借1
(4):将数组数字逆序打印
 

#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)
{
    vector<int> C;
    for (int i = 0, t = 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;
    vector<int> A, B;
    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');

    vector<int> C;

    if (cmp(A, B)) C = sub(A, B);
    else C = sub(B, A), cout << '-';

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

    return 0;
}

(1)设置一个足够大的数N，用于标识数组的长度
(2)创建两个字符数组，用于接收高精度数字
(3)创建两个整形数组，用于逆序存储高精度数字
(4)接收相减的结果
(5)将大数字逆序插入到整形数组中
(6)比较两个高精度数字的长度，用于后面消除前导0
(7)比较两个高精度数字的大小
(8)模拟减法竖式运算
(9)对应位置数字相减
(10)将相减得到的结果插入到数组中
(11)判断是否需要向后一位借1
(12)去除前导0
(13)逆序打印结果

高精度乘法

主要思想:依旧是模拟小学的乘法运算，使用字符数组存储大数字，再逆序存储到整形数组中。
小学乘法的做法:
1.对应位置相乘
2.对相乘的结果%10加到后一位

这里我们进行乘法的模拟运算：

 

通过该图我们发现：
a0b0对应C1的位置
a1b0对应C1的位置
a2b0对应C2的位置
a3b0对应C3的位置
a0b1对应C1的位置
a1b1对应C2的位置
a2b1对应C3的位置
a3b1对应C4的位置
由此可以归纳出来一个规律
C[i+j]=a[i]*a[j]
由此也可得出进位等于C[i+j+1]

高精度乘法的步骤：
(1):字符数组存储大数字
(2):逆序插入整形数组
(3):对应位置数字相乘，相乘结果进行%10运算，并加到后一位上。
(4):将数组数字逆序打印
 

#include <iostream>
#include <vector>

using namespace std;


vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || 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();//考虑b=0的情况的，如果b!=0就不用加

    return C;
}


int main()
{
    string a;
    int b;

    cin >> a >> b;

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

    auto C = mul(A, b);

    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);

    return 0;
}

(1)设置一个足够大的数N，用于标识数组的长度。
(2)创建两个字符数组用于存储高精度数字。
(3)创建整形数组。
(4)将数字逆序插入数组中
(5)对所得结果%10进行进位操作
(6)相乘得到的结果需要进行%10才能存储到数组中
(7)去除前导0
(8)逆序打印数字
 

高精度除法

主要思想:依旧是模拟小学的除法运算，使用字符数组存储大数字，再存储到整形数组中。（这里插入到数组中，不是逆序插入！）

(1)4/12不够除，所以第一位商0
(2)42/12商3余3
(3)33/12商2余9
所以答案就为32余9
这里的过程为：
4/12，不够除
410+12=42 ，42/12=3，这位余下了一个3
310+3==33 ， 33/12=2，被除数每一位都走完，除法结束。余数为0
可以得到规律：
前一位的余数*10+当前位的数字/除数=商

高精度除法步骤：
(1):字符数组存储大数字
(2):正序插入整形数组
(3):计算上一位的余数*10+当前位的数字/除数的结果
(4):计算当前位的余数
(5):将数组数字逆序打印
 

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

using namespace std;

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

    int B;
    cin >> a >> B;
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');

    int r;
    auto C = div(A, B, r);

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

    cout << endl << r << endl;

    return 0;
}

(1)创建一个足够大的N为数组分配空间
(2)创建一个字符串数组用于存储大数字
(3)(4)创建两个整形数组，一个用于存储大数字，一个用于存储结果
(5)存储低精度数字
(6)将大数字按正常顺序存储数组中
(7)因为是第一位，没有上一位，所以余数t一开始设置为0
(8)当前位的数字加上上一位的余数*10,再除以除数
(9)计算当前位的余数
(10)去除前导0
(11)顺序打印结果
 

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

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

相关文章

STM32_HAL Freertos按键控制LED

STM32_HAL Freertos按键控制LED

设置GPIO引脚 根据电路图&#xff0c;K0为用户按键&#xff0c;连接在PA0引脚&#xff0c;当K0按下时接地&#xff0c;引脚电平低电平。在CubeMX中设置PA0&#xff0c;将IO设置为输入&#xff0c;上拉&#xff08;上拉外部悬空时&#xff0c;引脚为高电平&#xff09;。 添…
阅读更多...
物联网云平台源码，Spring Cloud智慧工地源码，建筑施工智能化管理

物联网云平台源码，Spring Cloud智慧工地源码，建筑施工智能化管理

智慧工地以物联网云平台为核心&#xff0c;基于智慧工地物联网云平台与现场多个子系统的互联&#xff0c;实现现场各类工况数据采集&#xff0c;存储、分析与应用。通过接入智慧工地物联网云平台的多个子系统板块&#xff0c;根据现场管理实际需求灵活组合&#xff0c;实现一体…
阅读更多...
Mac Parallels19.1.0 Install CentOS7.9

Mac Parallels19.1.0 Install CentOS7.9

0、资源准备 # centos7.9镜像一份 链接: https://pan.baidu.com/s/1acIjUnsTGhk_2cYCZLSoGg?pwd6666 提取码: 6666 --来自百度网盘超级会员v7的分享1、打开PD 2、选择镜像进行安装 指定镜像名称 创建 进行密码设置 安装目的地点开后直接点击完成 网络和主机名称 开…
阅读更多...
cad快速看图软件免费版(手机在线cad快速看图)

cad快速看图软件免费版(手机在线cad快速看图)

cad快速看图软件免费版(手机在线cad快速看图) 很多机械设计师日常工作过程中涉及到多种格式的cad图纸&#xff0c;cad图纸大多都需要cad设计软件才能打开&#xff0c;然而很多小伙伴并没有下载相应的cad设计软件&#xff0c;这种情况下如何进行cad快速看图呢&#xff1f; 今天…
阅读更多...
【开源项目】WPF 扩展组件 -- Com.Gitusme.Net.Extensiones.Wpf

【开源项目】WPF 扩展组件 -- Com.Gitusme.Net.Extensiones.Wpf

一、项目简介 Com.Gitusme.Net.Extensiones.Wpf 是一款 Wpf 扩展组件。基于.Net Core 3.1 开发&#xff0c;当前最新 1.0.1 版本。包含 核心扩展库&#xff08;Com.Gitusme.Net.Extensiones.Core&#xff09;、视频渲染&#xff08;Com.Gitusme.Media.Video&#xff09;、串口…
阅读更多...
刚学C/C++，使用的是CLion，想要在同一个项目里面运行多个相互独立脚本?

刚学C/C++，使用的是CLion，想要在同一个项目里面运行多个相互独立脚本?

前言&#xff1a; 正常来说&#xff0c;一般一个项目只会有一个程序入口点。C和C程序的入口点是main函数。在一个项目中&#xff0c;只能有一个main函数&#xff0c;否则编译器会不知道从哪个main函数开始执行。 但是&#xff0c;作为初学者&#xff0c;我就是想用CLio…
阅读更多...
Redis（Nosql数据库）

Redis（Nosql数据库）

目录 一.SQL 与 NoSQL 的区别&#xff1f; 二.Redis Redis 为什么那么快&#xff1f; 三.Redis的安装 安装redis&#xff1a; 创建redis工作目录&#xff1a; 修改redis配置文件&#xff1a; redis-cli 命令行工具&#xff1a; redis-benchmark 测试工具&#xff1a; …
阅读更多...
插槽slot涉及到的样式污染问题

插槽slot涉及到的样式污染问题

1. 前言 本次我们主要结合一些案例研究一下vue的插槽中样式污染问题。在这篇文章中&#xff0c;我们主要关注以下两点: 父组件的样式是否会影响子组件的样式&#xff1f;子组件的样式是否会影响父组件定义的插槽部分的样式&#xff1f; 2. 准备代码 2.1 父组件代码 <te…
阅读更多...
Linux驱动开发(1)-最简单的字符设备驱动开发例子

Linux驱动开发(1)-最简单的字符设备驱动开发例子

1.简介 字符设备驱动&#xff1a;按照字节流进行读写操作的设备&#xff0c;例如点灯、按键、IIC、SPI、LCD。 Linux系统中一切皆文件&#xff0c;驱动加载成功&#xff0c;就会在/dev目录生成文件&#xff0c;对文件操作&#xff0c;则可实现对硬件操作。应用程序运行在用户…
阅读更多...
Vue新手村（一）

Vue新手村（一）

目录 1、Vue简介——Vue的特点 2、Vue的第一个页面 3.Vue的简单使用介绍 3.1、{{ }}的使用 3.2、v-text和v-html 3.2.1、v-text和{{ }}的区别 3.2.2、v-html和v-text的区别 3.3、v-on【事件绑定】 3.3.1、绑定事件的语法 3.3.2、语法简化 3.3.3、传参 3.4、v-show和…
阅读更多...
excel统计分析——两因素有重复方差分析

excel统计分析——两因素有重复方差分析

参考资料&#xff1a;生物统计学 无重复观测值的两因素方差分析只能研究两个因素的主效应&#xff0c;不能考察因素间的交互作用&#xff0c;只有在确定因素间不存在交互作用时才能进行无重复观测值的试验和分析。为了准确估计因素的主效应、交互作用和随机误差&#xff0c;每个…
阅读更多...
设计模式之原型模式【创造者模式】

设计模式之原型模式【创造者模式】

学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。各位小伙伴&#xff0c;如果您&#xff1a; 想系统/深入学习某技术知识点… 一个人摸索学习很难坚持&#xff0c;想组团高效学习… 想写博客但无从下手&#xff0c;急需…
阅读更多...
第121场双周赛题解：揭秘算法竞赛中的数位挑战与解题策略

第121场双周赛题解：揭秘算法竞赛中的数位挑战与解题策略

需要多掌握解题套路 比赛地址 100157. 大于等于顺序前缀和的最小缺失整数 class Solution:def missingInteger(self, nums: List[int]) -> int:# Step 1: Find the longest consecutive prefixi 0 for i in range(1, len(nums)):if nums[i] ! nums[i - 1] 1:breakelse:…
阅读更多...
Zookeeper三节点搭建

Zookeeper三节点搭建

一、安装前准备 安装JDK&#xff08;之前已经安装了&#xff09; 拷贝apache-zookeeper-3.5.7-bin.tar.gz安装包到Linux系统下 解压到指定目录 在/opt/module/zookeeper-3.5.7/这个目录下创建zkData&#xff0c;在/opt/module/zookeeper-3.5.7/zkData目录下创建一个myid的…
阅读更多...
第 121 场 LeetCode 双周赛题解

第 121 场 LeetCode 双周赛题解

A 大于等于顺序前缀和的最小缺失整数 模拟&#xff1a;先求最长顺序前缀的和 s s s &#xff0c;然后从 s s s 开始找没有出现在 n u m s nums nums 中的最小整数 class Solution { public:int missingInteger(vector<int> &nums) {unordered_set<int> vis(…
阅读更多...
MySQL数据管理（二）

MySQL数据管理（二）

DML语言 DML &#xff08;数据操作语&#xff09;&#xff1a;用于操作数据库对象中所包含的数据 DML包括&#xff1a; INSERT&#xff08;添加数据语句&#xff09;UPDATE&#xff08;更新数据语句&#xff09;DELETE&#xff08;删除数据语句&#xff09; 一、添加数据 …
阅读更多...
Matlab三维绘图

Matlab三维绘图

绘制三维图plot3 t0:pi/50:10*pi; xsin(t); ycos(t); zt; plot3(x,y,z); 产生栅格数据点meshgrid 这个接口在绘制三维图像里面相当重要&#xff0c;很多时候要将向量变成矩阵才能绘制三维图。 x0:0.5:5; y0:1:10; [X,Y]meshgrid(x,y); plot(X,Y,o); x和y是向量&#xff0c;…
阅读更多...
qt三大控件

qt三大控件

1.QListWidget控件 先在ui界面将 QListWidget拖出来竖直对齐 再去代码中实现文本插入 两种插入方式 方法1 //listWidget使用 有左右中间对齐需求QListWidgetItem * itemnew QListWidgetItem("床前明月光"); // //上面只是独立的一句话,没有关联起来ui-&g…
阅读更多...
Android AAudio

Android AAudio

文章目录 基本概念启用流程基本流程HAL层对接数据流计时模型调试 基本概念 AAudio 是 Android 8.0 版本中引入的一种音频 API。 AAudio 提供了一个低延迟数据路径。在 EXCLUSIVE 模式下&#xff0c;使用该功能可将客户端应用代码直接写入与 ALSA 驱动程序共享的内存映射缓冲区…
阅读更多...
HarmonyOS4.0系统性深入开发15Want概述

HarmonyOS4.0系统性深入开发15Want概述

Want概述 Want的定义与用途 Want是对象间信息传递的载体&#xff0c;可以用于应用组件间的信息传递。其使用场景之一是作为startAbility()的参数&#xff0c;包含了指定的启动目标以及启动时需携带的相关数据&#xff0c;如bundleName和abilityName字段分别指明目标Ability所…
阅读更多...
最新文章

Copyright @ 2022~2023