从零开始学算法:认识算法

作者: | 更新日期:

计划写一个系列来分享如何入门学习算法

大家好,我是tiankonguse。
由于某些原因,经常有人想要学习算法,但是自己之前又没有相关经验,不知道从何做起。
我思考了许久,计划写一个系列来分享如何入门学习算法。

第一篇自然是认识算法。

认识算法之前,需要先介绍一下计算机和程序语言的特点,这个特点对于新手来说相当重要。

特点1:计算机是万能的,可以做到你告诉她的任何事情。
特点2:计算机是低能的,你必须按照计算机的规则并清清楚楚的告诉她如何一步步做事情。
特点3:我们通过程序语言来控制计算机,程序语言也是万能的和低能的。

上面的两个特点看起来很简单,但是新手往往会在这上面耗费很多的时间。
你想控制万能的计算机,你需要有强大的思维能力、逻辑能力、分析能力。
你想控制低能的计算机,你需要有细心、耐心、良好的代码规范、统一代码风格。

这里我们就来尝试控制低能的计算机吧。
我们一般通过编程语言来操作计算机,而编程语言和计算机有同样的特点。 下面依次让大家来慢慢适应编程语言吧。

一、输入输出

面对编程语言,第一件事就是学会输入和输出。
学会了输入和输出,我们就可以和编程语言交互了。
所以对于程序员,学习每一门编程语言做的第一件事都是输出“hello word!”。

对于c/c++编程语言,标准输入是通过键盘输入的,对应的函数是scanf。
而标准输出是通过屏幕输出的,对应的函数是printf。 当然,常用的输入输出还有其他函数 getchar,putchar,gets,puts分别对应字符的输入输出和行的输入输出。
cincout是c++的输入输出语法,由于性能比较低以及输出格式控制不方便,一般不使用。

ACM比赛中一般键盘就是标准输入和屏幕就是标准输出,所以直接输入输出就行了。
但是对于OI或者其他比赛,要求从指定文件输出和指定文件输出。 此时比较方便的做法是标准输出和标准输出重定向到文件,即下面的做法。

int main(){
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    //scanf或cin 输出
    //算法
    //printf或cout输出
    
    return 0;
}

对于scanfprintf常用的格式有%d %lld %c %s %lf分别代表32整数,64位整数,字符,字符串,和double浮点型。
除了%c字符外,其他输入都可以自动跳过空白字符。
另外一个输入输出相关的就是longfloat了,程序中禁止使用这两个类型,由于含义不清晰,很容易出错。

程序语言的输入和输出看完了,下面就来看看比赛的输入和输出吧。

二、算法的输入

比赛的输入其实很简单,就是告诉我们规则,我们按规则执行就行了。
但是很多新人不知道怎么遵守规则,导致基本的输入都做不到。

样例1:不知道有多少个测试数据,直到读到文件结尾为止。
练习地址:http://acm.hdu.edu.cn/showproblem.php?pid=1089

while(scanf("%d %d",&a, &b) != EOF){

}

样例2:告诉你有多少个数据样例, 然后你循环梳理对应的数据即可。
练习地址:http://acm.hdu.edu.cn/showproblem.php?pid=1090

样例3:不告诉你有多少个样例,但是告诉你以什么形式结束。
练习地址:http://acm.hdu.edu.cn/showproblem.php?pid=1091

样例4: 输入含有空格的字符串
练习地址:http://acm.hdu.edu.cn/showproblem.php?pid=1048

char buf[20]; 
while(gets(buf)){

}

样例5:混合型

练习地址:http://acm.hdu.edu.cn/showproblem.php?pid=1092 练习地址:http://acm.hdu.edu.cn/showproblem.php?pid=1093 练习地址:http://acm.hdu.edu.cn/showproblem.php?pid=1094

二、算法的输出

比赛的输出也是有各种各样的规则,输出即使差一个空格或换行符也不行的。

样例1:正常的一行一个答案型
练习地址:http://acm.hdu.edu.cn/showproblem.php?pid=1089

样例2:每组数据后一个空行型
练习地址:http://acm.hdu.edu.cn/showproblem.php?pid=1095

样例3:数据之间有一个空行型
练习地址:http://acm.hdu.edu.cn/showproblem.php?pid=1096

当然也有混合型的,而且和各种特殊的输入混搭在一起的,相信大家练习了上面的各种类型问题后,这些输入输出都不是问题了。

三、算法的套路

在大家经历了上面痛苦的输入输出过程后,相信大家都初步养成了细心、耐心、坚持的好习惯。
接下来需要锻炼的是更高级的能力:分析问题能力、逻辑能力。

我们面对一道题、一个问题,首先需要知道题的含义是什么?
也就是输入有什么、输出需要是什么。
然后想想怎么做,即分哪些步骤把数据从输入转化为输出。

而对于这种问题,高精度加法对初学者来说是最好的练习题了。

问题:输入两个正整数,数字的位数最大是10000位,求两个数字之和。
大家思考几分钟。看看输入是什么,怎么储存。输出是什么,怎么储存。
然后是怎么由输入计算出输出。

输入是两个大整数,我们不能使用两个整数变量储存起来,我们只能使用两个字符串储存起来。
所以输入的是两个字符串。

输入也是一个大整数,所以我们输出的答案也应该使用字符串保存起来。

所以我们的代码就像这个样子。


const int maxn = 11111;

void readData(char* first, char* second){
	scanf("%s %s", first, second);
}

void calAns(char* first, char* second, char* ans){
	//计算逻辑
}


void writeData(char* ans){
	printf("%s\n", ans);
}

int main(){
	char first[maxn], second[maxn], ans[maxn];
	
	readData(first, second);
	calAns(first, second, ans);
	writeData(ans);
	
	return 0;
}

第二个问题就是:我们怎么对两个字符串求和呢?
这时候就要观察输入数据的特征了,假设输入的数字是”1234567”和”12345678”,我们转化为字符串的形式。

下标:   0123456
位数 :  7654321
first : 1234567

下标:   01234567
位数 :  87654321
second: 12345678

我们发现输入的大整数,数字的高位在前面,地位在后面,例如个位在最后。
我们平常相加两个数字的时候,都是从个数开始加的,因为涉及到进位。
所以我们能够把这个字符串转化为个位在前面,高位在后面就好了。
而这个转化就是字符串翻转。

下标:   0123456
位数 :  1234567
first : 7654321

下标:   01234567
位数 :  12345678
second: 87654321

然后两个字符串就可以对齐了。

下标:   01234567
位数 :  12345678
first : 7654321 
second: 87654321

我们从左到右依次相加,如果涉及到进位,下一位就加一。
前面的正常循环就可以了,到了最后,发现有点麻烦。
因为涉及好几种情况:1+1、3+7、1+11、5+51等。

面对这些特殊情况,我们当然可以分别处理,但是我相信大多数人处理不过来。
所以我们还需要进行分步骤处理。

就像1+11,第二位一个是空,一个有数字,怎么相加呢?
答案是空的按0处理。

对于另一种情况3+7,进行了进位,之后没有下一位了,怎么处理呢?
答案是下一位都按0处理即可。

于是我们就可以想能不能提前预处理,不管答案是否涉及空位,提前补齐0,最后再去掉无关的0即可。
所以就得出下面的结果。

计算步骤为:得到最大位数加1,然后对不足位数的位置填充0.

下标:   012345678
位数 :  123456789
first : 765432100 
second: 876543210

然后就是正常的循环加了,我们的循环可以正常结束了,没有任何边界条件。

下标:   012345678
位数 :  123456789
first : 765432100 
second: 876543210
ans:    542085310

这时候我们会发现答案的高位有前导0, 所以我们需要处理一下去掉前导0.

542085310 =》 54208531

这里就得到了答案,不过这个答案的个位在前面,而我们输出的答案个数应该在后面,所以需要再次翻转字符串。

54208531 =》 13580245

上面几个小节的练习都是英文,大家很不习惯吧。
为此我找了一个中文的练习网站,大家可以去这里练习一下大整数加法吧。
练习地址:http://oj.noi.cn/oj/#main/show/1138


这是从零开始学算法的第一篇文章,介绍一下基础知识。
如果你有什么问题,可以加入我的知识星球进行提问。

大家如果有什么建议或问题可以在底部留言区留言。
当然,你也可以加我微信找我私聊,微信号: tiankonguse。

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越