论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2005-09-30 20:53 |只看该作者 |倒序浏览

应lenovo版主之请，将Dijkstra大师寓言的中文版转贴如下：

原贴见：
http://bbs.chinaunix.net/forum/v ... w_type=&start=0

一个寓言

多年以前有一个铁路公司，它的一位领导（可能就是商务方面的头儿）有了这样一个
发现，如果只给百分之五十的车厢配备厕所的话，原始投资将会大大地减少。于是，
他们决定就这么做了。

公司执行这项措施之后不久，关于厕所的抱怨就接踵而至。经调查发现，实际情况是
尽管这家公司还很年轻，但它已经存在严重的内部沟通问题，因为上头关于厕所的决
定并没有传达给调度室，所有的车厢都得到了同等的对待，于是有时候一列车中几乎
没有一个厕所。

为了解决这个问题，给每个车厢都加上了一些信息，用于区别这个车厢上是否有厕所，
调度室则需要在列车编组的时候尽量保证两种车厢的数量是相等的。这对调度来说无
疑是个麻烦事，不过问题解决之后，负责调度过程的人们都为此而非常得意。

新的调度过程实施之后，关于厕所的抱怨却依然没有平息。新的调查发现，尽管在一
列车中确实有一半的车厢有厕所，但有时候却把所有的厕所都编组在了列车的一头。
为了对此加以补救，上头又有了新的措施，规定带厕所的车厢和不带厕所的车厢应该
交替编组。这个方法的复杂度对于调度人员来说实在是太恐怖了，不过在最初的一番
唧唧崴崴之后，他们最终还是搞定了。

然而，抱怨仍在继续。调查出来的原因是，对于那些有厕所的车厢来说，厕所都位于
车厢的一头，列车中两个相邻厕所的距离仍然可能会有三个车厢的长度。对于那些有
紧急需要的抱小孩儿的妈咪们——尤其是过道上充塞着行李箱的时候——就会导致灾
难性的后果。结果是，给那些带厕所的车厢又加上了一点信息，将它们变成了带方向
的物体，新的规定是，在每个列车中，所有带厕所的车厢都必须是同向的。这一次，
调度人员收到新的指示的时候就差没疯掉了，因为调车转台的数目刚刚够用，如果要
完全公正地说的话，我们必须得承认，按照任何合情合理的标准，调车转台的数目是
不够用的，调度人员必须发挥极大的创造力才能勉强搞定。

等到所有的厕所都均匀地分布在列车中之后，公司有理由确信所有的事情都OK了，不
过乘客们依然在抱怨：尽管没有乘客离最近的厕所会超过一节车厢，乘客们（尤其是
有紧急需要的）不知道该向过道的那个方向开始他们的冲刺！为了解决这个问题，
写有“TOILET”的箭头被固定在了过道上。这就让另一半的车厢也变成了带方向的物
体，调度过程也必须对它们的方向进行正确地排列。

收到新的指令之后，调度室里充斥着绝望和反抗的情绪：这是不可能的！在这个关键
时刻，有个人站了出来，他的名字已经被遗忘了，而且也无从查证，他做出了以下的
分析。当每节带厕所的车厢都在它的有厕所的一头和另一节没有厕所的车厢配好对之
后，调度室根本无需再为N个两种类型的带方向的车厢而烦恼了，因为他们面对的将
是N/2个同样的单元，不管从哪个方面说，这些单元都可以被认为是对称的。这个分析
搞定了所有的调度问题，不过稍微有点代价，首先是每次只能向列车上加挂偶数个
的车厢——由此而增加的少量车厢可以从商务头目最初省下的那笔钱里面报销！——
其次，假定所有厕所的尺寸都是相同的。不过，谁会在乎那最后的三英尺呢？

尽管在发生这个故事的时候人类还没有计算机，但发现解决方案的那位匿名人物可以
当之无愧地被视为全世界第一个合格的程序员。