微信号:tiankonguse-code

介绍:这里是tiankonguse在代码世界里学习时的记录

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

2018-03-14 18:49 袁小康

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

第一篇自然是认识算法。

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

特点1:计算机是万能的,她可以做到你告诉她的任何事情
特点2:计算机是低能的,你必须按照计算机的规则并清清楚楚的告诉她如何一步步做

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

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

一、输入输出

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

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

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

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

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

二、算法的输入

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

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

样例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

样例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位,求两个数字之和。
大家思考几分钟。看看输入是什么,怎么储存。输出是什么,怎么储存。
然后是怎么由输入计算出输出。

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

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

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

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

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

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

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

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

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

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

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

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

然后就是正常的循环加了,我们的循环可以正常结束了,没有任何特殊逻辑。

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

542085310 =》 54208531

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

54208531 =》 13580245

到这里我们就分步骤的解决了这道题
我们回顾一下这个问题
问题:输入两个大整数,求两个大整数的和。
我们通过一系列步骤,就根据输入逐渐转化为输出。

1. 输入储存在两个字符串中
2. 输入的字符串高低位转换,使得个位在低位
3. 标准化字符串:字符串高位填充0。
4. 循环相加。
5. 删除高位的0
6. 翻转字符串得到答案
7. 输出答案

好了,看到这里也可以回顾一下前面提到的算法基本套路了。
先明确题意,了解输入和输出是什么以及这些输入输出怎么储存
然后根据一系列步骤,想办法根据输入转化为输出
如果中间遇到了比较难处理的地方,就需要考虑细分为容易处理的子步骤
子步骤全部简单的处理完了,我们也轻松的得到了答案。

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


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

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


     
    天空的代码世界 更多文章 理财之路:股票 图片因版权被告?这里有免版权的 生活:开启留言功能 理财之路:基金 理财之路:P2P网络借贷
    猜您喜欢 学会审视自己 29个你必须知道的Linux命令 Neofetch :带发行版 Logo 图像的系统信息显示工具 最值得使用的5个免费在线java编译器 7年时间、64次迭代、10亿月活,微信凭什么?