便槽协议的脆弱性September 4, 2009

标题党下，其实这篇是伪科学文章。老外老外能将生涩的算法举例得如此的生动，着实让我感到佩服。这篇文章只为博君一笑，所以翻译方面就不用那么严谨啦，嘿嘿～

当我们内急的时候，走进厕所你通常会选择哪个便槽方便？这可是个国际性的话题。一般基本的情况是第一个先来家伙自由选择了便槽，那么后面来的哥们会尽量选取离他相对较远的便槽。也就是说，这样至少要能间隔一个便槽，以免尴尬的发生（老外有偷窥别人的“铅笔” Size 癖好？）。

那么，我们就可以在人数以及便槽数量上寻找些有趣的规律，用于得出厕所中放多少个便槽才是最合适。如果厕所中有五个便槽，那么可能将会这样分配：

前两个哥们分别使用第一个以及最后个便槽，第三个别无选择只能选取中间这个便槽。虽然，此时如果再有弟兄挤进去就会发生尴尬，但此时的利用率是最高的 -- 超过了 50% 的便槽正在被使用。

那么，另个方面如果厕所中有七个便槽，他们可能就不会有效的被利用：

虽然上面的情况会有四个便槽空闲，但由于第三个哥们还是选择了中间的那个便槽，于是后面来的几个哥们无从选择 -- 他们无论选择哪个，都会面临被自己的“铅笔”被偷窥的危险。

然而如果是有八个便槽，那么情况就会变得好些：

由此可以得知，厕所中八个便槽会比七个便槽具有更高的使用率，同时五个便槽效率是最高的。

现在引入个问题：如何得出，来方便的人数以及便槽数量 N 之间利用率的一般公式？我们可以写个算法搞定它，首先将先来的两位哥们安排在便槽的开头和结尾，然后递归的将其余的兄弟载入两个用户的中间。

假定 n 是便槽的数量，那么 f(n) 是来方便的人数，那么当 n > 2 时， f(n) 的一般公式为：

进一步的，根据这个公式，我们可以得出这个公式的稀疏区间。根据不同的便槽数量，我们可以了解有些便槽的利用率高、而有些利用率则相对较低。将几个数带入 n，则可以得出这样的函数曲线：

同时可以测出最高的利用率为 50% 而最低的利用率大约为 33%，将峰值取出统计成一般式，得出：

在另方面，最严重的（也就是利用率最低的）为：

因此，如果你希望厕所中的便槽使用率最高，最好的数目应该是 3、5、9、17 或者是 33；当然如果你决定最大限度的发挥使用者的偷窥天赋，那么 4、7、14 或者 25 是再合适不过的了。

上面的演算仅仅是个演算，你可以将这思想带入你生活中某这无法决定数量的情况 -- 例如决定在家中安装几个便槽（译注：老外的这个笑话真冷）。

如果你真得想制造些尴尬，你可以将这篇文章打印出来，下次给站在你旁边方便的那兄弟看看。

好吧，最后就是女权主义者不要找我麻烦，因为我不了解女厕所的情况。

-- Split --

这篇文章的评论也很精彩，在这里摘抄些：

Gracecode.com