瓶子体积比较

ob

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

www.ddhw.com

 

我很高兴

这个是不是等同于数据结构里的有5个数，用最坏的冒泡法（Bubble Sort）比较大小并排序的最坏的效率呢？ 是不是n(n-1)/2次？也就是10次？（我认为的前提是如果5个顺序不排定，就没法找出第三个，可能我认为的这个前提也有误） www.ddhw.com

luant

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

乱弹

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. www.ddhw.com   Do not know if it is the best. www.ddhw.com

乱弹

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. www.ddhw.com

乱弹

  The last sentence is wrong