瓶子体积比较

ob · 发表于 2005-3-5 03:51:48

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

我很高兴 · 发表于 2005-3-5 08:54:40

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

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

luant · 发表于 2005-3-5 09:26:27

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

乱弹 · 发表于 2005-3-5 11:24:50

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:24

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:18

The last sentence is wrong

		自动登录	找回密码
密码			立即注册

动态微博

瓶子体积比较

回复：瓶子体积比较[>:D<]

显然不需要十次

Seven times is enough.

Six.

The last sentence is wrong