刚做了道脑残的放鸽子题

2009 5 20 03:09 PM 1477次查看

分类：无 标签：无

一共有25只鸽子。
每次可以放飞其中5只，并得知其速度排名（不知道具体速度）。
已知每只鸽子每次的飞行速度都不变，且各不相同。
求最少放飞多少次，可以找出其中最快的5只鸽子（可以对鸽子进行编号）。

想了半天，终于做出来了，以下剧透注意。

首先看最笨的方法：
第1次：放飞其中5只，按排名编为1～5。
第2次：放飞另5只，按排名编为6～10。
……
第5次：放飞最后5只，按排名编为21～25。

第6次：每组的第1名相比，得到总第1名，假设是1号。
第7次：把得胜那组第2名（即2号）与剩下各组第一（即6、11、16和21）相比，得到总第2名，假设是6号。
第8次：把得胜那组剩下最快的（即7号）与剩下的各组第一（即2、11、16和21）相比，得到总第2名，假设是6号。
……
依此顺序，第10次得到第5名。

再想一下，其中很多次比较都是无意义的。
假设第6次得知1>6>11>16>21，那么第2名就只可能是2或6之间的，不需要再次比较11、16和21。
而第3名也只能是3、7、11和2、6之间的。
所以第7次可以这样比：2    3    6    7    11
这样第2名是其中最快的，第3名是其中第2快的。

假设顺序就是：2>3>6>7>11。
那么可以拿到下表：
12345
678910
1112131415
1617181920
2122232425
那么第8次只要比较4、5、6、7即可得知第4、5名。这是最好情况。

假设顺序是6>11>7>2>3。
那么根据目前的情况，可以拿到下表：
161172345
78910
1112131415
1617181920
2122232425
可见第4名可能是7、12、16，第5名则还需加上2、8、13、17、21。
那么第8次选2、8、13、17、21，比出前2名。
这前2名再加上7、12、16，比第9次，则前2名分别是第4、5名。
这也是最坏的情况。

所以答案是最好情况是8次，最差是9次。
实际上第7次还有其他的方法，但我试过都至少要9次，所以应该没有更好的方法了。

0条评论 你不来一发么↓

    想说点什么呢？