《计算机是怎样跑起来的》————让写算法跟呼吸一样简单

 程序是用来在计算机上实现现实世界中的业务和娱乐活动的。为了达到这个目的，程序员们需要结合计算机的特性，用程序来表示现实世界中对问题的处理步骤，即处理流程。在绝大多数情况下，为了达到某个目的需要进行若干步处理。例如为了达到“计算出两个数相加的结果”这个目的，就需要依次完成以下三个步骤，即“输入数值”“执行加法运算”“展示结果”。像这样的处理步骤，就被称为算法。

int a,b;
scanf("%d %d",&a,&b);
printf("%d",a+b);

 学习编程语言和学习外语类似，都需要记忆单词和语法。但是学习算法仅仅囫囵吞枣地把关键词和语法记下来，是无法写出算法的，就像只记忆了外语中的单词和语法，却无法流利的说外语。无论是说外语，还是写算法，都是将自己的想法和思考通过一门外语或一门编程语言表达出来，所以在这个过程中，你的想法和思考才是最重要的，一篇表达清晰，逻辑严密的文章总是比一篇用华丽的辞藻堆砌，思想空洞的要来的好。只要理清在现实世界解决问题的步骤，再结合计算机的特性，就一定能想出算法。接下来将是一些思考算法的一些要点。
要点一：算法中解决问题的步骤是明确且有限的。 我们需要了解一下算法的基本概念，通俗易懂的语言来说，算法就是“把解决问题的步骤无一遗漏地用文字或图表示出来”。要是把这里的“用文字或图表示”替换为“用编程语言表达”，算法就变成了程序。但是需要注意的是“步骤必须是明确的并且步骤数必须是有限的”。
接下来举个简单的例子，试求出 12 和 42 的最大公约数，。最大公约数是指两个整数的公共约数（能整除被除数的数）中最大的数。最大公约数的求解方法应该在中学的数学课上学过了。把两个数写在一排，不断地寻找能够同时整除这两个整数的除数。最后把这些除数相乘就得到了最大公约数。如下图所示：

但这是算法吗？答案是不是，因为步骤不够明确。步骤一和步骤二为什么是这样的？步骤三又是怎么知道的？为什么只需要四个步骤？这些内容都是不明确的，或者说是靠直觉判断的，所以这并不能看作是算法，更不能用程序表示。
要点 2：计算机不靠直觉而是机械地解决问题。 刚刚提到靠直觉判断的步骤并不能看作是算法，归根结底的来说，算法是靠计算机来执行，而计算机并不能像人一样自发的思考和用直觉判断，因此计算机所执行的由程序表示的算法必须是由机械的步骤所构成。所谓“机械的步骤”，就是不用动任何脑筋，只要按照这个步骤做就一定能完成的意思。
辗转相除法就是一个由机械的步骤构成的解决最大公约数的经典算法。

在辗转相除法中分为使用除法运算和使用减法运算两种方法。使用减法运算简单易懂。用两个数中较大的数减去较小的数（步骤），反复进行上述步骤，直到两个数的值相等（步骤的终止）。如果最终这两个数相同，那么这个数就是最大公约数。
请诸位注意以下三点：

1. 步骤是明确的、完全不依赖直觉的；
2. 步骤是机械的、不需要动脑筋就能完成的；
3. 使步骤终止的原因是明确的。
   这些步骤符合算法的特征，即上面的所有步骤都可以用程序表示：

int a = 12;
int b = 42;
while (a != b) {if (a > b) {a = a - b;} else {b = b - a;}}
printf("最大公约数为 %d。\n", b);

 要点 3：了解并应用典型算法.“令人生畏且难以掌握”“和自己无缘”，诸位是不是会对算法留下这样的印象呢？诚然，有那种无法轻松理解、难以掌握的算法，但是我们也可以站在巨人的肩膀上，把算法看透。有些经典的算法需要我们去学习和掌握，这是学习算法的必经之路。

但即便我们学习和掌握了一些经典的算法，也不一定能解决一些特殊的问题。所以我们更多的是自己思考，依托经典算法里的算法思想，切实的去解决具体的问题。
要点 4：使用编程技巧提升程序执行速度。 解决一个问题的算法未必只有一种。在考量用于解决同一个问题的多种算法的优劣时，可以认为转化为程序后，执行时间较短的算法更为优秀。虽然计算机的处理速度快得惊人，但是当处理的数据数值巨大或是数量繁多时还是要花费大量的时间。例如，判定 91 是否是素数的过程一下子就有结果了，可是要去判定 999999937 的话，程序执行的时间就会延长很多了。
有时稍微往算法中加入一些技巧，就能大幅度地缩短处理时间。在判定素数上，原先的过程是用待判定的数除以比它小的所有正整数，只要在此之上加入一些技巧，改成用待判定的数除以比它的 1/2 小的所有数，处理时间就会缩短。
要点 5：找出数字间的规律. 所有的信息都可以用数字表示——这是计算机的特性之一。因此为了构造算法，经常会利用到存在于数字间的规律。例如，请思考一下判定石头剪刀布游戏胜负的算法。如果把石头、剪刀、布分别用数字 0、1、2 表示，把玩家 A 做出的手势用变量 A 表示，玩家 B 做出的手势用变量 B 表示，那么变量 A
由表中内容可以找到一些数字的规律：

● 如果变量 A 和 B 相等就是“平局”
● 如果用 B＋1 除以 3 得到的余数与变量 A 相等就是“玩家 B
获胜”
● 其余的情况都是“玩家 A 获胜”
所以最终的程序代码是这样的：

if (A == B) {printf("平局\n");} else if (A == (B + 1) % 3) {printf("玩家 B 获胜\n");} else {printf("玩家 A 获胜\n");}

 要点 6：先在纸上考虑算法。 最后介绍最为重要的一点，那就是思考算法的时候，要先在纸上用文字或图表描述出解决问题的步骤，而不要立刻开始编写代码。
在纸上画完或写完流程以后，再把具体的数据代入以跟踪流程的处理，确认是否能得到预期的结果。在验算的时候，建议使用简单的数据，这样即使是用心算也能得出正确的结果。例如，要确认辗转相除法的流程，就可以使用数值较小的数做验算，这样就算是用中学所学的求解步骤也能求出最大公约数。如果使用的是数值较大的数，比如 123456789 和987654321（最大公约数是 9），那么就难跟踪流程的处理了。
最后这些就是我在这本书中看到的学习算法的几个要点，希望对您在学习算法的路上提供助力，感谢您的查看浏览。