蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图)

这篇具有很好参考价值的文章主要介绍了蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

🌈前言:

📁 高精度的概念

📁 高精度加法和其模板

📁 高精度减法和其模板

📁 高精度乘法和其模板

📁 高精度除法和其模板

📁 总结


🌈前言:

蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习
        这篇文章主要是准备蓝桥杯竞赛同学所写,为你更好准备蓝桥杯比赛涉及的算法知识点。不知道你是否苦恼于不知算法从何学起,苦恼于网上资料稀少,或者复杂难懂,这篇文章就是帮助这部分同学的。

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

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

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

蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习

        上图是大学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的位置呢?

蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习

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

📁 高精度加法和其模板

蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习

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

蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习

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

蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习

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

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数组的话,要引用头文件。

📁 高精度减法和其模板

        ​​​​​​蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习

        A-B,我们要分两种情况,即A>=B,和 A < B;对于第1种情况,我们直接输出A-B即可,对于第二种情况我们输出 - (B - A);蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习

        对于模板,我们只需要确保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;
}

📁 高精度乘法和其模板

蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习

        下图便是高精度与低精度整数想乘的运算方式,将每一位数乘低精度数b + 上一位的进位,余数就是这位上的数,进位等于相除的结果。蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习

        得出模板为:

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,,依次类推。理解了这里,高精度除法也就懂了。

蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习

        下面展示模板:

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等网站进行练习,比如你看完了这篇文章,做回了例题习题,就可以上这些网站进行想应的练习。

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

蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图),蓝桥杯备赛指南,蓝桥杯,c语言,c++,学习文章来源地址https://www.toymoban.com/news/detail-801264.html

到了这里,关于蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯备赛 | 洛谷做题打卡day5

    题目描述 小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小 K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。 假设洛谷

    2024年01月17日
    浏览(59)
  • 蓝桥杯备赛 | 洛谷做题打卡day4

    高精度加法,相当于 a+b problem, 不用考虑负数 。 分两行输入。 a , b ≤ 1 0 500 a,b leq 10^{500} a , b ≤ 1 0 500 。 输出只有一行,代表 a + b a+b a + b 的值。 样例输入 #1 样例输出 #1 样例输入 #2 样例输出 #2 学会利用新知,自己多试试并尝试积攒一些固定解答方案,debug,以下是我的

    2024年01月17日
    浏览(45)
  • 蓝桥杯备赛day02 -- 算法训练题 拿金币Java

    目录 题目: 问题描述 输入格式 输出格式 解题过程 第一步 定义dp数组 第二步 确定 dp 数组递推公式  第三步 dp数组的初始化 第四步 dp数组的遍历顺序 第五步 举例说明  报错:内存超限 用dp数组去存储位置上的金币 dp数组从二维降为一维  收获:   有一个N x N的方格,每一个

    2024年01月17日
    浏览(45)
  • (基础算法)高精度加法,高精度减法

    什么叫做高精度加法呢?包括接下来的高精度减法,高精度乘法与除法都是同一个道理。正常来讲的话加减乘除,四则运算的数字都是整数,也就是需要在int的范围之内,但当这个操作数变得非常\\\"大\\\"的时候( 其实就是一个字符串,比方说有一个数是20位,如果用整数视角来

    2024年02月01日
    浏览(60)
  • C++基础算法高精度篇

    📟作者主页:慢热的陕西人 🌴专栏链接:C++算法 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 主要讲解了高精度算法的四种常用的计算 以下数字均指位数 ①A + B(精度均在10^6) ②A - B (精度均在10^6) ③A * b (len(A) = 10^6, a = 1000); ④A / b (len(A) = 10^6, a = 1000); Ⅲ. Ⅰ . A

    2024年02月16日
    浏览(36)
  • C++基础算法①——高精度加减法计算

    当我们利用计算机进行数值计算,有时候会遇到这样的问题: n!的精确结果是多少? 当n小于30的时候,我们当然可以通过电脑自带的计算器计算出来。但是当我们遇到 100! 的时候就没有办法直接计算出精确的结果。再比如,求两个20000位的数的和。 那怎么解决精度缺失的问

    2024年02月16日
    浏览(50)
  • 【蓝桥杯备赛Java组】语言基础|竞赛常用库函数|输入输出|String的使用|常见的数学方法|大小写转换

    🎥 个人主页:深鱼~ 🔥收录专栏:蓝桥杯 🌄欢迎 👍点赞✍评论⭐收藏 目录 一、编程基础 1.1 Java类的创建  1.2 Java方法  1.3 输入输出  1.4 String的使用 二、竞赛常用库函数 1.常见的数学方法 2.大小写转换 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,

    2024年01月21日
    浏览(75)
  • 【蓝桥杯备赛Java组】第一章·语言基础|竞赛常用库函数|输入输出|String的使用|常见的数学方法|大小写转换

    🎥 个人主页:深鱼~ 🔥收录专栏:蓝桥杯 🌄欢迎 👍点赞✍评论⭐收藏 目录 一、编程基础 1.1 Java类的创建  1.2 Java方法  1.3 输入输出  1.4 String的使用 二、竞赛常用库函数 1.常见的数学方法 2.大小写转换 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,

    2024年01月19日
    浏览(79)
  • 蓝桥杯备赛|成绩统计|排列字母|纸张尺寸

    目录   1 成绩统计 题目描述 输入描述 输出描述 输入输出样例 示例 1.1 解题思路 1.2 AC_Code Python 标程 2 排列字母 问题描述 2.1 解题思路 2.2 AC_Code Python 标程 3 纸张尺寸 问题描述 输入格式 输出格式 样例输入1 样例输出1 样例输入 2 样例输出 2 运行限制 3.1 解题思路 3.2 AC_Code P

    2023年04月09日
    浏览(44)
  • 【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)

    目录 写在前面: 题目:92. 递归实现指数型枚举 - AcWing题库 读题: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 距离蓝桥杯已经不足一个月了, 根据江湖上的传言, 蓝桥杯最喜欢考的是深度优先搜索和

    2024年02月03日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包