[蓝桥杯训练]———高精度乘法、除法

高精度乘法、除法

  • 一、高精度乘法⭐
    • 1.1 初步理解
      • 1.1.1 高精度的定义
      • 1.1.2 为什么会有高精度
      • 1.1.3 高精度乘法的复杂度
    • 1.2 思想讲解
    • 1.3 代码实现
      • 1.3.1 声明
      • 1.3.2 实现高精度乘法
      • 1.3.3 整体实现
      • 1.3.4 代码测试
  • 二、高精度除法⭐
    • 2.1 初步理解
    • 2.2 思想讲解
    • 2.3 代码实现
      • 2.3.1 声明
      • 2.3.2 div部分
      • 2.3.3 整体部分

hello! 这里是欧_aita的频道。
今日语录:不要等待机会,而要创造机会。
祝福语:愿你的程序像太阳一样明亮,给世界带来温暖和光明。
大家可以在评论区畅所欲言,可以指出我的错误,在交流中共同进步。
欢迎大家关注我的专栏:
数据结构与算法(内含蓝桥杯算法训练)
C++基础
MySQL数据库

一、高精度乘法⭐

1.1 初步理解

1.1.1 高精度的定义

在计算机科学中,高精度算法通常指的是处理超过计算机原生数据类型表示范围的数字的能力。例如,如果要处理非常大或非常小的整数或小数,可能需要使用高精度算法,因为标准的整数和浮点数类型的表示范围是有限的。

通常存在两种
1.大整数高精度
2.浮点型高精度

1.1.2 为什么会有高精度

举个例子,如果需要运算一个按千亿级别的加减乘除运算,按照普通的运算方法是非常占用时间的,但是我们如果使用一个数组存储想要进行运算的数字,然后化解为三个数的运算,这样就会大大提高代码的效率。

1.1.3 高精度乘法的复杂度

会依次遍历存储大整数的数组,所以时间复杂度是O(n),其中n是指存储大整数的数组长度。

1.2 思想讲解

首先是输入,我们正常来说都会选择倒着存储数字
在这里插入图片描述
注意下标表示的是数组中的下标
在这里插入图片描述
在这里插入图片描述
此时所求的C就求出来了

1.3 代码实现

1.3.1 声明

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

1.3.2 实现高精度乘法

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

这里最不好理解的是t,这个t是重复使用的,但也是在不断更新的。

1.3.3 整体实现

#include <iostream>
#include <cstring>
#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() - 1; i++)
	{
		t = A[i] * b + t;
		C.push_back(t % 10);
		t /= 10;
	}
	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');
	}

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

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

1.3.4 代码测试

在这里插入图片描述

二、高精度除法⭐

在这里插入图片描述

2.1 初步理解

大致理解是和乘法是一样的,但是除法的实现会更加抽象。

2.2 思想讲解

在这里插入图片描述
得出的结果是上一位余数(r*10+A[i])/b。

2.3 代码实现

2.3.1 声明

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

2.3.2 div部分

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;
}

注意,原本的vector数组中只能对队尾元素插入删除实现O(1)的时间复杂度,所以我们把整个结果reverse一遍,这样判断数组尾部是否为0,如果是就删除。

2.3.3 整体部分

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

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;
	int b;

	cin >> a >> b;
	vector<int>A;
	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--)printf("%d", C[i]);
	cout << endl << r << endl;
	system("pause");
	return 0;
}

这篇文章就到此结束了,如果对你有所帮助,就点个赞吧,你的支持对我而言很有帮助!

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

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

相关文章

【Vulnhub靶机】Jarbas--Jenkins

文章目录 信息收集主机发现端口扫描目录爆破 漏洞探测whatwebhash-identifierwhatweb 文档说明&#xff1a;https://www.vulnhub.com/entry/jarbas-1,232/ 靶机下载&#xff1a;Download (Mirror): 信息收集 主机发现 扫描C段 sudo nmap -sn 10.9.75.0/24端口扫描 sudo nma…

【教学类-06-11】20231125(55格版)X-Y之间“除法÷题”(以1-9乘法口诀表倒推)(随机抽取和正序抽取)

图片展示 &#xff08;随机打乱排序&#xff09; 正序&#xff08;每张都一样&#xff09; 背景需求&#xff1a; 前面三篇写到了随机加法、随机减法、随机乘法&#xff0c;既然做了三套&#xff0c;怎么能不试试最后一款“除法”呢 模仿乘法版本&#xff0c;制作打乱版和正…

安卓用SQLite数据库存储数据

什么是SQLite&#xff1f; SQLite是安卓中的轻量级内置数据库&#xff0c;不需要设置用户名和密码就可以使用。资源占用较少&#xff0c;运算速度也比较快。 SQLite支持&#xff1a;null&#xff08;空&#xff09;、integer&#xff08;整形&#xff09;、real&#xff08;小…

前端入门(三)Vue生命周期、组件技术、脚手架、存储、事件总线、

文章目录 Vue生命周期Vue 组件化编程 - .vue文件非单文件组件组件的注意点组件嵌套Vue实例对象和VueComponent实例对象Js对象原型与原型链Vue与VueComponent的重要内置关系 应用单文件组件构建 Vue脚手架 - vue.cli项目文件结构组件相关高级属性引用名 - ref数据接入 - props混…

安卓系统修图软件(一)

平时我们会不时在朋友圈发自己的自拍照&#xff0c;或者是风景图等&#xff0c;许多小伙伴们此时会对照片进行一定的修理&#xff0c;比如添加滤镜等操作。在电脑上用ps修图比较繁琐&#xff0c;日常中大可不必用这把宰牛刀&#xff1b;而手机自带的编辑器&#xff0c;或者是QQ…

【Java基础系列】文件上传功能

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

反思一次效能提升

前天与一个大佬交流。想起自己在6年多前在团队里做的一次小小的效能提升。 改进前 在同一个产品团队&#xff0c;同时有前端工程师和后端工程师。他们经常需要共同协作完成features。 前端是一个传统的多页应用。前端渲染是由后端的velocity模板引擎实现的。 打包后&#xff0c…

【电路笔记】-分流器

分流器 文章目录 分流器1、概述2、通用/网络配置3、无功分流器3.1 电阻电容分流器3.2 电阻-电感分流器 4、总结 我们在之前关于分压器的文中已经看到&#xff0c;分压过程是通过在串联配置中关联相同的组件来实现的。 在本文中&#xff0c;我们将重点关注电流分频器执行的电流分…

“不得了·放飞杯” 2023年四川省健身健美锦标赛启动在成都隆重召开

“不得了放飞杯” 2023年四川省健身健美锦标赛启动在成都隆重召开 为了更好地推动四川省健身健美运动的普及和发展&#xff0c;结合《四川全民健身实施计划》的现状&#xff0c;适应新时代健身私教服务产业的发展需求&#xff0c;由中国健美协会指导&#xff0c;四川省健美健美…

M2BLS

U are randomly generated&#xff0c;g is an activation function 辅助信息 作者未提供代码

如何通过ShardingJDBC进行读写分离

背景信息&#xff1a; 面对日益增加的系统访问量&#xff0c;数据库的吞吐量面临着巨大瓶颈。 对于同一时刻有大量并发读操作和较少写操作类型的应用系统来说&#xff0c;将数据库拆分为主库和从库。其中主库负责处理事务性的增删改操作&#xff0c;从库负责处理查询操作&#…

【Qt绘制仪表盘】

目的 使用Qt的绘制事件绘制一个仪表盘 思路 需要创建一个带绘制事件的控件重写绘制事件显示 实现 以下是实现代码&#xff0c;可复制到程序到&#xff0c;直接运行。 .h // GaugeWidget.h #ifndef GAUGEWIDGET_H #define GAUGEWIDGET_H#include <QWidget>class Ga…

Docker Swarm总结+基础、集群搭建维护、安全以及集群容灾(1/3)

博主介绍&#xff1a;Java领域优质创作者,博客之星城市赛道TOP20、专注于前端流行技术框架、Java后端技术领域、项目实战运维以及GIS地理信息领域。 &#x1f345;文末获取源码下载地址&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3fb;…

【WSA】无法打开 适用于 Android™ 的 Windows 子系统,因为它处于脱机状态。可能缺少存储设备,或者存储设备已断开连接。

问题描述 之前可以正常使用适用于 Android™ 的 Windows 子系统&#xff08;WSA&#xff09;&#xff0c;但突然间无法启动了。 当尝试启动WSA中的软件时&#xff0c;都会出现以下错误提示&#xff1a; 无法打开 适用于 Android™ 的 Windows 子系统&#xff0c;因为它处于脱…

《微信小程序开发从入门到实战》学习三十

3.4 开发参与投票页面 3.3.7 获取用户信息 如果投票是实名投票&#xff0c;那么用户点击完成确认投票时&#xff0c;需要将用户投票信息和用户昵称一起提交&#xff0c;可以在JS文件中使用API接口wx.getuserInfo获取用户的信息。 使用wx.getUserInfo接口前需要对获取 用户信…

C语言—二维数组

一、二维数组的创建 int arr[3][4];char arr[3][5];double arr[2][4]; 数组创建&#xff1a;“[ ]”中要给一个常量&#xff0c;不能使用变量 二、二维数组的初始化 int arr[3][4]{1,2,3,4};int arr[3][4]{{1,2},{4,5}};int arr[][4]{{2,3},{4,5}}; 前面的为行&#xff0c…

ethernet II 的故事

以太帧有很多种类型。不同类型的帧具有不同的格式和MTU值。但在同种物理媒体上都可同时存在。 以太网第二版或者称之为Ethernet II 帧&#xff0c;DIX帧&#xff0c;是最常见的帧类型。并通常直接被IP协议使用。 格式 当数据帧到达网卡时&#xff0c;网卡要先去掉前导码&#…

leetcode刷题详解四

25. K 个一组翻转链表 这道题本质上还是用的反转前n个链表的思想。 具体细节如下&#xff1a; 先调用一次函数&#xff0c;使用一个newHead接受返回值&#xff0c;这个是为了方便最后函数的返回。 调用reverseN这个函数的时候&#xff0c;要标记反转这段链表的前置节点和后置节…

用户与组管理:如何在服务器系统中管理用户和权限

你是否想过&#xff0c;当你登录到一个服务器系统时&#xff0c;你是如何被识别和授权的&#xff1f;你是否知道&#xff0c;你可以通过创建和管理用户和组来简化和优化你的系统管理工作&#xff1f;你是否想了解一些常用的用户和组管理命令和技巧&#xff1f;如果你的答案是肯…

接口测试场景:怎么实现登录之后,需要进行昵称修改?

在接口测试中有一个这样的场景&#xff1a;登录之后&#xff0c;需要进行昵称修改&#xff0c;怎么实现&#xff1f; 首先我们分别看下登录、昵称修改的接口说明&#xff1a; 以上业务中补充一点&#xff0c;昵称修改&#xff0c;还需要添加请求头Authorization传登录获取的to…