珍珠湾ART

标题: 瓶子体积比较 [打印本页]

作者: ob 时间: 2005-3-5 03:51
标题: 瓶子体积比较

有5个形状不同，体积不同的瓶子。比较两个瓶子体积的唯一办法是将一个瓶子装满水，倒入另一个。当然，如果a>b,b>c,那么不用比a和c也知道a大。
现在要找出体积第3的那个瓶子，最坏情况需要比较几次？怎么比？

作者: 我很高兴 时间: 2005-3-5 08:54
标题: 回复：瓶子体积比较[>:D<]

这个是不是等同于数据结构里的有5个数，用最坏的冒泡法（Bubble Sort）比较大小并排序的最坏的效率呢？

是不是n(n-1)/2次？也就是10次？（我认为的前提是如果5个顺序不排定，就没法找出第三个，可能我认为的这个前提也有误）

作者: luant 时间: 2005-3-5 09:26
标题: 显然不需要十次

先四个排序，最多6 次，设次序为A>B>C>D. 现在让剩下的E 和B 比较，如果E>B, 那么选B; 如果Ewww.ddhw.com

作者: 乱弹 时间: 2005-3-5 11:24
标题: Seven times is enough.

Four comparisons to decide the largest one and the smallest one among four bottles, which sure can not be the answer. Then three comparisons to decide the middle one among the remaining three bottles.

Do not know if it is the best.

作者: 乱弹 时间: 2005-3-5 12:01
标题: Six.

Deleting the smallest one among four bottles is a waste.
Three comparison to decide the largest one among four bottles.
(Compare A and B, then compare C and D; wlog, assume A>B, C>D, compare A and C, assume A>C)

Ignoring the largest one A, we are left
B, E and C>D.
Compare B and E, assume that B>E; compare B and C, assume that B>C. Compare E and C, the larger one is the 3rd among five bottles. (Six times. )

We did not compare the 4th and 5th. So seven times is enough to sort the list witht 5 members.

作者: 乱弹 时间: 2005-3-5 13:12
标题: The last sentence is wrong

The last sentence is wrong

欢迎光临珍珠湾ART (http://zzwav.com/)