大家好,我是tiankonguse。
由于某些原因,经常有人想要学习算法,但是自己之前又没有相关经验,不知道从何做起。
我思考了许久,计划写一个系列来分享如何入门学习算法。
第一篇自然是认识算法。
认识算法之前,需要先介绍一下计算机和程序语言的特点,这个特点对于新手来说相当重要。
特点1:计算机是万能的,她可以做到你告诉她的任何事情。
特点2:计算机是低能的,你必须按照计算机的规则并清清楚楚的告诉她如何一步步做。
上面的两个特点看起来很简单,但是新手往往会在这上面耗费很多的时间。
你想控制万能的计算机,你需要有强大的思维能力、逻辑能力、分析能力。
你想控制低能的计算机,你需要有细心、耐心、良好的代码规范、统一代码风格。
一、输入输出
面对编程语言,第一件事就是学会输入和输出。
学会了输入和输出,我们就可以和编程语言交互了。
所以对于程序员,学习每一门编程语言做的第一件事都是输出“hello word!”。
对于c/c++编程语言,标准输入是通过键盘输入的,对应的函数是scanf。
而标准输出是通过屏幕输出的,对应的函数是printf。 当然,常用的输入输出还有其他函数 分别对应字符的输入输出和行的输入输出。
和是c++的输入输出语法,由于性能比较低以及输出格式控制不方便,一般不使用。
ACM比赛中一般键盘就是标准输入和屏幕就是标准输出,所以直接输入输出就行了。
但是对于OI或者其他比赛,要求从指定文件输出和指定文件输出。 此时比较方便的做法是标准输出和标准输出重定向到文件,即下面的做法。
对于和常用的格式有分别代表32整数,64位整数,字符,字符串,和double浮点型。
除了字符外,其他输入都可以自动跳过空白字符。
另外一个输入输出相关的就是和了,程序中禁止使用这两个类型,由于含义不清晰,很容易出错。
程序语言的输入和输出看完了,下面就来看看算法的输入和输出吧。
二、算法的输入
比赛算法的输入其实很简单,就是告诉我们规则,我们按规则执行就行了。
但是很多新人不知道怎么遵守规则,导致基本的输入都做不到。
样例5:混合型
二、算法的输出
比赛算法的输出也是有各种各样的规则,输出即使差一个空格或换行符也不行的。
当然也有混合型的,而且和各种特殊的输入混搭在一起的,相信大家练习了上面的各种类型问题后,这些输入输出都不是问题了。
三、算法的套路
在大家经历了上面痛苦的输入输出过程后,相信大家都初步养成了细心、耐心、坚持的好习惯。
接下来需要锻炼的是更高级的能力:分析问题能力、逻辑能力。
我们面对一道题、一个问题,首先需要知道题的含义是什么?
也就是输入有什么、输出需要是什么。
然后想想怎么做,即分哪些步骤把数据从输入转化为输出。
而对于这种问题,高精度加法对初学者来说是最好的练习题了。
问题:输入两个正整数,数字的位数最大是10000位,求两个数字之和。
大家思考几分钟。看看输入是什么,怎么储存。输出是什么,怎么储存。
然后是怎么由输入计算出输出。
输入是两个大整数,我们不能使用两个整数变量储存起来,我们只能使用两个字符串储存起来。
所以输入的是两个字符串。
输入也是一个大整数,所以我们输出的答案也应该使用字符串保存起来。
所以我们的代码就像这个样子。
第二个问题就是:我们怎么对两个字符串求和呢?
这时候就要观察输入数据的特征了,假设输入的数字是”1234567”和”12345678”,我们转化为字符串的形式。
我们发现输入的大整数,数字的高位在前面,地位在后面,例如个位在最后。
我们平常相加两个数字的时候,都是从个数开始加的,因为涉及到进位。
所以我们需要把这个字符串转化为个位在前面,高位在后面。
而这个转化就是字符串翻转。
然后两个字符串就可以对齐了。
我们从左到右依次相加,如果涉及到进位,下一位就加一。
前面的正常循环都没啥问题,到了最后,发现有点麻烦。
因为涉及好几种情况:1+1、3+7、1+11、5+51等。
面对这些特殊情况,我们当然可以分别处理,但是我相信大多数人处理不过来。
所以我们还需要进行分步骤来想办法计算这个东西。
就像1+11,第二位一个是空,一个有数字,怎么相加呢?
答案是空的按0处理。
对于另一种情况3+7,进行了进位,之后没有下一位了,怎么处理呢?
答案是下一位都按0处理即可。
于是我们就可以想能不能提前预处理,不管答案是否涉及空位,提前补齐0,最后再去掉无关的0即可。
所以就得出下面的结果。
计算步骤为:得到最大位数加1,然后对不足位数的位置填充0.
然后就是正常的循环加了,我们的循环可以正常结束了,没有任何特殊逻辑。
这时候我们会发现答案的高位有前导0, 所以我们需要处理一下去掉前导0.
这里就得到了答案,不过这个答案的个位在前面,而我们输出的答案个数应该在后面,所以需要再次翻转字符串。
到这里我们就分步骤的解决了这道题。
我们回顾一下这个问题。
问题:输入两个大整数,求两个大整数的和。。
我们通过一系列步骤,就根据输入逐渐转化为输出。
1. 输入储存在两个字符串中。
2. 输入的字符串高低位转换,使得个位在低位。
3.标准化字符串:字符串高位填充0。
4. 循环相加。
5. 删除高位的0。
6. 翻转字符串得到答案。
7. 输出答案
好了,看到这里也可以回顾一下前面提到的算法基本套路了。
先明确题意,了解输入和输出是什么以及这些输入输出怎么储存。
然后根据一系列步骤,想办法根据输入转化为输出。
如果中间遇到了比较难处理的地方,就需要考虑细分为容易处理的子步骤。
子步骤全部简单的处理完了,我们也轻松的得到了答案。
这是从零开始学算法的第一篇文章,介绍一下基础知识。
如果你有什么问题,可以加入我的知识星球进行提问。
领取专属 10元无门槛券
私享最新 技术干货