首页
学习
活动
专区
工具
TVP
发布

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

大家好,我是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. 输出答案

好了,看到这里也可以回顾一下前面提到的算法基本套路了。

先明确题意,了解输入和输出是什么以及这些输入输出怎么储存。

然后根据一系列步骤,想办法根据输入转化为输出。

如果中间遇到了比较难处理的地方,就需要考虑细分为容易处理的子步骤。

子步骤全部简单的处理完了,我们也轻松的得到了答案。

这是从零开始学算法的第一篇文章,介绍一下基础知识。

如果你有什么问题,可以加入我的知识星球进行提问。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180314G1DJQT00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券