当前位置: 首页 > article >正文

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

高精度乘法、除法

  • 一、高精度乘法⭐
    • 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;
}

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


http://www.kler.cn/a/145915.html

相关文章:

  • jvm_threads_live_threads 和 jvm_threads_states_threads 这两个指标之间存在一定的关系,但它们关注的维度不同
  • STM32单片机:GPIO模式
  • 走进DevOps:让开发与运维齐头并进
  • 点云目标检测训练数据预处理---平面拟合与坐标转换(python实现)
  • 【数据分享】1929-2024年全球站点的逐年平均气温数据(Shp\Excel\无需转发)
  • 微服务与docker
  • 『heqingchun-Ubuntu系统+x86架构+编译安装ffmpeg+带有nvidia硬件加速』
  • Linux7安装mysql数据库以及navicat远程连接mysql
  • Java8实战-总结49
  • jupyter notebook 不知道密码,怎么登录解决办法
  • Spring Boot Actuator 2.2.5 基本使用
  • 代码随想录算法训练营 ---第四十五天
  • 什么是工业物联网(IOT)?这样的IOT平台你需要吗?——青创智通
  • MySQL(免密登录)
  • 【STM32单片机】贪吃蛇游戏设计
  • 【算法】装备合成(二分)
  • 【UCAS自然语言处理作业二】训练FFN, RNN, Attention机制的语言模型,并计算测试集上的PPL
  • 电子学会C/C++编程等级考试2021年09月(三级)真题解析
  • redisserver一闪而过 redis闪退解决版本
  • 深信服超融合一体机提示:内存ECC
  • Echarts title标题配置项的使用 更改颜色 副标题
  • 常见树种(贵州省):021冬青、连香树、白辛树、香合欢、云贵鹅耳枥、肥牛树、杜英、格木、黄连木、圆果化香树、南天竹
  • 基于51单片机直流电机PWM控制设计
  • linux环境下对mysql操作
  • FilterChain攻击解析及利用
  • ATK-ESP8266 WIFI模块串口通信通用实现方案