查字典图书网
查字典图书网
本章的标题既然是“程序员与算法”，就必然要涉及一个基本问题，那就是“程序员是否必须会算法”。这是一个充满争议的问题，虽然并不像“生存还是毁灭”之类的选择那样艰难而沉重，但也绝不是一个轻松的话题。朋友们在我的“算法系列”博客专栏上发表的评论和回复，并不都是我所期待的赞美和鼓励，也常常会有一些冷言冷语。... 查看全部[ 1.1 什么是算法 ]
很多人可能是好莱坞大片看多了，以为计算机神通广大，但事实不是这样的。计算机其实是一种很傻的工具，傻到几乎没有智商（至少目前是这样）。它可以连续几年做同一件事情而毫无怨言，但是如果你不告诉它怎么做，它什么事情也不会做。最有创造性的活动其实是由一种被称为“程序员”的人做的，计算机做的只不过是人类不愿意做... 查看全部[ 1.2 程序员必须要会算法吗 ]
算法有很多种存在形式，编写计算机程序只是其中一种，是程序员惯用的方式，本书要介绍的内容就是如何以计算机程序的方式研究算法。1.2节介绍的两个例子都是我亲身经历过的事情，程序员在大部分时间里都是处理一些平凡而琐碎的程序，但有时候也需要做一些创造性的工作。记住，程序员就是计算机的“上帝”，计算机能解决问... 查看全部[ 1.3 算法的乐趣在哪里 ]
本书讲到的算法都是以计算机程序作为载体展示的，其基本形式就是程序代码。作为一个软件开发人员，你希望看到什么样的代码？是这样的代码： double kg = gScale * 102.1 + 55.3; NotifyModule1(kk); double kl1 = kg / l_mask; ... 查看全部[ 1.4 算法与代码 ]
本章借用了多部知名著作中对算法的定义，只是想让大家对算法有一个“宽容”一点的理解。通过我亲身经历的两个例子，说明了程序员与算法之间“剪不断，理还乱”的关系。除此之外，还简单探讨了算法乐趣的来源、算法和代码的关系，以及研究代码本身的乐趣等内容。 如果你认同我的观点，就可以继续阅读本书了。本书的每一章... 查看全部[ 1.5 总结 ]
每年凤凰花开、蝉鸣绿叶的季节，都是毕业的季节，也是同学们找工作的季节。很显然，学生和雇主之间从来都是双向选择的关系，然而学霸们往往先人一步，早早地就抓了一把offer。无奈，即便是学霸也分身无术，最终只能选择一个offer。毫无疑问，学霸们会根据自己的偏好对offer排队，选其中最好的一个。有时候我... 查看全部[ 7.1 稳定匹配问题 ]
本节利用舞伴问题介绍一个Gale-Shapley算法的应用实例。舞伴问题是这样的：有 n 个男孩与 n 个女孩参加舞会，每个男孩和女孩均交给主持一个名单，写上他（她）中意的舞伴名字。无论男孩还是女孩，提交给主持人的名单都是按照偏爱程度排序的，排在前面的都是他们最中意的舞伴。试问主持人在收到名单后，是... 查看全部[ 7.2 Gale-Shapley算法的应用实例 ]
当参加舞会的男孩和女孩按照一定的顺序排好队，位置固定之后，使用Gale-Shapley算法能够得到一个确定的稳定匹配结果。但是对这群男孩和女孩来说，稳定匹配的结果肯定不是唯一的，其实只要将计算策略从“男士优先”转换成“女士优先”，就可以得到另外一个完全不同的稳定匹配结果。同样，调整一下男孩们的位置顺... 查看全部[ 7.3 有多少稳定匹配 ]
之前讨论稳定匹配问题的时候，我们把完美匹配定义为每个男人和女人都属于匹配中的某个对，并不是很直观，现在我们准备用图的术语更一般地表达完美匹配的概念。首先介绍一下二部图，二部图G=(V,E)是这样的一个图，它的顶点集合V可以划分为X和Y两个集合，它的边集合E中的每条边都有一个端点在X集合，另一个端点在... 查看全部[ 7.4 二部图与二分匹配 ]
各种匹配问题可不是仅仅用来娱乐的算法竞赛题目，它们在现实生活中都有着广泛的应用。比如稳定匹配原理作为一种资源的分配方法，就在美国的医疗体系中得到了广泛应用。19世纪40年代，在先进医疗技术的引领下，美国的医疗体系得到了巨大的发展，但是稀缺的医学院毕业生成了这个体系的心病。为了争抢稀缺资源，医院被迫在... 查看全部[ 7.5 总结 ]
[1] Gale D, Shapley L S. College Admissions and the Stability of Marriage. American Mathematical Monthly，1962,69:9-15 [2] Levitin A. 算法设计与分析基础. 潘彦译... 查看全部[ 7.6 参考资料 ]