纳新季之算法介绍

ZUCCIOT实验室之算法介绍

划

重

点

Q1：什么是算法

Knuth在《计算机程序设计艺术》中将算法（Algorithm）描述为从一个步骤开始，按照既定的顺序执行完所有步骤，最后得到结果的一个过程。从上面这段描述中，我们可以知道，如果将问题的来源看作是原料，我们所期望的结果看作是产品的话，算法就是产品的生产过程。

在不同的著作中，对算法的定义都有不同的表述，虽然到现在还没有被普遍接受的“算法”的正式定义，但是在各种著作中，对算法的基本特征的定义是明确的。作为解决问题的方法，算法有以下四个特征：

有穷性：即算法必须在有限个步骤后终止。

确定性：算法的每个步骤是明确的，所得到的结果也是确定的。

可行性：一般来说，我们希望算法最后得出的是正确的结果，就要保证算法中的每一个步骤都是可行的。

输入和输出：正如上文所说，算法是用来解决特定的问题的，问题就是算法的输入，其结果就是算法的输出，不用来解决问题的算法是没有意义的，得不到结果的算法是没有用的。

Q2：算法与生活

从上面的定义我们可以知道，算法并不是程序员的专长，也不是什么高深莫测的事物，

算法只是用来解决特定问题的一种方法。小到专业领域，大到生活中的方方面面，我们都能从中发现算法的身影：

Microsoft Office套件中的Project软件使用了能帮助我们在生活中找到更好的安排工程项目开始时间的方法——关键路径算法；在我们使用的购物软件中经常带有推荐系统，这些推荐系统中使用了与数据挖掘方面的相关算法——协同过滤，朴素贝叶斯；旅游公司在帮助我们做一日游行程规划时，用到了基于路程的最短图路径算法，基于价格的贪心算法，以帮助我们规划出性价比最高的行程；人机对弈的背后有各种博弈树搜素算法，一个能立于不败之地的井字棋AI，所需的代码也只有100行左右；音频播放器显示的频谱背后是离散傅里叶变换算法；著名的PCX图像文件格式用的是RLE压缩算法；历法和二十四节气的计算使用了牛顿迭代法……类似的例子在生活中不胜枚举，由此可见算法离我们并不遥远，我们也在生活中享受过算法带给我们的便利。

《算法的乐趣》一书中有这样一段话：“算法之大，大到可以囊括宇宙万物的运行规律，算法之小，小到寥寥数行代码即可展现一个神奇的功能，算法是琐碎的，以至于常常被人们忽视，然而忽视算法能力的培养所带来的代价是巨大的。”当代社会，我们不管从事什么样的专业，都需要与计算机打交道。计算机是一个空有蛮力的小伙子，需要我们给它下指令它才能完成工作，那么作为指挥计算机完成工作的我们，是去贴吧论坛当一个伸手党求代码，还是自己研究解决问题的算法呢？答案不言而喻。

毕竟不是一关注就能拿到奖品的，还需要付出一些时间精力去分享、拉新。如果有人为了拿奖品恶意刷粉，我们后台可以监测到的哟~

Q3：个人订阅号能用吗？

舞伴问题：有n个男孩和n个女孩参加舞会，每个男孩和女孩均交给主持人一个名单，写上他中意的舞伴名字。无论是男孩还是女孩，提交给主持人的名单都是按照偏爱程度排序的，排在前面的都是他们最中意的舞伴。试问主持人在收到名单后，是否可以将他们分成n对，使得每个人都能和他们中意的舞伴结对跳舞？为了避免舞会上出现不和谐的情况，要求这些舞伴的关系是稳定的（不存在不稳定因素）。

不稳定因素的定义：如果有2对分好的舞伴：男孩A和女孩B，男孩B和女孩A。但是男孩A更想和女孩A一起，女孩A也更想和男孩A在一起。男孩B更想和女孩B一起，女孩B也更想和男孩B在一起，那么这2对分好的舞伴就会倾向于分开，这就是不稳定因素。

图解：红线的两人倾向于组合，绿线的两人倾向于分开。

若要用计算机程序来求解这道题看起来十分复杂，但是好在前人已经研究出了解决这种匹配问题的算法：Gale—Shapley算法，该问题的Gale—Shapley算法程序框图如下：

在学习了编程语言后，大家可以尝试将上面的程序框图翻译成编程语言，再设计一组样例作为输入后，就可以看到匹配后的结果。

例：有一组输入样例如下：

我将上面程序框图所表示的算法翻译成了C语言，编译运行后输入上面的样例打印结果如下：

从上面用Gale-Shapley算法求解的过程来看，女孩从接受第一个邀请开始就有了舞伴，并且舞伴会越来越好，因为女孩可以根据自己的偏爱名单确定是否选择更好的舞伴，与此同时，男孩如果被拒绝，他的选择会变得越来越差，因为他们是按照他们的偏爱列表由好到差开始选择的。看起来这个算法过程对女孩更有利一些，然而实际情况是：在Gale-Shapley算法中，主动邀请的他人的一方往往会找到自己比较中意的舞伴，而被动接受的一方得到的舞伴往往不尽如意，排在他们偏爱名单较后面的位置，这种情况正是因为选择的主动权所导致的。在现实生活中也有相同的道理：婚姻中的男人如果不主动争取，条件好的女孩就会投入别人的怀抱。

Q4：ZUCC物联网实验室对算法能力的培养

ZUCC物联网实验室对编程水平与算法能力的培养一直比较重视，在2017届大一新生进入实验室时指导其进行Python语言的学习，并在学习完Python语言后组织实验室所有成员在PAT网站中完成乙级难度题目，以提高实验室成员的整体编程水平和算法能力，在2017年第一学年结束时实验室全体成员完成了PAT网站中乙级难度的80道题目，并且全体成员总分都高于1200分，这为后续的项目打下了良好的基础。此外，实验室的公共书架上摆有许多与算法和编程语言有关的书籍，可供实验室成员随时学习。

Q5：感谢

本推送内容部分参考自《算法的乐趣》一书，特此向原作者表示感谢。

END

▼

从这里了解更多zucc物联网创新实验室

▼