乒乓问题

有多少人轮空

如果你用直观的方法解决这个问题，你可以实际画一下37个人实际的比赛表。你可以看到无论怎样画，总有4个轮空。轮空数是比赛者人数n的函数，怎样来计算这个数呢?

n已知，可按如下方祛确定轮空数。用2的最小指数幂，要求它大于等于n，减去n，差额用二进制来表示。二进制表达式中1的个数就是转空数。在我们的例子中，我们用64(2⁶)减去37得到27，用二进制表示27=11011，有4个1，所以比赛中共有4个轮空，这是满足这种奇妙算法的有趣验证。

这种问题所描述的比赛被称为是淘汰赛。计算机专家们总结这种算法是通过成对比较，确定一组几个元素中最大元素。我们看到要确定最大值，实际需要n-1次比较，计算机处理器可以比较3组，4组，5组等等这样的集合。

数据处理这个问题在计算机理论和应用上非常重要，所有的书都阐述这个问题。你可以很容易想到许多实际问题在数据处理方面的重要性。据估计，在科技、商业和工业方面花费在数据处理问题上的计算时间要占计算机运行时间的1/4。

上一页   下一页