※ 引述《walkwall (会走路的墙)》之铭言： : ※ 引述《Arton0306 (Ar藤)》之铭言： : : 现在有16个队伍 要参加比赛 : : 这比赛是强弱分明的 强者必胜(有递移律) : : 现在16队强弱都不一样 : : 那麽最少要比几场才能「找出最强队和最弱队」 : : 先列个比法 : : 1.先两两分组比，赢的为胜部，输的败部，需8场 : : 2.胜部有8队找出最强的，需7场 : : 3.败部有8队找出最弱的，需7场 : : 共22场， : : 请问有没有办法以更少的场数找出来？ : : 没有的话可否证明？ : 首先, 定义队伍状态四种 : N-未比较 W-胜候选 L-败候选 X-非第一也非最後 : 一开始当然所有队伍都是处於N状态, 而结束状态则必须只有一W一L且其他为X : 然而N状态的队伍经过一次比较後, 只可能转换成W或L, : W或L至少也要比一次後才可能转为X : 因此我们可以把四状态的资讯量分别定义为 N:0 W:1 L:1 X:2 : 从开始的状态(N*16,资讯量0), 到结束的状态(W*1+L*1+X*14, 资讯量30) : 要求出解共需30资讯量 : 接下来, 不管是什麽演算法, 如果资讯量无法到30, 就无法确定只剩一解 : 反过来说, 如果资讯量到30, 由於比较一次以後必然至少有一W, 所以就能确定只剩一解 : 所以现在的问题转换成 "最少需几次比较, 资讯量能到30?" : 假定有个最佳的演算法, 考虑每次比较能获得的资讯量, : 演算法能控制的是选用哪两个队伍对战, 但选定後用该组合的最低的资讯量考虑 : 这是因为所有演算法都应考虑其最差表现, 才知道最少可以几次判断出来 : 以你推文为例, 一次(W,N)的对战组合, 有可能获得1or2的资讯量, 最低为1 : 考量N,W,L,X四种状态的对战组合, 我们知道只有(N,N)的最低资讯量为2, : (W,L) (W,X) (L,X) (X,X)的最低资讯量为0, 其他最低为1 : 因此要达到最小次数, 就要尽量选(N,N), : 但是(N,N)每次配完後会少掉两个N (一定一个变W一个变L), 所以(N,N)只能用8次 : 这样资讯量达到16, 剩下的不管什麽猜法资讯量最多为1, 所以至少要14次 : 故8+14=22为最少对战次数得证 感谢 但我还有个问题 NWLX四个状态没有谁比谁大的资讯 也就是如果用这4个状态来表示某一连续的比较结果 会失去某些资讯 如现在只有abcd四队 a比b後知a>b c比d後知c>d 若只用状态来看 只知a,c为胜候胜 b,d为败候选 失去了a>b c>d的资讯 也许有的演算法可以利用这样的资讯 使得比较次数更少 这样是不是还要再证明 这样的资讯对任何算法都没有帮助呢？ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 114.36.36.150