IT牛人博客聚合

    当 1848 年国际象棋玩家 Max Bezzel 提出八皇后问题（eight queens puzzle）时，他恐怕怎么也想不到，100 多年以后，这个问题竟然成为了编程学习中最重要的必修课之一。八皇后问题听上去非常简单：把八个皇后放在国际象棋棋盘上，使得这八个皇后互相之间不攻击（国际象棋棋盘是一个 8×8 的方阵，皇后则可以朝横竖斜八个方向中的任意一个方向走任意多步）。虽然这个问题一共有 92 个解，但要想徒手找出一个解来也并不容易。下图就是其中一个解：

     

    八皇后问题有很

查看全文: http://www.udpwork.com/item/5685.html

    由于某些原因，最近在整理以前的日志。偶然翻到这篇日志时，顺便在 Wikipedia 复习了一下 Arrow 不可能性定理的证明，惊奇地发现这个定理的证明过程非常困难但又非常初等，是一个门槛很低、老少咸宜的思维游戏。虽然不少人都翻译过 Wikipedia 上的这段证明，但我也想自己写一个自己的理解，一来做个笔记，二来也锻炼一下自己的表达能力。

    Arrow 不可能性定理是一个与选举制度有关的定理。选举制度，说穿了就是把所有选民的意见综合成一个全体意见的算法。选民的意见，无非是候选对象在心目中谁优谁劣，完整地反应在选票上，就是候选对象们从优到

查看全文: http://www.udpwork.com/item/4769.html

多模式匹配在这里指的是在一个字符串中寻找多个模式字符字串的问题。一般来说，给出一个长字符串和很多短模式字符串，如何最快最省的求出哪些模式字符串出现在长字符串中是我们所要思考的。该算法广泛应用于关键字过滤、入侵检测、病毒检测、分词等等问题中。多模问题一般有Trie树，AC算法，WM算法等等。我们将首先介绍这些常见算法。

1.hash

可以单字、双字、全字、首尾字hash。

优点：简单、通常有效

缺点：受最坏情况制约，空间消耗大，需要回朔。

2.Trie树

改进：进行穿线，参考KMP的算法，进行相同前缀匹配，建立跳转路径，避免回朔。

跳转路径建立的算法思想：

如果要建立节点 A -> A’ 的 跳转路径需要满足：

查看全文: http://www.udpwork.com/item/6036.html

    一个小镇上即将进行大选，候选人有 m ≥ 3 个，选民一共有 n 人。选举时，每个选民在选票上写下一个候选人的名字，然后由计算机根据某种选举机制算出大选的获胜者来。如果把 n 个选民的选票依次记为 x1, x2, ..., xn 的话，那么选举机制的算法其实就是一个映射到 {1, 2, ..., m} 的函数 f(x1, x2, ..., xn) 。

    为了保证选举程序的公平性，让每个人手中的选票都能发挥作用，政府提出了“差异性原则”：如果每个人的选票都变了，那么竞选的获胜者也应当改变。也就是说，如果对于所有的 i 都有 xi ≠ yi

查看全文: http://www.udpwork.com/item/6368.html

    昨天终于读完了《The Annotated Turing》一书，第一次完整地阅读了 Turing 最经典的那篇论文，理解了 Turing 机提出的动机和由此带来的一系列结论。不过，这本书的最大价值，则是让我开始重新认识和思考这个世界。在这里，我想把我以前积累的哲学观点和最近一些新的思考记下来，与大家一同分享。《The Annotated Turing》一书中的一些学术内容，留待以后几篇日志与大家分享。今年是 Alan Turing 诞辰 100 周年，图灵公司将推出这本书的中译本《图灵的秘密》，现在正在紧张的编辑排版中，不久之后就能和大家见面。

   &

查看全文: http://www.udpwork.com/item/6949.html

    今天看到这里给出了一个“星际争霸是 NP-hard 问题”的一个证明。具体地说，给定一个初始布局（包括地图、双方已有资源、双方已有建筑、双方已有兵力），判断其中一方是否能获胜，这个问题是 NP-hard 的。当然，考虑到即时战略游戏的复杂性，这个结论并不出人意料；真正有趣的，则是如何巧妙地利用游戏中的元素，构造出极其精巧的初始局面，从而转化成某个已知的 NP-complete 问题。下面是原文中给出的证明。这个证明有没有什么漏洞？你还能想到哪些别的证明方法？欢迎在下面留言一同分享。

    假设初始时有 A 、 B 两位玩家，他们分别位于两个孤

查看全文: http://www.udpwork.com/item/6748.html

    这篇文章是漫话中文分词算法的续篇。在这里，我们将紧接着上一篇文章的内容继续探讨下去：如果计算机可以对一句话进行自动分词，它还能进一步整理句子的结构，甚至理解句子的意思吗？这两篇文章的关系十分紧密，因此，我把前一篇文章改名为了《漫话中文自动分词和语义识别（上）》，这篇文章自然就是它的下篇。我已经在很多不同的地方做过与这个话题有关的演讲了，在这里我想把它们写下来，和更多的人一同分享。

    什么叫做句法结构呢？让我们来看一些例子。“白天鹅在水中游”，这句话是有歧义的，它可能指的是“白天有一只鹅在水中游”，也可能指的是“有一只白天鹅在水中游”。不同

查看全文: http://www.udpwork.com/item/6654.html

今天吃晚饭的时候想到，我需要一个定制的内存分配器。主要是为了解决 共享内存 中的字符串池的管理。

这个内存分配器需要是非入侵式的，即不在要分配的内存块中写 cookie 。

而我的需求中，需要被管理的内存块都是很规则的，成 2 的整数次幂的长度。buddy memory allocation 刚好适用。

算法很简单，就是每次把一个正内存块对半切分，一直切到需要的大小分配出去。回收的时候，如果跟它配对的块也是未被使用的，就合并成一个大的块。标准算法下，分配和释放的时间复杂度都是 O(log N) ，N 不会特别大。算法的优点是碎片率很小。而且很容易做成非入侵式的，不用在被管理的内存上保存 cookie 。只需要额外开辟一个二叉

查看全文: http://www.udpwork.com/item/6560.html

    同样是无穷集合，如果集合里的元素能够与全体正整数构成一一对应的关系，我们就说它是可数的，否则就说它是不可数的。 1874 年， Cantor 发表了一篇重要的论文，论文中证明了全体有理数甚至是全体代数数都是可数的，但全体实数却是不可数的。换句话说，同样是无穷多，实数的数量比有理数、代数数的数量都高出了一个级别。不过，当时 Cantor 证明实数集不可数的方法并不容易理解。 1891 年， Cantor 发表了另一篇论文，给出了实数集不可数的另一种证明方法。此后，这个简单到不可思议的证明不断地震撼着每一个初学集合论的人：

    事实上，实数区间

查看全文: http://www.udpwork.com/item/6488.html

前言

我在哪？是LBS领域首先要解决的问题。因为技术限制，传统的GPS卫星定位只有室外的空旷地区才能够准确定位，对于室内环境来说，GPS定位往往会因“搜星”失败而无法定位。正因为GPS定位的天然缺陷，基于手机基站的定位技术正在蓬勃发展。然而因为基站的覆盖范围大，很难以取得高精度的效果，本文利用基站轨迹，提出了一个提高基站定位精度的方法。

关键字：基站定位，轨迹定位，Viterbi算法

绪论

对于单基站定位，如果仅根据用户当前的基站ID进行定位，精度必定有限。用户可能出现在基站覆盖范围内的任意一个地方，基站的覆盖范围越大，推测出来的用户位置就越不准。

如果我们还知道用户之前一段时间内经过的基站ID序列（称为基站轨迹），此时即

查看全文: http://www.udpwork.com/item/6449.html

Keith Schwarz是一个斯坦福大学计算机科学系的讲师。他对编程充满了热情。他的主页上他自己正在实现各种各样的有意思的算法和数据结构，http://www.keithschwarz.com/interesting/， 目前这个网页上有88个（见下面的列表），但这位大哥要干135个，你可以看看他的To-Do List。

从这个列表上，我们可以看到，他从去年7月份就在自己实现这些东西了，我把他实现的这些算法转过来，

一方面我们可以学习一下这些算法和代码，因为很多东西对我来说都比较新，我以前列举过一些经典的算法，算法和数据结构词典，还有可视化的数据结构和算法， 不过感觉都没有这个全。

另一方面我希望这个事可以影响到一些正在学习

查看全文: http://www.udpwork.com/item/6424.html

    去年年初的时候，我曾经发布过某专业课期末作业研究过程中带来的一个有趣的副产品：汉字的字义网络图。不过，当时我是直接调用的 Mathematica 的相关函数，函数几乎不能调整参数，并且也无法处理边上权重不同的情况。最近在研究引力斥力绘图算法，突然想到把当时的数据重新画一张图。于是就有了汉字地图第二版（点击小图看大图）：

   

    还是简述一下整个图的制作方法吧。我们的基本依据就是，在全唐诗中，经常对偶的字往往都有非常密切的关系。于是，我们首先找出全唐诗中的对偶字：

   &n

查看全文: http://www.udpwork.com/item/6387.html

话说月初的时候曾想玩玩移动app开发，目前app开发比较流行c/s架构，不，用时髦点的话说是云端架构。对于网络应用来说，第一个遇到的问题就是用户身份验证。之前基本上就没做过c/s架构的东西（和b/s对应的c/s），所以在这方面算是空白。后来面试过两个Android开发者，把这个问题当做一个系统设计的题目来问，也没有得到更多的想法。

当年做b/s时，用户身份验证这种事靠的是cookie&session，即浏览器发送请求时携带写入cookie的session_id，服务端通过session_id可以得到用户的一些信息。但session的局限性在于服务器必须维持这个状态。除此之外还有纯cookie，就是把需要维持key-val

查看全文: http://www.udpwork.com/item/6379.html

问题

最近我们在做一个项目的时候有这样一个需求：我们有多台服务器资源，希望彼此协作完成一项工作。这项工作可以被划分为N个小的模块，但由于这项工作会依赖于持续不断的输入(在线业务)，因此我们无法使用人工指定的方式将此工作分发到不同服务器进行。目前我们想到一个方法，将这项工作划分出的小模块放到一个稳定可靠的地方，例如mola存储系统，然后每台服务器去存储系统上取得一定数量的模块进行工作，完成后再将处理的结果输出到前述的存储系统上。这些小的模块虽然可以被不同的服务器运行，然后重复运行却是不可接受的(例如我们的计费日志，重复计费是绝对不允许的)。因此，当任意一台机器取得一些模块并准备运行时，一定要通知到其他所有机器：这些模块已经由我运行，

查看全文: http://www.udpwork.com/item/6367.html

    今天的题目来自这里。有三个水桶，它们里面分别装了 a 升的水、 b 升的水和 c 升的水（其中 a 、 b 、 c 都是正整数，桶本身没有容量限制）。你可以把水从一个桶倒进另一个桶，但必须保证让后者的水量刚好变成原来的两倍。证明，不管 a 、 b 、 c 是多少，你总能让其中某一个水桶变空。

    例如，假设初始时 (a, b, c) = (3, 2, 1) ，那么你可以先把 (3, 2, 1) 变成 (1, 4, 1) ，再把它变成 (2, 4, 0) ，从而把第三个水桶变空。

    让我们先来看

查看全文: http://www.udpwork.com/item/6091.html

    网友 @ipondering 分享了一个非常精彩的数学趣题集，里面有很多我之前从没见过的趣题，其中有些问题的题目和解答都相当漂亮。近段时间里，我打算从中选一些最精彩的题目来讲讲。今天的题目是该趣题集中的第二题，原题背景涉及到 King Arthur 和 Merlin 的故事，我就舍去简化了。

    某个国王手下有 n 个大臣。国王定期主持国家会议，届时 n 个大臣将会间隔均匀地坐在圆桌上。每个座位前都有一盏照明灯，只有所有的灯都亮了，会议才能开始进行。如果有些灯没亮，国王会下达指令，让指定位置上的大臣按下座位前的灯的开关，把没亮的灯都打开。例

查看全文: http://www.udpwork.com/item/5994.html