acwing算法基础课文字版(看不懂你打我)——第二课基础算法之:高精度算法(大数乘小数、大数除小数)

写在前面:acwing是由北大学长创立的算法学习平台,在IT资源良莠不齐的当下异军突起。只需一顿火锅钱,就能跟着获得noi金牌的北大学长学习算法,是IT初学者进行深入研究的不二平台。本系列帖子将围绕AcWing平台的主打课程——算法基础课,并辅以本人自己的学习心得与广大算法爱好者分享知识。如果觉得本篇内容对你有帮助的话,希望不吝点赞。若有不同看法的话欢迎在评论区友善探讨。下面附上AcWing平台的地址,强烈推荐大家去学习视频课程哦!!!
链接:https://www.acwing.com/activity/content/introduction/11/
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

前置知识

算法,对于学习计算机软件相关的同学来说,无论是求职还是升学,都是不可避免的一环。

当我们面对常规的算法题时,往往对于解题速度有着一定的要求。

但当我们面对不常规的算法题时,考验我们思维深度的同时也对基础算法的掌握程度有了苛刻的要求,如果对基础算法的掌握不牢固的话,很难更进一步。

。所以,本系列将结合AcWing平台提供的基础算法模板进行算法硬核干货讲解。

理解并熟悉 本系列的基础算法,将对同学们的求职升学都带来极大帮助,对于类似蓝桥杯等比赛也能轻松拿下!

高精度乘法(大数乘小数)

该课程,总共七章,平均每章三节课左右。视频总共45小时,这里是第一章第二节课的大数乘小数。

算法原理

第一步:依旧需要设置一个进位t.。

算法模板

#include<iostream>
#include<cstdio>
#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++){ //要么是i没有循环完,要么是t不等于零
		if(i < A.size()) t += A[i] * b;
		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');
	
	auto C = mul(A,b);
	for(int i = C.size() - 1; i >= 0; i--) printf("%d",C[i]);
	return 0;
}

高精度除法(大数除小数)

该课程,总共七章,平均每章三节课左右。视频总共45小时,这里是第一章第二节课的大数乘小数。

算法原理

第一步:依旧需要设置一个进位t.。

算法模板

#include<iostream>
#include<cstdio>
#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;
	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<< r<<endl;

	return 0;
}

补充说明

前导零的固定格式要记住。这里的除法本来不用倒过来,但是平时题目里经常是四则运算混合的,所以要倒过来,为了和其他的统一。

上一篇:实验5-3 使用函数求奇数和 (15 分)


下一篇:合并两个有序数组-88