奇妙的组合之乒乓问题 |
|
|
| 来源：不详 更新时间：2013-6-6 12:10:29 |
|
|
|
|
a．米拉德·费尔默中学乒乓球俱乐部的5名成员决定举办一次淘汰赛。
b．教练解释他的比赛安排。
教练：5是一个奇数，所以第一轮比赛一名队员轮空。第二轮比赛仍有一个轮空，需比赛4场。
c．第二年乒乓球运动非常流行，俱乐部已拥有37名成员。教练还是按使轮空次数最少来安排比赛，你能算出要比多少场吗?
d．你还没算出来吗?你还在画表吗?你失去了好机会！每场比赛淘汰一名队员，有36名队员要被淘汰，要比36场，对吗?
有多少人轮空
如果你用直观的方法解决这个问题，你可以实际画一下37个人实际的比赛表。你可以看到无论怎样画，总有4个轮空。轮空数是比赛者人数n的函数，怎样来计算这个数呢?
n已知，可按如下方祛确定轮空数。用2的最小指数幂，要求它大于等于n，减去n，差额用二进制来表示。二进制表达式中1的个数就是转空数。在我们的例子中，我们用64(26)减去37得到27，用二进制表示27=11011，有4个1，所以比赛中共有4个轮空，这是满足这种奇妙算法的有趣验证。
这种问题所描述的比赛被称为是淘汰赛。计算机专家们总结这种算法是通过成对比较，确定一组几个元素中最大元素。我们看到要确定最大值，实际需要n-1次比较，计算机处理器可以比较3组，4组，5组等等这样的集合。
数据处理这个问题在计算机理论和应用上非常重要，所有的书都阐述这个问题。你可以很容易想到许多实际问题在数据处理方面的重要性。据估计，在科技、商业和工业方面花费在数据处理问题上的计算时间要占计算机运行时间的1/4。
|
上一个数学： 奇妙的组合之口香糖问题
下一个数学： 没有了 |
|
|
|
|
